1 /* 2 * INET An implementation of the TCP/IP protocol suite for the LINUX 3 * operating system. INET is implemented using the BSD Socket 4 * interface as the means of communication with the user level. 5 * 6 * Implementation of the Transmission Control Protocol(TCP). 7 * 8 * Authors: Ross Biro 9 * Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG> 10 * Mark Evans, <evansmp@uhura.aston.ac.uk> 11 * Corey Minyard <wf-rch!minyard@relay.EU.net> 12 * Florian La Roche, <flla@stud.uni-sb.de> 13 * Charles Hedrick, <hedrick@klinzhai.rutgers.edu> 14 * Linus Torvalds, <torvalds@cs.helsinki.fi> 15 * Alan Cox, <gw4pts@gw4pts.ampr.org> 16 * Matthew Dillon, <dillon@apollo.west.oic.com> 17 * Arnt Gulbrandsen, <agulbra@nvg.unit.no> 18 * Jorge Cwik, <jorge@laser.satlink.net> 19 */ 20 21 /* 22 * Changes: 23 * Pedro Roque : Fast Retransmit/Recovery. 24 * Two receive queues. 25 * Retransmit queue handled by TCP. 26 * Better retransmit timer handling. 27 * New congestion avoidance. 28 * Header prediction. 29 * Variable renaming. 30 * 31 * Eric : Fast Retransmit. 32 * Randy Scott : MSS option defines. 33 * Eric Schenk : Fixes to slow start algorithm. 34 * Eric Schenk : Yet another double ACK bug. 35 * Eric Schenk : Delayed ACK bug fixes. 36 * Eric Schenk : Floyd style fast retrans war avoidance. 37 * David S. Miller : Don't allow zero congestion window. 38 * Eric Schenk : Fix retransmitter so that it sends 39 * next packet on ack of previous packet. 40 * Andi Kleen : Moved open_request checking here 41 * and process RSTs for open_requests. 42 * Andi Kleen : Better prune_queue, and other fixes. 43 * Andrey Savochkin: Fix RTT measurements in the presence of 44 * timestamps. 45 * Andrey Savochkin: Check sequence numbers correctly when 46 * removing SACKs due to in sequence incoming 47 * data segments. 48 * Andi Kleen: Make sure we never ack data there is not 49 * enough room for. Also make this condition 50 * a fatal error if it might still happen. 51 * Andi Kleen: Add tcp_measure_rcv_mss to make 52 * connections with MSS<min(MTU,ann. MSS) 53 * work without delayed acks. 54 * Andi Kleen: Process packets with PSH set in the 55 * fast path. 56 * J Hadi Salim: ECN support 57 * Andrei Gurtov, 58 * Pasi Sarolahti, 59 * Panu Kuhlberg: Experimental audit of TCP (re)transmission 60 * engine. Lots of bugs are found. 61 * Pasi Sarolahti: F-RTO for dealing with spurious RTOs 62 */ 63 64 #define pr_fmt(fmt) "TCP: " fmt 65 66 #include <linux/mm.h> 67 #include <linux/slab.h> 68 #include <linux/module.h> 69 #include <linux/sysctl.h> 70 #include <linux/kernel.h> 71 #include <net/dst.h> 72 #include <net/tcp.h> 73 #include <net/inet_common.h> 74 #include <linux/ipsec.h> 75 #include <asm/unaligned.h> 76 #include <net/netdma.h> 77 78 int sysctl_tcp_timestamps __read_mostly = 1; 79 int sysctl_tcp_window_scaling __read_mostly = 1; 80 int sysctl_tcp_sack __read_mostly = 1; 81 int sysctl_tcp_fack __read_mostly = 1; 82 int sysctl_tcp_reordering __read_mostly = TCP_FASTRETRANS_THRESH; 83 EXPORT_SYMBOL(sysctl_tcp_reordering); 84 int sysctl_tcp_dsack __read_mostly = 1; 85 int sysctl_tcp_app_win __read_mostly = 31; 86 int sysctl_tcp_adv_win_scale __read_mostly = 1; 87 EXPORT_SYMBOL(sysctl_tcp_adv_win_scale); 88 89 /* rfc5961 challenge ack rate limiting */ 90 int sysctl_tcp_challenge_ack_limit = 100; 91 92 int sysctl_tcp_stdurg __read_mostly; 93 int sysctl_tcp_rfc1337 __read_mostly; 94 int sysctl_tcp_max_orphans __read_mostly = NR_FILE; 95 int sysctl_tcp_frto __read_mostly = 2; 96 97 int sysctl_tcp_thin_dupack __read_mostly; 98 99 int sysctl_tcp_moderate_rcvbuf __read_mostly = 1; 100 int sysctl_tcp_early_retrans __read_mostly = 3; 101 102 #define FLAG_DATA 0x01 /* Incoming frame contained data. */ 103 #define FLAG_WIN_UPDATE 0x02 /* Incoming ACK was a window update. */ 104 #define FLAG_DATA_ACKED 0x04 /* This ACK acknowledged new data. */ 105 #define FLAG_RETRANS_DATA_ACKED 0x08 /* "" "" some of which was retransmitted. */ 106 #define FLAG_SYN_ACKED 0x10 /* This ACK acknowledged SYN. */ 107 #define FLAG_DATA_SACKED 0x20 /* New SACK. */ 108 #define FLAG_ECE 0x40 /* ECE in this ACK */ 109 #define FLAG_SLOWPATH 0x100 /* Do not skip RFC checks for window update.*/ 110 #define FLAG_ORIG_SACK_ACKED 0x200 /* Never retransmitted data are (s)acked */ 111 #define FLAG_SND_UNA_ADVANCED 0x400 /* Snd_una was changed (!= FLAG_DATA_ACKED) */ 112 #define FLAG_DSACKING_ACK 0x800 /* SACK blocks contained D-SACK info */ 113 #define FLAG_SACK_RENEGING 0x2000 /* snd_una advanced to a sacked seq */ 114 #define FLAG_UPDATE_TS_RECENT 0x4000 /* tcp_replace_ts_recent() */ 115 116 #define FLAG_ACKED (FLAG_DATA_ACKED|FLAG_SYN_ACKED) 117 #define FLAG_NOT_DUP (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED) 118 #define FLAG_CA_ALERT (FLAG_DATA_SACKED|FLAG_ECE) 119 #define FLAG_FORWARD_PROGRESS (FLAG_ACKED|FLAG_DATA_SACKED) 120 121 #define TCP_REMNANT (TCP_FLAG_FIN|TCP_FLAG_URG|TCP_FLAG_SYN|TCP_FLAG_PSH) 122 #define TCP_HP_BITS (~(TCP_RESERVED_BITS|TCP_FLAG_PSH)) 123 124 /* Adapt the MSS value used to make delayed ack decision to the 125 * real world. 126 */ 127 static void tcp_measure_rcv_mss(struct sock *sk, const struct sk_buff *skb) 128 { 129 struct inet_connection_sock *icsk = inet_csk(sk); 130 const unsigned int lss = icsk->icsk_ack.last_seg_size; 131 unsigned int len; 132 133 icsk->icsk_ack.last_seg_size = 0; 134 135 /* skb->len may jitter because of SACKs, even if peer 136 * sends good full-sized frames. 137 */ 138 len = skb_shinfo(skb)->gso_size ? : skb->len; 139 if (len >= icsk->icsk_ack.rcv_mss) { 140 icsk->icsk_ack.rcv_mss = len; 141 } else { 142 /* Otherwise, we make more careful check taking into account, 143 * that SACKs block is variable. 144 * 145 * "len" is invariant segment length, including TCP header. 146 */ 147 len += skb->data - skb_transport_header(skb); 148 if (len >= TCP_MSS_DEFAULT + sizeof(struct tcphdr) || 149 /* If PSH is not set, packet should be 150 * full sized, provided peer TCP is not badly broken. 151 * This observation (if it is correct 8)) allows 152 * to handle super-low mtu links fairly. 153 */ 154 (len >= TCP_MIN_MSS + sizeof(struct tcphdr) && 155 !(tcp_flag_word(tcp_hdr(skb)) & TCP_REMNANT))) { 156 /* Subtract also invariant (if peer is RFC compliant), 157 * tcp header plus fixed timestamp option length. 158 * Resulting "len" is MSS free of SACK jitter. 159 */ 160 len -= tcp_sk(sk)->tcp_header_len; 161 icsk->icsk_ack.last_seg_size = len; 162 if (len == lss) { 163 icsk->icsk_ack.rcv_mss = len; 164 return; 165 } 166 } 167 if (icsk->icsk_ack.pending & ICSK_ACK_PUSHED) 168 icsk->icsk_ack.pending |= ICSK_ACK_PUSHED2; 169 icsk->icsk_ack.pending |= ICSK_ACK_PUSHED; 170 } 171 } 172 173 static void tcp_incr_quickack(struct sock *sk) 174 { 175 struct inet_connection_sock *icsk = inet_csk(sk); 176 unsigned int quickacks = tcp_sk(sk)->rcv_wnd / (2 * icsk->icsk_ack.rcv_mss); 177 178 if (quickacks == 0) 179 quickacks = 2; 180 if (quickacks > icsk->icsk_ack.quick) 181 icsk->icsk_ack.quick = min(quickacks, TCP_MAX_QUICKACKS); 182 } 183 184 static void tcp_enter_quickack_mode(struct sock *sk) 185 { 186 struct inet_connection_sock *icsk = inet_csk(sk); 187 tcp_incr_quickack(sk); 188 icsk->icsk_ack.pingpong = 0; 189 icsk->icsk_ack.ato = TCP_ATO_MIN; 190 } 191 192 /* Send ACKs quickly, if "quick" count is not exhausted 193 * and the session is not interactive. 194 */ 195 196 static inline bool tcp_in_quickack_mode(const struct sock *sk) 197 { 198 const struct inet_connection_sock *icsk = inet_csk(sk); 199 200 return icsk->icsk_ack.quick && !icsk->icsk_ack.pingpong; 201 } 202 203 static inline void TCP_ECN_queue_cwr(struct tcp_sock *tp) 204 { 205 if (tp->ecn_flags & TCP_ECN_OK) 206 tp->ecn_flags |= TCP_ECN_QUEUE_CWR; 207 } 208 209 static inline void TCP_ECN_accept_cwr(struct tcp_sock *tp, const struct sk_buff *skb) 210 { 211 if (tcp_hdr(skb)->cwr) 212 tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR; 213 } 214 215 static inline void TCP_ECN_withdraw_cwr(struct tcp_sock *tp) 216 { 217 tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR; 218 } 219 220 static inline void TCP_ECN_check_ce(struct tcp_sock *tp, const struct sk_buff *skb) 221 { 222 if (!(tp->ecn_flags & TCP_ECN_OK)) 223 return; 224 225 switch (TCP_SKB_CB(skb)->ip_dsfield & INET_ECN_MASK) { 226 case INET_ECN_NOT_ECT: 227 /* Funny extension: if ECT is not set on a segment, 228 * and we already seen ECT on a previous segment, 229 * it is probably a retransmit. 230 */ 231 if (tp->ecn_flags & TCP_ECN_SEEN) 232 tcp_enter_quickack_mode((struct sock *)tp); 233 break; 234 case INET_ECN_CE: 235 if (!(tp->ecn_flags & TCP_ECN_DEMAND_CWR)) { 236 /* Better not delay acks, sender can have a very low cwnd */ 237 tcp_enter_quickack_mode((struct sock *)tp); 238 tp->ecn_flags |= TCP_ECN_DEMAND_CWR; 239 } 240 /* fallinto */ 241 default: 242 tp->ecn_flags |= TCP_ECN_SEEN; 243 } 244 } 245 246 static inline void TCP_ECN_rcv_synack(struct tcp_sock *tp, const struct tcphdr *th) 247 { 248 if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || th->cwr)) 249 tp->ecn_flags &= ~TCP_ECN_OK; 250 } 251 252 static inline void TCP_ECN_rcv_syn(struct tcp_sock *tp, const struct tcphdr *th) 253 { 254 if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || !th->cwr)) 255 tp->ecn_flags &= ~TCP_ECN_OK; 256 } 257 258 static bool TCP_ECN_rcv_ecn_echo(const struct tcp_sock *tp, const struct tcphdr *th) 259 { 260 if (th->ece && !th->syn && (tp->ecn_flags & TCP_ECN_OK)) 261 return true; 262 return false; 263 } 264 265 /* Buffer size and advertised window tuning. 266 * 267 * 1. Tuning sk->sk_sndbuf, when connection enters established state. 268 */ 269 270 static void tcp_sndbuf_expand(struct sock *sk) 271 { 272 const struct tcp_sock *tp = tcp_sk(sk); 273 int sndmem, per_mss; 274 u32 nr_segs; 275 276 /* Worst case is non GSO/TSO : each frame consumes one skb 277 * and skb->head is kmalloced using power of two area of memory 278 */ 279 per_mss = max_t(u32, tp->rx_opt.mss_clamp, tp->mss_cache) + 280 MAX_TCP_HEADER + 281 SKB_DATA_ALIGN(sizeof(struct skb_shared_info)); 282 283 per_mss = roundup_pow_of_two(per_mss) + 284 SKB_DATA_ALIGN(sizeof(struct sk_buff)); 285 286 nr_segs = max_t(u32, TCP_INIT_CWND, tp->snd_cwnd); 287 nr_segs = max_t(u32, nr_segs, tp->reordering + 1); 288 289 /* Fast Recovery (RFC 5681 3.2) : 290 * Cubic needs 1.7 factor, rounded to 2 to include 291 * extra cushion (application might react slowly to POLLOUT) 292 */ 293 sndmem = 2 * nr_segs * per_mss; 294 295 if (sk->sk_sndbuf < sndmem) 296 sk->sk_sndbuf = min(sndmem, sysctl_tcp_wmem[2]); 297 } 298 299 /* 2. Tuning advertised window (window_clamp, rcv_ssthresh) 300 * 301 * All tcp_full_space() is split to two parts: "network" buffer, allocated 302 * forward and advertised in receiver window (tp->rcv_wnd) and 303 * "application buffer", required to isolate scheduling/application 304 * latencies from network. 305 * window_clamp is maximal advertised window. It can be less than 306 * tcp_full_space(), in this case tcp_full_space() - window_clamp 307 * is reserved for "application" buffer. The less window_clamp is 308 * the smoother our behaviour from viewpoint of network, but the lower 309 * throughput and the higher sensitivity of the connection to losses. 8) 310 * 311 * rcv_ssthresh is more strict window_clamp used at "slow start" 312 * phase to predict further behaviour of this connection. 313 * It is used for two goals: 314 * - to enforce header prediction at sender, even when application 315 * requires some significant "application buffer". It is check #1. 316 * - to prevent pruning of receive queue because of misprediction 317 * of receiver window. Check #2. 318 * 319 * The scheme does not work when sender sends good segments opening 320 * window and then starts to feed us spaghetti. But it should work 321 * in common situations. Otherwise, we have to rely on queue collapsing. 322 */ 323 324 /* Slow part of check#2. */ 325 static int __tcp_grow_window(const struct sock *sk, const struct sk_buff *skb) 326 { 327 struct tcp_sock *tp = tcp_sk(sk); 328 /* Optimize this! */ 329 int truesize = tcp_win_from_space(skb->truesize) >> 1; 330 int window = tcp_win_from_space(sysctl_tcp_rmem[2]) >> 1; 331 332 while (tp->rcv_ssthresh <= window) { 333 if (truesize <= skb->len) 334 return 2 * inet_csk(sk)->icsk_ack.rcv_mss; 335 336 truesize >>= 1; 337 window >>= 1; 338 } 339 return 0; 340 } 341 342 static void tcp_grow_window(struct sock *sk, const struct sk_buff *skb) 343 { 344 struct tcp_sock *tp = tcp_sk(sk); 345 346 /* Check #1 */ 347 if (tp->rcv_ssthresh < tp->window_clamp && 348 (int)tp->rcv_ssthresh < tcp_space(sk) && 349 !sk_under_memory_pressure(sk)) { 350 int incr; 351 352 /* Check #2. Increase window, if skb with such overhead 353 * will fit to rcvbuf in future. 354 */ 355 if (tcp_win_from_space(skb->truesize) <= skb->len) 356 incr = 2 * tp->advmss; 357 else 358 incr = __tcp_grow_window(sk, skb); 359 360 if (incr) { 361 incr = max_t(int, incr, 2 * skb->len); 362 tp->rcv_ssthresh = min(tp->rcv_ssthresh + incr, 363 tp->window_clamp); 364 inet_csk(sk)->icsk_ack.quick |= 1; 365 } 366 } 367 } 368 369 /* 3. Tuning rcvbuf, when connection enters established state. */ 370 static void tcp_fixup_rcvbuf(struct sock *sk) 371 { 372 u32 mss = tcp_sk(sk)->advmss; 373 int rcvmem; 374 375 rcvmem = 2 * SKB_TRUESIZE(mss + MAX_TCP_HEADER) * 376 tcp_default_init_rwnd(mss); 377 378 /* Dynamic Right Sizing (DRS) has 2 to 3 RTT latency 379 * Allow enough cushion so that sender is not limited by our window 380 */ 381 if (sysctl_tcp_moderate_rcvbuf) 382 rcvmem <<= 2; 383 384 if (sk->sk_rcvbuf < rcvmem) 385 sk->sk_rcvbuf = min(rcvmem, sysctl_tcp_rmem[2]); 386 } 387 388 /* 4. Try to fixup all. It is made immediately after connection enters 389 * established state. 390 */ 391 void tcp_init_buffer_space(struct sock *sk) 392 { 393 struct tcp_sock *tp = tcp_sk(sk); 394 int maxwin; 395 396 if (!(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) 397 tcp_fixup_rcvbuf(sk); 398 if (!(sk->sk_userlocks & SOCK_SNDBUF_LOCK)) 399 tcp_sndbuf_expand(sk); 400 401 tp->rcvq_space.space = tp->rcv_wnd; 402 tp->rcvq_space.time = tcp_time_stamp; 403 tp->rcvq_space.seq = tp->copied_seq; 404 405 maxwin = tcp_full_space(sk); 406 407 if (tp->window_clamp >= maxwin) { 408 tp->window_clamp = maxwin; 409 410 if (sysctl_tcp_app_win && maxwin > 4 * tp->advmss) 411 tp->window_clamp = max(maxwin - 412 (maxwin >> sysctl_tcp_app_win), 413 4 * tp->advmss); 414 } 415 416 /* Force reservation of one segment. */ 417 if (sysctl_tcp_app_win && 418 tp->window_clamp > 2 * tp->advmss && 419 tp->window_clamp + tp->advmss > maxwin) 420 tp->window_clamp = max(2 * tp->advmss, maxwin - tp->advmss); 421 422 tp->rcv_ssthresh = min(tp->rcv_ssthresh, tp->window_clamp); 423 tp->snd_cwnd_stamp = tcp_time_stamp; 424 } 425 426 /* 5. Recalculate window clamp after socket hit its memory bounds. */ 427 static void tcp_clamp_window(struct sock *sk) 428 { 429 struct tcp_sock *tp = tcp_sk(sk); 430 struct inet_connection_sock *icsk = inet_csk(sk); 431 432 icsk->icsk_ack.quick = 0; 433 434 if (sk->sk_rcvbuf < sysctl_tcp_rmem[2] && 435 !(sk->sk_userlocks & SOCK_RCVBUF_LOCK) && 436 !sk_under_memory_pressure(sk) && 437 sk_memory_allocated(sk) < sk_prot_mem_limits(sk, 0)) { 438 sk->sk_rcvbuf = min(atomic_read(&sk->sk_rmem_alloc), 439 sysctl_tcp_rmem[2]); 440 } 441 if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf) 442 tp->rcv_ssthresh = min(tp->window_clamp, 2U * tp->advmss); 443 } 444 445 /* Initialize RCV_MSS value. 446 * RCV_MSS is an our guess about MSS used by the peer. 447 * We haven't any direct information about the MSS. 448 * It's better to underestimate the RCV_MSS rather than overestimate. 449 * Overestimations make us ACKing less frequently than needed. 450 * Underestimations are more easy to detect and fix by tcp_measure_rcv_mss(). 451 */ 452 void tcp_initialize_rcv_mss(struct sock *sk) 453 { 454 const struct tcp_sock *tp = tcp_sk(sk); 455 unsigned int hint = min_t(unsigned int, tp->advmss, tp->mss_cache); 456 457 hint = min(hint, tp->rcv_wnd / 2); 458 hint = min(hint, TCP_MSS_DEFAULT); 459 hint = max(hint, TCP_MIN_MSS); 460 461 inet_csk(sk)->icsk_ack.rcv_mss = hint; 462 } 463 EXPORT_SYMBOL(tcp_initialize_rcv_mss); 464 465 /* Receiver "autotuning" code. 466 * 467 * The algorithm for RTT estimation w/o timestamps is based on 468 * Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL. 469 * <http://public.lanl.gov/radiant/pubs.html#DRS> 470 * 471 * More detail on this code can be found at 472 * <http://staff.psc.edu/jheffner/>, 473 * though this reference is out of date. A new paper 474 * is pending. 475 */ 476 static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep) 477 { 478 u32 new_sample = tp->rcv_rtt_est.rtt; 479 long m = sample; 480 481 if (m == 0) 482 m = 1; 483 484 if (new_sample != 0) { 485 /* If we sample in larger samples in the non-timestamp 486 * case, we could grossly overestimate the RTT especially 487 * with chatty applications or bulk transfer apps which 488 * are stalled on filesystem I/O. 489 * 490 * Also, since we are only going for a minimum in the 491 * non-timestamp case, we do not smooth things out 492 * else with timestamps disabled convergence takes too 493 * long. 494 */ 495 if (!win_dep) { 496 m -= (new_sample >> 3); 497 new_sample += m; 498 } else { 499 m <<= 3; 500 if (m < new_sample) 501 new_sample = m; 502 } 503 } else { 504 /* No previous measure. */ 505 new_sample = m << 3; 506 } 507 508 if (tp->rcv_rtt_est.rtt != new_sample) 509 tp->rcv_rtt_est.rtt = new_sample; 510 } 511 512 static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp) 513 { 514 if (tp->rcv_rtt_est.time == 0) 515 goto new_measure; 516 if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq)) 517 return; 518 tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rcv_rtt_est.time, 1); 519 520 new_measure: 521 tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd; 522 tp->rcv_rtt_est.time = tcp_time_stamp; 523 } 524 525 static inline void tcp_rcv_rtt_measure_ts(struct sock *sk, 526 const struct sk_buff *skb) 527 { 528 struct tcp_sock *tp = tcp_sk(sk); 529 if (tp->rx_opt.rcv_tsecr && 530 (TCP_SKB_CB(skb)->end_seq - 531 TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss)) 532 tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0); 533 } 534 535 /* 536 * This function should be called every time data is copied to user space. 537 * It calculates the appropriate TCP receive buffer space. 538 */ 539 void tcp_rcv_space_adjust(struct sock *sk) 540 { 541 struct tcp_sock *tp = tcp_sk(sk); 542 int time; 543 int copied; 544 545 time = tcp_time_stamp - tp->rcvq_space.time; 546 if (time < (tp->rcv_rtt_est.rtt >> 3) || tp->rcv_rtt_est.rtt == 0) 547 return; 548 549 /* Number of bytes copied to user in last RTT */ 550 copied = tp->copied_seq - tp->rcvq_space.seq; 551 if (copied <= tp->rcvq_space.space) 552 goto new_measure; 553 554 /* A bit of theory : 555 * copied = bytes received in previous RTT, our base window 556 * To cope with packet losses, we need a 2x factor 557 * To cope with slow start, and sender growing its cwin by 100 % 558 * every RTT, we need a 4x factor, because the ACK we are sending 559 * now is for the next RTT, not the current one : 560 * <prev RTT . ><current RTT .. ><next RTT .... > 561 */ 562 563 if (sysctl_tcp_moderate_rcvbuf && 564 !(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) { 565 int rcvwin, rcvmem, rcvbuf; 566 567 /* minimal window to cope with packet losses, assuming 568 * steady state. Add some cushion because of small variations. 569 */ 570 rcvwin = (copied << 1) + 16 * tp->advmss; 571 572 /* If rate increased by 25%, 573 * assume slow start, rcvwin = 3 * copied 574 * If rate increased by 50%, 575 * assume sender can use 2x growth, rcvwin = 4 * copied 576 */ 577 if (copied >= 578 tp->rcvq_space.space + (tp->rcvq_space.space >> 2)) { 579 if (copied >= 580 tp->rcvq_space.space + (tp->rcvq_space.space >> 1)) 581 rcvwin <<= 1; 582 else 583 rcvwin += (rcvwin >> 1); 584 } 585 586 rcvmem = SKB_TRUESIZE(tp->advmss + MAX_TCP_HEADER); 587 while (tcp_win_from_space(rcvmem) < tp->advmss) 588 rcvmem += 128; 589 590 rcvbuf = min(rcvwin / tp->advmss * rcvmem, sysctl_tcp_rmem[2]); 591 if (rcvbuf > sk->sk_rcvbuf) { 592 sk->sk_rcvbuf = rcvbuf; 593 594 /* Make the window clamp follow along. */ 595 tp->window_clamp = rcvwin; 596 } 597 } 598 tp->rcvq_space.space = copied; 599 600 new_measure: 601 tp->rcvq_space.seq = tp->copied_seq; 602 tp->rcvq_space.time = tcp_time_stamp; 603 } 604 605 /* There is something which you must keep in mind when you analyze the 606 * behavior of the tp->ato delayed ack timeout interval. When a 607 * connection starts up, we want to ack as quickly as possible. The 608 * problem is that "good" TCP's do slow start at the beginning of data 609 * transmission. The means that until we send the first few ACK's the 610 * sender will sit on his end and only queue most of his data, because 611 * he can only send snd_cwnd unacked packets at any given time. For 612 * each ACK we send, he increments snd_cwnd and transmits more of his 613 * queue. -DaveM 614 */ 615 static void tcp_event_data_recv(struct sock *sk, struct sk_buff *skb) 616 { 617 struct tcp_sock *tp = tcp_sk(sk); 618 struct inet_connection_sock *icsk = inet_csk(sk); 619 u32 now; 620 621 inet_csk_schedule_ack(sk); 622 623 tcp_measure_rcv_mss(sk, skb); 624 625 tcp_rcv_rtt_measure(tp); 626 627 now = tcp_time_stamp; 628 629 if (!icsk->icsk_ack.ato) { 630 /* The _first_ data packet received, initialize 631 * delayed ACK engine. 632 */ 633 tcp_incr_quickack(sk); 634 icsk->icsk_ack.ato = TCP_ATO_MIN; 635 } else { 636 int m = now - icsk->icsk_ack.lrcvtime; 637 638 if (m <= TCP_ATO_MIN / 2) { 639 /* The fastest case is the first. */ 640 icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + TCP_ATO_MIN / 2; 641 } else if (m < icsk->icsk_ack.ato) { 642 icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + m; 643 if (icsk->icsk_ack.ato > icsk->icsk_rto) 644 icsk->icsk_ack.ato = icsk->icsk_rto; 645 } else if (m > icsk->icsk_rto) { 646 /* Too long gap. Apparently sender failed to 647 * restart window, so that we send ACKs quickly. 648 */ 649 tcp_incr_quickack(sk); 650 sk_mem_reclaim(sk); 651 } 652 } 653 icsk->icsk_ack.lrcvtime = now; 654 655 TCP_ECN_check_ce(tp, skb); 656 657 if (skb->len >= 128) 658 tcp_grow_window(sk, skb); 659 } 660 661 /* Called to compute a smoothed rtt estimate. The data fed to this 662 * routine either comes from timestamps, or from segments that were 663 * known _not_ to have been retransmitted [see Karn/Partridge 664 * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88 665 * piece by Van Jacobson. 666 * NOTE: the next three routines used to be one big routine. 667 * To save cycles in the RFC 1323 implementation it was better to break 668 * it up into three procedures. -- erics 669 */ 670 static void tcp_rtt_estimator(struct sock *sk, long mrtt_us) 671 { 672 struct tcp_sock *tp = tcp_sk(sk); 673 long m = mrtt_us; /* RTT */ 674 u32 srtt = tp->srtt_us; 675 676 /* The following amusing code comes from Jacobson's 677 * article in SIGCOMM '88. Note that rtt and mdev 678 * are scaled versions of rtt and mean deviation. 679 * This is designed to be as fast as possible 680 * m stands for "measurement". 681 * 682 * On a 1990 paper the rto value is changed to: 683 * RTO = rtt + 4 * mdev 684 * 685 * Funny. This algorithm seems to be very broken. 686 * These formulae increase RTO, when it should be decreased, increase 687 * too slowly, when it should be increased quickly, decrease too quickly 688 * etc. I guess in BSD RTO takes ONE value, so that it is absolutely 689 * does not matter how to _calculate_ it. Seems, it was trap 690 * that VJ failed to avoid. 8) 691 */ 692 if (srtt != 0) { 693 m -= (srtt >> 3); /* m is now error in rtt est */ 694 srtt += m; /* rtt = 7/8 rtt + 1/8 new */ 695 if (m < 0) { 696 m = -m; /* m is now abs(error) */ 697 m -= (tp->mdev_us >> 2); /* similar update on mdev */ 698 /* This is similar to one of Eifel findings. 699 * Eifel blocks mdev updates when rtt decreases. 700 * This solution is a bit different: we use finer gain 701 * for mdev in this case (alpha*beta). 702 * Like Eifel it also prevents growth of rto, 703 * but also it limits too fast rto decreases, 704 * happening in pure Eifel. 705 */ 706 if (m > 0) 707 m >>= 3; 708 } else { 709 m -= (tp->mdev_us >> 2); /* similar update on mdev */ 710 } 711 tp->mdev_us += m; /* mdev = 3/4 mdev + 1/4 new */ 712 if (tp->mdev_us > tp->mdev_max_us) { 713 tp->mdev_max_us = tp->mdev_us; 714 if (tp->mdev_max_us > tp->rttvar_us) 715 tp->rttvar_us = tp->mdev_max_us; 716 } 717 if (after(tp->snd_una, tp->rtt_seq)) { 718 if (tp->mdev_max_us < tp->rttvar_us) 719 tp->rttvar_us -= (tp->rttvar_us - tp->mdev_max_us) >> 2; 720 tp->rtt_seq = tp->snd_nxt; 721 tp->mdev_max_us = tcp_rto_min_us(sk); 722 } 723 } else { 724 /* no previous measure. */ 725 srtt = m << 3; /* take the measured time to be rtt */ 726 tp->mdev_us = m << 1; /* make sure rto = 3*rtt */ 727 tp->rttvar_us = max(tp->mdev_us, tcp_rto_min_us(sk)); 728 tp->mdev_max_us = tp->rttvar_us; 729 tp->rtt_seq = tp->snd_nxt; 730 } 731 tp->srtt_us = max(1U, srtt); 732 } 733 734 /* Set the sk_pacing_rate to allow proper sizing of TSO packets. 735 * Note: TCP stack does not yet implement pacing. 736 * FQ packet scheduler can be used to implement cheap but effective 737 * TCP pacing, to smooth the burst on large writes when packets 738 * in flight is significantly lower than cwnd (or rwin) 739 */ 740 static void tcp_update_pacing_rate(struct sock *sk) 741 { 742 const struct tcp_sock *tp = tcp_sk(sk); 743 u64 rate; 744 745 /* set sk_pacing_rate to 200 % of current rate (mss * cwnd / srtt) */ 746 rate = (u64)tp->mss_cache * 2 * (USEC_PER_SEC << 3); 747 748 rate *= max(tp->snd_cwnd, tp->packets_out); 749 750 if (likely(tp->srtt_us)) 751 do_div(rate, tp->srtt_us); 752 753 /* ACCESS_ONCE() is needed because sch_fq fetches sk_pacing_rate 754 * without any lock. We want to make sure compiler wont store 755 * intermediate values in this location. 756 */ 757 ACCESS_ONCE(sk->sk_pacing_rate) = min_t(u64, rate, 758 sk->sk_max_pacing_rate); 759 } 760 761 /* Calculate rto without backoff. This is the second half of Van Jacobson's 762 * routine referred to above. 763 */ 764 static void tcp_set_rto(struct sock *sk) 765 { 766 const struct tcp_sock *tp = tcp_sk(sk); 767 /* Old crap is replaced with new one. 8) 768 * 769 * More seriously: 770 * 1. If rtt variance happened to be less 50msec, it is hallucination. 771 * It cannot be less due to utterly erratic ACK generation made 772 * at least by solaris and freebsd. "Erratic ACKs" has _nothing_ 773 * to do with delayed acks, because at cwnd>2 true delack timeout 774 * is invisible. Actually, Linux-2.4 also generates erratic 775 * ACKs in some circumstances. 776 */ 777 inet_csk(sk)->icsk_rto = __tcp_set_rto(tp); 778 779 /* 2. Fixups made earlier cannot be right. 780 * If we do not estimate RTO correctly without them, 781 * all the algo is pure shit and should be replaced 782 * with correct one. It is exactly, which we pretend to do. 783 */ 784 785 /* NOTE: clamping at TCP_RTO_MIN is not required, current algo 786 * guarantees that rto is higher. 787 */ 788 tcp_bound_rto(sk); 789 } 790 791 __u32 tcp_init_cwnd(const struct tcp_sock *tp, const struct dst_entry *dst) 792 { 793 __u32 cwnd = (dst ? dst_metric(dst, RTAX_INITCWND) : 0); 794 795 if (!cwnd) 796 cwnd = TCP_INIT_CWND; 797 return min_t(__u32, cwnd, tp->snd_cwnd_clamp); 798 } 799 800 /* 801 * Packet counting of FACK is based on in-order assumptions, therefore TCP 802 * disables it when reordering is detected 803 */ 804 void tcp_disable_fack(struct tcp_sock *tp) 805 { 806 /* RFC3517 uses different metric in lost marker => reset on change */ 807 if (tcp_is_fack(tp)) 808 tp->lost_skb_hint = NULL; 809 tp->rx_opt.sack_ok &= ~TCP_FACK_ENABLED; 810 } 811 812 /* Take a notice that peer is sending D-SACKs */ 813 static void tcp_dsack_seen(struct tcp_sock *tp) 814 { 815 tp->rx_opt.sack_ok |= TCP_DSACK_SEEN; 816 } 817 818 static void tcp_update_reordering(struct sock *sk, const int metric, 819 const int ts) 820 { 821 struct tcp_sock *tp = tcp_sk(sk); 822 if (metric > tp->reordering) { 823 int mib_idx; 824 825 tp->reordering = min(TCP_MAX_REORDERING, metric); 826 827 /* This exciting event is worth to be remembered. 8) */ 828 if (ts) 829 mib_idx = LINUX_MIB_TCPTSREORDER; 830 else if (tcp_is_reno(tp)) 831 mib_idx = LINUX_MIB_TCPRENOREORDER; 832 else if (tcp_is_fack(tp)) 833 mib_idx = LINUX_MIB_TCPFACKREORDER; 834 else 835 mib_idx = LINUX_MIB_TCPSACKREORDER; 836 837 NET_INC_STATS_BH(sock_net(sk), mib_idx); 838 #if FASTRETRANS_DEBUG > 1 839 pr_debug("Disorder%d %d %u f%u s%u rr%d\n", 840 tp->rx_opt.sack_ok, inet_csk(sk)->icsk_ca_state, 841 tp->reordering, 842 tp->fackets_out, 843 tp->sacked_out, 844 tp->undo_marker ? tp->undo_retrans : 0); 845 #endif 846 tcp_disable_fack(tp); 847 } 848 849 if (metric > 0) 850 tcp_disable_early_retrans(tp); 851 } 852 853 /* This must be called before lost_out is incremented */ 854 static void tcp_verify_retransmit_hint(struct tcp_sock *tp, struct sk_buff *skb) 855 { 856 if ((tp->retransmit_skb_hint == NULL) || 857 before(TCP_SKB_CB(skb)->seq, 858 TCP_SKB_CB(tp->retransmit_skb_hint)->seq)) 859 tp->retransmit_skb_hint = skb; 860 861 if (!tp->lost_out || 862 after(TCP_SKB_CB(skb)->end_seq, tp->retransmit_high)) 863 tp->retransmit_high = TCP_SKB_CB(skb)->end_seq; 864 } 865 866 static void tcp_skb_mark_lost(struct tcp_sock *tp, struct sk_buff *skb) 867 { 868 if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) { 869 tcp_verify_retransmit_hint(tp, skb); 870 871 tp->lost_out += tcp_skb_pcount(skb); 872 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 873 } 874 } 875 876 static void tcp_skb_mark_lost_uncond_verify(struct tcp_sock *tp, 877 struct sk_buff *skb) 878 { 879 tcp_verify_retransmit_hint(tp, skb); 880 881 if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) { 882 tp->lost_out += tcp_skb_pcount(skb); 883 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 884 } 885 } 886 887 /* This procedure tags the retransmission queue when SACKs arrive. 888 * 889 * We have three tag bits: SACKED(S), RETRANS(R) and LOST(L). 890 * Packets in queue with these bits set are counted in variables 891 * sacked_out, retrans_out and lost_out, correspondingly. 892 * 893 * Valid combinations are: 894 * Tag InFlight Description 895 * 0 1 - orig segment is in flight. 896 * S 0 - nothing flies, orig reached receiver. 897 * L 0 - nothing flies, orig lost by net. 898 * R 2 - both orig and retransmit are in flight. 899 * L|R 1 - orig is lost, retransmit is in flight. 900 * S|R 1 - orig reached receiver, retrans is still in flight. 901 * (L|S|R is logically valid, it could occur when L|R is sacked, 902 * but it is equivalent to plain S and code short-curcuits it to S. 903 * L|S is logically invalid, it would mean -1 packet in flight 8)) 904 * 905 * These 6 states form finite state machine, controlled by the following events: 906 * 1. New ACK (+SACK) arrives. (tcp_sacktag_write_queue()) 907 * 2. Retransmission. (tcp_retransmit_skb(), tcp_xmit_retransmit_queue()) 908 * 3. Loss detection event of two flavors: 909 * A. Scoreboard estimator decided the packet is lost. 910 * A'. Reno "three dupacks" marks head of queue lost. 911 * A''. Its FACK modification, head until snd.fack is lost. 912 * B. SACK arrives sacking SND.NXT at the moment, when the 913 * segment was retransmitted. 914 * 4. D-SACK added new rule: D-SACK changes any tag to S. 915 * 916 * It is pleasant to note, that state diagram turns out to be commutative, 917 * so that we are allowed not to be bothered by order of our actions, 918 * when multiple events arrive simultaneously. (see the function below). 919 * 920 * Reordering detection. 921 * -------------------- 922 * Reordering metric is maximal distance, which a packet can be displaced 923 * in packet stream. With SACKs we can estimate it: 924 * 925 * 1. SACK fills old hole and the corresponding segment was not 926 * ever retransmitted -> reordering. Alas, we cannot use it 927 * when segment was retransmitted. 928 * 2. The last flaw is solved with D-SACK. D-SACK arrives 929 * for retransmitted and already SACKed segment -> reordering.. 930 * Both of these heuristics are not used in Loss state, when we cannot 931 * account for retransmits accurately. 932 * 933 * SACK block validation. 934 * ---------------------- 935 * 936 * SACK block range validation checks that the received SACK block fits to 937 * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT. 938 * Note that SND.UNA is not included to the range though being valid because 939 * it means that the receiver is rather inconsistent with itself reporting 940 * SACK reneging when it should advance SND.UNA. Such SACK block this is 941 * perfectly valid, however, in light of RFC2018 which explicitly states 942 * that "SACK block MUST reflect the newest segment. Even if the newest 943 * segment is going to be discarded ...", not that it looks very clever 944 * in case of head skb. Due to potentional receiver driven attacks, we 945 * choose to avoid immediate execution of a walk in write queue due to 946 * reneging and defer head skb's loss recovery to standard loss recovery 947 * procedure that will eventually trigger (nothing forbids us doing this). 948 * 949 * Implements also blockage to start_seq wrap-around. Problem lies in the 950 * fact that though start_seq (s) is before end_seq (i.e., not reversed), 951 * there's no guarantee that it will be before snd_nxt (n). The problem 952 * happens when start_seq resides between end_seq wrap (e_w) and snd_nxt 953 * wrap (s_w): 954 * 955 * <- outs wnd -> <- wrapzone -> 956 * u e n u_w e_w s n_w 957 * | | | | | | | 958 * |<------------+------+----- TCP seqno space --------------+---------->| 959 * ...-- <2^31 ->| |<--------... 960 * ...---- >2^31 ------>| |<--------... 961 * 962 * Current code wouldn't be vulnerable but it's better still to discard such 963 * crazy SACK blocks. Doing this check for start_seq alone closes somewhat 964 * similar case (end_seq after snd_nxt wrap) as earlier reversed check in 965 * snd_nxt wrap -> snd_una region will then become "well defined", i.e., 966 * equal to the ideal case (infinite seqno space without wrap caused issues). 967 * 968 * With D-SACK the lower bound is extended to cover sequence space below 969 * SND.UNA down to undo_marker, which is the last point of interest. Yet 970 * again, D-SACK block must not to go across snd_una (for the same reason as 971 * for the normal SACK blocks, explained above). But there all simplicity 972 * ends, TCP might receive valid D-SACKs below that. As long as they reside 973 * fully below undo_marker they do not affect behavior in anyway and can 974 * therefore be safely ignored. In rare cases (which are more or less 975 * theoretical ones), the D-SACK will nicely cross that boundary due to skb 976 * fragmentation and packet reordering past skb's retransmission. To consider 977 * them correctly, the acceptable range must be extended even more though 978 * the exact amount is rather hard to quantify. However, tp->max_window can 979 * be used as an exaggerated estimate. 980 */ 981 static bool tcp_is_sackblock_valid(struct tcp_sock *tp, bool is_dsack, 982 u32 start_seq, u32 end_seq) 983 { 984 /* Too far in future, or reversed (interpretation is ambiguous) */ 985 if (after(end_seq, tp->snd_nxt) || !before(start_seq, end_seq)) 986 return false; 987 988 /* Nasty start_seq wrap-around check (see comments above) */ 989 if (!before(start_seq, tp->snd_nxt)) 990 return false; 991 992 /* In outstanding window? ...This is valid exit for D-SACKs too. 993 * start_seq == snd_una is non-sensical (see comments above) 994 */ 995 if (after(start_seq, tp->snd_una)) 996 return true; 997 998 if (!is_dsack || !tp->undo_marker) 999 return false; 1000 1001 /* ...Then it's D-SACK, and must reside below snd_una completely */ 1002 if (after(end_seq, tp->snd_una)) 1003 return false; 1004 1005 if (!before(start_seq, tp->undo_marker)) 1006 return true; 1007 1008 /* Too old */ 1009 if (!after(end_seq, tp->undo_marker)) 1010 return false; 1011 1012 /* Undo_marker boundary crossing (overestimates a lot). Known already: 1013 * start_seq < undo_marker and end_seq >= undo_marker. 1014 */ 1015 return !before(start_seq, end_seq - tp->max_window); 1016 } 1017 1018 /* Check for lost retransmit. This superb idea is borrowed from "ratehalving". 1019 * Event "B". Later note: FACK people cheated me again 8), we have to account 1020 * for reordering! Ugly, but should help. 1021 * 1022 * Search retransmitted skbs from write_queue that were sent when snd_nxt was 1023 * less than what is now known to be received by the other end (derived from 1024 * highest SACK block). Also calculate the lowest snd_nxt among the remaining 1025 * retransmitted skbs to avoid some costly processing per ACKs. 1026 */ 1027 static void tcp_mark_lost_retrans(struct sock *sk) 1028 { 1029 const struct inet_connection_sock *icsk = inet_csk(sk); 1030 struct tcp_sock *tp = tcp_sk(sk); 1031 struct sk_buff *skb; 1032 int cnt = 0; 1033 u32 new_low_seq = tp->snd_nxt; 1034 u32 received_upto = tcp_highest_sack_seq(tp); 1035 1036 if (!tcp_is_fack(tp) || !tp->retrans_out || 1037 !after(received_upto, tp->lost_retrans_low) || 1038 icsk->icsk_ca_state != TCP_CA_Recovery) 1039 return; 1040 1041 tcp_for_write_queue(skb, sk) { 1042 u32 ack_seq = TCP_SKB_CB(skb)->ack_seq; 1043 1044 if (skb == tcp_send_head(sk)) 1045 break; 1046 if (cnt == tp->retrans_out) 1047 break; 1048 if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) 1049 continue; 1050 1051 if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS)) 1052 continue; 1053 1054 /* TODO: We would like to get rid of tcp_is_fack(tp) only 1055 * constraint here (see above) but figuring out that at 1056 * least tp->reordering SACK blocks reside between ack_seq 1057 * and received_upto is not easy task to do cheaply with 1058 * the available datastructures. 1059 * 1060 * Whether FACK should check here for tp->reordering segs 1061 * in-between one could argue for either way (it would be 1062 * rather simple to implement as we could count fack_count 1063 * during the walk and do tp->fackets_out - fack_count). 1064 */ 1065 if (after(received_upto, ack_seq)) { 1066 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS; 1067 tp->retrans_out -= tcp_skb_pcount(skb); 1068 1069 tcp_skb_mark_lost_uncond_verify(tp, skb); 1070 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSTRETRANSMIT); 1071 } else { 1072 if (before(ack_seq, new_low_seq)) 1073 new_low_seq = ack_seq; 1074 cnt += tcp_skb_pcount(skb); 1075 } 1076 } 1077 1078 if (tp->retrans_out) 1079 tp->lost_retrans_low = new_low_seq; 1080 } 1081 1082 static bool tcp_check_dsack(struct sock *sk, const struct sk_buff *ack_skb, 1083 struct tcp_sack_block_wire *sp, int num_sacks, 1084 u32 prior_snd_una) 1085 { 1086 struct tcp_sock *tp = tcp_sk(sk); 1087 u32 start_seq_0 = get_unaligned_be32(&sp[0].start_seq); 1088 u32 end_seq_0 = get_unaligned_be32(&sp[0].end_seq); 1089 bool dup_sack = false; 1090 1091 if (before(start_seq_0, TCP_SKB_CB(ack_skb)->ack_seq)) { 1092 dup_sack = true; 1093 tcp_dsack_seen(tp); 1094 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKRECV); 1095 } else if (num_sacks > 1) { 1096 u32 end_seq_1 = get_unaligned_be32(&sp[1].end_seq); 1097 u32 start_seq_1 = get_unaligned_be32(&sp[1].start_seq); 1098 1099 if (!after(end_seq_0, end_seq_1) && 1100 !before(start_seq_0, start_seq_1)) { 1101 dup_sack = true; 1102 tcp_dsack_seen(tp); 1103 NET_INC_STATS_BH(sock_net(sk), 1104 LINUX_MIB_TCPDSACKOFORECV); 1105 } 1106 } 1107 1108 /* D-SACK for already forgotten data... Do dumb counting. */ 1109 if (dup_sack && tp->undo_marker && tp->undo_retrans && 1110 !after(end_seq_0, prior_snd_una) && 1111 after(end_seq_0, tp->undo_marker)) 1112 tp->undo_retrans--; 1113 1114 return dup_sack; 1115 } 1116 1117 struct tcp_sacktag_state { 1118 int reord; 1119 int fack_count; 1120 long rtt_us; /* RTT measured by SACKing never-retransmitted data */ 1121 int flag; 1122 }; 1123 1124 /* Check if skb is fully within the SACK block. In presence of GSO skbs, 1125 * the incoming SACK may not exactly match but we can find smaller MSS 1126 * aligned portion of it that matches. Therefore we might need to fragment 1127 * which may fail and creates some hassle (caller must handle error case 1128 * returns). 1129 * 1130 * FIXME: this could be merged to shift decision code 1131 */ 1132 static int tcp_match_skb_to_sack(struct sock *sk, struct sk_buff *skb, 1133 u32 start_seq, u32 end_seq) 1134 { 1135 int err; 1136 bool in_sack; 1137 unsigned int pkt_len; 1138 unsigned int mss; 1139 1140 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) && 1141 !before(end_seq, TCP_SKB_CB(skb)->end_seq); 1142 1143 if (tcp_skb_pcount(skb) > 1 && !in_sack && 1144 after(TCP_SKB_CB(skb)->end_seq, start_seq)) { 1145 mss = tcp_skb_mss(skb); 1146 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq); 1147 1148 if (!in_sack) { 1149 pkt_len = start_seq - TCP_SKB_CB(skb)->seq; 1150 if (pkt_len < mss) 1151 pkt_len = mss; 1152 } else { 1153 pkt_len = end_seq - TCP_SKB_CB(skb)->seq; 1154 if (pkt_len < mss) 1155 return -EINVAL; 1156 } 1157 1158 /* Round if necessary so that SACKs cover only full MSSes 1159 * and/or the remaining small portion (if present) 1160 */ 1161 if (pkt_len > mss) { 1162 unsigned int new_len = (pkt_len / mss) * mss; 1163 if (!in_sack && new_len < pkt_len) { 1164 new_len += mss; 1165 if (new_len >= skb->len) 1166 return 0; 1167 } 1168 pkt_len = new_len; 1169 } 1170 err = tcp_fragment(sk, skb, pkt_len, mss, GFP_ATOMIC); 1171 if (err < 0) 1172 return err; 1173 } 1174 1175 return in_sack; 1176 } 1177 1178 /* Mark the given newly-SACKed range as such, adjusting counters and hints. */ 1179 static u8 tcp_sacktag_one(struct sock *sk, 1180 struct tcp_sacktag_state *state, u8 sacked, 1181 u32 start_seq, u32 end_seq, 1182 int dup_sack, int pcount, 1183 const struct skb_mstamp *xmit_time) 1184 { 1185 struct tcp_sock *tp = tcp_sk(sk); 1186 int fack_count = state->fack_count; 1187 1188 /* Account D-SACK for retransmitted packet. */ 1189 if (dup_sack && (sacked & TCPCB_RETRANS)) { 1190 if (tp->undo_marker && tp->undo_retrans && 1191 after(end_seq, tp->undo_marker)) 1192 tp->undo_retrans--; 1193 if (sacked & TCPCB_SACKED_ACKED) 1194 state->reord = min(fack_count, state->reord); 1195 } 1196 1197 /* Nothing to do; acked frame is about to be dropped (was ACKed). */ 1198 if (!after(end_seq, tp->snd_una)) 1199 return sacked; 1200 1201 if (!(sacked & TCPCB_SACKED_ACKED)) { 1202 if (sacked & TCPCB_SACKED_RETRANS) { 1203 /* If the segment is not tagged as lost, 1204 * we do not clear RETRANS, believing 1205 * that retransmission is still in flight. 1206 */ 1207 if (sacked & TCPCB_LOST) { 1208 sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS); 1209 tp->lost_out -= pcount; 1210 tp->retrans_out -= pcount; 1211 } 1212 } else { 1213 if (!(sacked & TCPCB_RETRANS)) { 1214 /* New sack for not retransmitted frame, 1215 * which was in hole. It is reordering. 1216 */ 1217 if (before(start_seq, 1218 tcp_highest_sack_seq(tp))) 1219 state->reord = min(fack_count, 1220 state->reord); 1221 if (!after(end_seq, tp->high_seq)) 1222 state->flag |= FLAG_ORIG_SACK_ACKED; 1223 /* Pick the earliest sequence sacked for RTT */ 1224 if (state->rtt_us < 0) { 1225 struct skb_mstamp now; 1226 1227 skb_mstamp_get(&now); 1228 state->rtt_us = skb_mstamp_us_delta(&now, 1229 xmit_time); 1230 } 1231 } 1232 1233 if (sacked & TCPCB_LOST) { 1234 sacked &= ~TCPCB_LOST; 1235 tp->lost_out -= pcount; 1236 } 1237 } 1238 1239 sacked |= TCPCB_SACKED_ACKED; 1240 state->flag |= FLAG_DATA_SACKED; 1241 tp->sacked_out += pcount; 1242 1243 fack_count += pcount; 1244 1245 /* Lost marker hint past SACKed? Tweak RFC3517 cnt */ 1246 if (!tcp_is_fack(tp) && (tp->lost_skb_hint != NULL) && 1247 before(start_seq, TCP_SKB_CB(tp->lost_skb_hint)->seq)) 1248 tp->lost_cnt_hint += pcount; 1249 1250 if (fack_count > tp->fackets_out) 1251 tp->fackets_out = fack_count; 1252 } 1253 1254 /* D-SACK. We can detect redundant retransmission in S|R and plain R 1255 * frames and clear it. undo_retrans is decreased above, L|R frames 1256 * are accounted above as well. 1257 */ 1258 if (dup_sack && (sacked & TCPCB_SACKED_RETRANS)) { 1259 sacked &= ~TCPCB_SACKED_RETRANS; 1260 tp->retrans_out -= pcount; 1261 } 1262 1263 return sacked; 1264 } 1265 1266 /* Shift newly-SACKed bytes from this skb to the immediately previous 1267 * already-SACKed sk_buff. Mark the newly-SACKed bytes as such. 1268 */ 1269 static bool tcp_shifted_skb(struct sock *sk, struct sk_buff *skb, 1270 struct tcp_sacktag_state *state, 1271 unsigned int pcount, int shifted, int mss, 1272 bool dup_sack) 1273 { 1274 struct tcp_sock *tp = tcp_sk(sk); 1275 struct sk_buff *prev = tcp_write_queue_prev(sk, skb); 1276 u32 start_seq = TCP_SKB_CB(skb)->seq; /* start of newly-SACKed */ 1277 u32 end_seq = start_seq + shifted; /* end of newly-SACKed */ 1278 1279 BUG_ON(!pcount); 1280 1281 /* Adjust counters and hints for the newly sacked sequence 1282 * range but discard the return value since prev is already 1283 * marked. We must tag the range first because the seq 1284 * advancement below implicitly advances 1285 * tcp_highest_sack_seq() when skb is highest_sack. 1286 */ 1287 tcp_sacktag_one(sk, state, TCP_SKB_CB(skb)->sacked, 1288 start_seq, end_seq, dup_sack, pcount, 1289 &skb->skb_mstamp); 1290 1291 if (skb == tp->lost_skb_hint) 1292 tp->lost_cnt_hint += pcount; 1293 1294 TCP_SKB_CB(prev)->end_seq += shifted; 1295 TCP_SKB_CB(skb)->seq += shifted; 1296 1297 skb_shinfo(prev)->gso_segs += pcount; 1298 BUG_ON(skb_shinfo(skb)->gso_segs < pcount); 1299 skb_shinfo(skb)->gso_segs -= pcount; 1300 1301 /* When we're adding to gso_segs == 1, gso_size will be zero, 1302 * in theory this shouldn't be necessary but as long as DSACK 1303 * code can come after this skb later on it's better to keep 1304 * setting gso_size to something. 1305 */ 1306 if (!skb_shinfo(prev)->gso_size) { 1307 skb_shinfo(prev)->gso_size = mss; 1308 skb_shinfo(prev)->gso_type = sk->sk_gso_type; 1309 } 1310 1311 /* CHECKME: To clear or not to clear? Mimics normal skb currently */ 1312 if (skb_shinfo(skb)->gso_segs <= 1) { 1313 skb_shinfo(skb)->gso_size = 0; 1314 skb_shinfo(skb)->gso_type = 0; 1315 } 1316 1317 /* Difference in this won't matter, both ACKed by the same cumul. ACK */ 1318 TCP_SKB_CB(prev)->sacked |= (TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS); 1319 1320 if (skb->len > 0) { 1321 BUG_ON(!tcp_skb_pcount(skb)); 1322 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTED); 1323 return false; 1324 } 1325 1326 /* Whole SKB was eaten :-) */ 1327 1328 if (skb == tp->retransmit_skb_hint) 1329 tp->retransmit_skb_hint = prev; 1330 if (skb == tp->lost_skb_hint) { 1331 tp->lost_skb_hint = prev; 1332 tp->lost_cnt_hint -= tcp_skb_pcount(prev); 1333 } 1334 1335 TCP_SKB_CB(prev)->tcp_flags |= TCP_SKB_CB(skb)->tcp_flags; 1336 if (TCP_SKB_CB(skb)->tcp_flags & TCPHDR_FIN) 1337 TCP_SKB_CB(prev)->end_seq++; 1338 1339 if (skb == tcp_highest_sack(sk)) 1340 tcp_advance_highest_sack(sk, skb); 1341 1342 tcp_unlink_write_queue(skb, sk); 1343 sk_wmem_free_skb(sk, skb); 1344 1345 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKMERGED); 1346 1347 return true; 1348 } 1349 1350 /* I wish gso_size would have a bit more sane initialization than 1351 * something-or-zero which complicates things 1352 */ 1353 static int tcp_skb_seglen(const struct sk_buff *skb) 1354 { 1355 return tcp_skb_pcount(skb) == 1 ? skb->len : tcp_skb_mss(skb); 1356 } 1357 1358 /* Shifting pages past head area doesn't work */ 1359 static int skb_can_shift(const struct sk_buff *skb) 1360 { 1361 return !skb_headlen(skb) && skb_is_nonlinear(skb); 1362 } 1363 1364 /* Try collapsing SACK blocks spanning across multiple skbs to a single 1365 * skb. 1366 */ 1367 static struct sk_buff *tcp_shift_skb_data(struct sock *sk, struct sk_buff *skb, 1368 struct tcp_sacktag_state *state, 1369 u32 start_seq, u32 end_seq, 1370 bool dup_sack) 1371 { 1372 struct tcp_sock *tp = tcp_sk(sk); 1373 struct sk_buff *prev; 1374 int mss; 1375 int pcount = 0; 1376 int len; 1377 int in_sack; 1378 1379 if (!sk_can_gso(sk)) 1380 goto fallback; 1381 1382 /* Normally R but no L won't result in plain S */ 1383 if (!dup_sack && 1384 (TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_RETRANS)) == TCPCB_SACKED_RETRANS) 1385 goto fallback; 1386 if (!skb_can_shift(skb)) 1387 goto fallback; 1388 /* This frame is about to be dropped (was ACKed). */ 1389 if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) 1390 goto fallback; 1391 1392 /* Can only happen with delayed DSACK + discard craziness */ 1393 if (unlikely(skb == tcp_write_queue_head(sk))) 1394 goto fallback; 1395 prev = tcp_write_queue_prev(sk, skb); 1396 1397 if ((TCP_SKB_CB(prev)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED) 1398 goto fallback; 1399 1400 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) && 1401 !before(end_seq, TCP_SKB_CB(skb)->end_seq); 1402 1403 if (in_sack) { 1404 len = skb->len; 1405 pcount = tcp_skb_pcount(skb); 1406 mss = tcp_skb_seglen(skb); 1407 1408 /* TODO: Fix DSACKs to not fragment already SACKed and we can 1409 * drop this restriction as unnecessary 1410 */ 1411 if (mss != tcp_skb_seglen(prev)) 1412 goto fallback; 1413 } else { 1414 if (!after(TCP_SKB_CB(skb)->end_seq, start_seq)) 1415 goto noop; 1416 /* CHECKME: This is non-MSS split case only?, this will 1417 * cause skipped skbs due to advancing loop btw, original 1418 * has that feature too 1419 */ 1420 if (tcp_skb_pcount(skb) <= 1) 1421 goto noop; 1422 1423 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq); 1424 if (!in_sack) { 1425 /* TODO: head merge to next could be attempted here 1426 * if (!after(TCP_SKB_CB(skb)->end_seq, end_seq)), 1427 * though it might not be worth of the additional hassle 1428 * 1429 * ...we can probably just fallback to what was done 1430 * previously. We could try merging non-SACKed ones 1431 * as well but it probably isn't going to buy off 1432 * because later SACKs might again split them, and 1433 * it would make skb timestamp tracking considerably 1434 * harder problem. 1435 */ 1436 goto fallback; 1437 } 1438 1439 len = end_seq - TCP_SKB_CB(skb)->seq; 1440 BUG_ON(len < 0); 1441 BUG_ON(len > skb->len); 1442 1443 /* MSS boundaries should be honoured or else pcount will 1444 * severely break even though it makes things bit trickier. 1445 * Optimize common case to avoid most of the divides 1446 */ 1447 mss = tcp_skb_mss(skb); 1448 1449 /* TODO: Fix DSACKs to not fragment already SACKed and we can 1450 * drop this restriction as unnecessary 1451 */ 1452 if (mss != tcp_skb_seglen(prev)) 1453 goto fallback; 1454 1455 if (len == mss) { 1456 pcount = 1; 1457 } else if (len < mss) { 1458 goto noop; 1459 } else { 1460 pcount = len / mss; 1461 len = pcount * mss; 1462 } 1463 } 1464 1465 /* tcp_sacktag_one() won't SACK-tag ranges below snd_una */ 1466 if (!after(TCP_SKB_CB(skb)->seq + len, tp->snd_una)) 1467 goto fallback; 1468 1469 if (!skb_shift(prev, skb, len)) 1470 goto fallback; 1471 if (!tcp_shifted_skb(sk, skb, state, pcount, len, mss, dup_sack)) 1472 goto out; 1473 1474 /* Hole filled allows collapsing with the next as well, this is very 1475 * useful when hole on every nth skb pattern happens 1476 */ 1477 if (prev == tcp_write_queue_tail(sk)) 1478 goto out; 1479 skb = tcp_write_queue_next(sk, prev); 1480 1481 if (!skb_can_shift(skb) || 1482 (skb == tcp_send_head(sk)) || 1483 ((TCP_SKB_CB(skb)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED) || 1484 (mss != tcp_skb_seglen(skb))) 1485 goto out; 1486 1487 len = skb->len; 1488 if (skb_shift(prev, skb, len)) { 1489 pcount += tcp_skb_pcount(skb); 1490 tcp_shifted_skb(sk, skb, state, tcp_skb_pcount(skb), len, mss, 0); 1491 } 1492 1493 out: 1494 state->fack_count += pcount; 1495 return prev; 1496 1497 noop: 1498 return skb; 1499 1500 fallback: 1501 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTFALLBACK); 1502 return NULL; 1503 } 1504 1505 static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk, 1506 struct tcp_sack_block *next_dup, 1507 struct tcp_sacktag_state *state, 1508 u32 start_seq, u32 end_seq, 1509 bool dup_sack_in) 1510 { 1511 struct tcp_sock *tp = tcp_sk(sk); 1512 struct sk_buff *tmp; 1513 1514 tcp_for_write_queue_from(skb, sk) { 1515 int in_sack = 0; 1516 bool dup_sack = dup_sack_in; 1517 1518 if (skb == tcp_send_head(sk)) 1519 break; 1520 1521 /* queue is in-order => we can short-circuit the walk early */ 1522 if (!before(TCP_SKB_CB(skb)->seq, end_seq)) 1523 break; 1524 1525 if ((next_dup != NULL) && 1526 before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) { 1527 in_sack = tcp_match_skb_to_sack(sk, skb, 1528 next_dup->start_seq, 1529 next_dup->end_seq); 1530 if (in_sack > 0) 1531 dup_sack = true; 1532 } 1533 1534 /* skb reference here is a bit tricky to get right, since 1535 * shifting can eat and free both this skb and the next, 1536 * so not even _safe variant of the loop is enough. 1537 */ 1538 if (in_sack <= 0) { 1539 tmp = tcp_shift_skb_data(sk, skb, state, 1540 start_seq, end_seq, dup_sack); 1541 if (tmp != NULL) { 1542 if (tmp != skb) { 1543 skb = tmp; 1544 continue; 1545 } 1546 1547 in_sack = 0; 1548 } else { 1549 in_sack = tcp_match_skb_to_sack(sk, skb, 1550 start_seq, 1551 end_seq); 1552 } 1553 } 1554 1555 if (unlikely(in_sack < 0)) 1556 break; 1557 1558 if (in_sack) { 1559 TCP_SKB_CB(skb)->sacked = 1560 tcp_sacktag_one(sk, 1561 state, 1562 TCP_SKB_CB(skb)->sacked, 1563 TCP_SKB_CB(skb)->seq, 1564 TCP_SKB_CB(skb)->end_seq, 1565 dup_sack, 1566 tcp_skb_pcount(skb), 1567 &skb->skb_mstamp); 1568 1569 if (!before(TCP_SKB_CB(skb)->seq, 1570 tcp_highest_sack_seq(tp))) 1571 tcp_advance_highest_sack(sk, skb); 1572 } 1573 1574 state->fack_count += tcp_skb_pcount(skb); 1575 } 1576 return skb; 1577 } 1578 1579 /* Avoid all extra work that is being done by sacktag while walking in 1580 * a normal way 1581 */ 1582 static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk, 1583 struct tcp_sacktag_state *state, 1584 u32 skip_to_seq) 1585 { 1586 tcp_for_write_queue_from(skb, sk) { 1587 if (skb == tcp_send_head(sk)) 1588 break; 1589 1590 if (after(TCP_SKB_CB(skb)->end_seq, skip_to_seq)) 1591 break; 1592 1593 state->fack_count += tcp_skb_pcount(skb); 1594 } 1595 return skb; 1596 } 1597 1598 static struct sk_buff *tcp_maybe_skipping_dsack(struct sk_buff *skb, 1599 struct sock *sk, 1600 struct tcp_sack_block *next_dup, 1601 struct tcp_sacktag_state *state, 1602 u32 skip_to_seq) 1603 { 1604 if (next_dup == NULL) 1605 return skb; 1606 1607 if (before(next_dup->start_seq, skip_to_seq)) { 1608 skb = tcp_sacktag_skip(skb, sk, state, next_dup->start_seq); 1609 skb = tcp_sacktag_walk(skb, sk, NULL, state, 1610 next_dup->start_seq, next_dup->end_seq, 1611 1); 1612 } 1613 1614 return skb; 1615 } 1616 1617 static int tcp_sack_cache_ok(const struct tcp_sock *tp, const struct tcp_sack_block *cache) 1618 { 1619 return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache); 1620 } 1621 1622 static int 1623 tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb, 1624 u32 prior_snd_una, long *sack_rtt_us) 1625 { 1626 struct tcp_sock *tp = tcp_sk(sk); 1627 const unsigned char *ptr = (skb_transport_header(ack_skb) + 1628 TCP_SKB_CB(ack_skb)->sacked); 1629 struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2); 1630 struct tcp_sack_block sp[TCP_NUM_SACKS]; 1631 struct tcp_sack_block *cache; 1632 struct tcp_sacktag_state state; 1633 struct sk_buff *skb; 1634 int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3); 1635 int used_sacks; 1636 bool found_dup_sack = false; 1637 int i, j; 1638 int first_sack_index; 1639 1640 state.flag = 0; 1641 state.reord = tp->packets_out; 1642 state.rtt_us = -1L; 1643 1644 if (!tp->sacked_out) { 1645 if (WARN_ON(tp->fackets_out)) 1646 tp->fackets_out = 0; 1647 tcp_highest_sack_reset(sk); 1648 } 1649 1650 found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire, 1651 num_sacks, prior_snd_una); 1652 if (found_dup_sack) 1653 state.flag |= FLAG_DSACKING_ACK; 1654 1655 /* Eliminate too old ACKs, but take into 1656 * account more or less fresh ones, they can 1657 * contain valid SACK info. 1658 */ 1659 if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window)) 1660 return 0; 1661 1662 if (!tp->packets_out) 1663 goto out; 1664 1665 used_sacks = 0; 1666 first_sack_index = 0; 1667 for (i = 0; i < num_sacks; i++) { 1668 bool dup_sack = !i && found_dup_sack; 1669 1670 sp[used_sacks].start_seq = get_unaligned_be32(&sp_wire[i].start_seq); 1671 sp[used_sacks].end_seq = get_unaligned_be32(&sp_wire[i].end_seq); 1672 1673 if (!tcp_is_sackblock_valid(tp, dup_sack, 1674 sp[used_sacks].start_seq, 1675 sp[used_sacks].end_seq)) { 1676 int mib_idx; 1677 1678 if (dup_sack) { 1679 if (!tp->undo_marker) 1680 mib_idx = LINUX_MIB_TCPDSACKIGNOREDNOUNDO; 1681 else 1682 mib_idx = LINUX_MIB_TCPDSACKIGNOREDOLD; 1683 } else { 1684 /* Don't count olds caused by ACK reordering */ 1685 if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) && 1686 !after(sp[used_sacks].end_seq, tp->snd_una)) 1687 continue; 1688 mib_idx = LINUX_MIB_TCPSACKDISCARD; 1689 } 1690 1691 NET_INC_STATS_BH(sock_net(sk), mib_idx); 1692 if (i == 0) 1693 first_sack_index = -1; 1694 continue; 1695 } 1696 1697 /* Ignore very old stuff early */ 1698 if (!after(sp[used_sacks].end_seq, prior_snd_una)) 1699 continue; 1700 1701 used_sacks++; 1702 } 1703 1704 /* order SACK blocks to allow in order walk of the retrans queue */ 1705 for (i = used_sacks - 1; i > 0; i--) { 1706 for (j = 0; j < i; j++) { 1707 if (after(sp[j].start_seq, sp[j + 1].start_seq)) { 1708 swap(sp[j], sp[j + 1]); 1709 1710 /* Track where the first SACK block goes to */ 1711 if (j == first_sack_index) 1712 first_sack_index = j + 1; 1713 } 1714 } 1715 } 1716 1717 skb = tcp_write_queue_head(sk); 1718 state.fack_count = 0; 1719 i = 0; 1720 1721 if (!tp->sacked_out) { 1722 /* It's already past, so skip checking against it */ 1723 cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache); 1724 } else { 1725 cache = tp->recv_sack_cache; 1726 /* Skip empty blocks in at head of the cache */ 1727 while (tcp_sack_cache_ok(tp, cache) && !cache->start_seq && 1728 !cache->end_seq) 1729 cache++; 1730 } 1731 1732 while (i < used_sacks) { 1733 u32 start_seq = sp[i].start_seq; 1734 u32 end_seq = sp[i].end_seq; 1735 bool dup_sack = (found_dup_sack && (i == first_sack_index)); 1736 struct tcp_sack_block *next_dup = NULL; 1737 1738 if (found_dup_sack && ((i + 1) == first_sack_index)) 1739 next_dup = &sp[i + 1]; 1740 1741 /* Skip too early cached blocks */ 1742 while (tcp_sack_cache_ok(tp, cache) && 1743 !before(start_seq, cache->end_seq)) 1744 cache++; 1745 1746 /* Can skip some work by looking recv_sack_cache? */ 1747 if (tcp_sack_cache_ok(tp, cache) && !dup_sack && 1748 after(end_seq, cache->start_seq)) { 1749 1750 /* Head todo? */ 1751 if (before(start_seq, cache->start_seq)) { 1752 skb = tcp_sacktag_skip(skb, sk, &state, 1753 start_seq); 1754 skb = tcp_sacktag_walk(skb, sk, next_dup, 1755 &state, 1756 start_seq, 1757 cache->start_seq, 1758 dup_sack); 1759 } 1760 1761 /* Rest of the block already fully processed? */ 1762 if (!after(end_seq, cache->end_seq)) 1763 goto advance_sp; 1764 1765 skb = tcp_maybe_skipping_dsack(skb, sk, next_dup, 1766 &state, 1767 cache->end_seq); 1768 1769 /* ...tail remains todo... */ 1770 if (tcp_highest_sack_seq(tp) == cache->end_seq) { 1771 /* ...but better entrypoint exists! */ 1772 skb = tcp_highest_sack(sk); 1773 if (skb == NULL) 1774 break; 1775 state.fack_count = tp->fackets_out; 1776 cache++; 1777 goto walk; 1778 } 1779 1780 skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq); 1781 /* Check overlap against next cached too (past this one already) */ 1782 cache++; 1783 continue; 1784 } 1785 1786 if (!before(start_seq, tcp_highest_sack_seq(tp))) { 1787 skb = tcp_highest_sack(sk); 1788 if (skb == NULL) 1789 break; 1790 state.fack_count = tp->fackets_out; 1791 } 1792 skb = tcp_sacktag_skip(skb, sk, &state, start_seq); 1793 1794 walk: 1795 skb = tcp_sacktag_walk(skb, sk, next_dup, &state, 1796 start_seq, end_seq, dup_sack); 1797 1798 advance_sp: 1799 i++; 1800 } 1801 1802 /* Clear the head of the cache sack blocks so we can skip it next time */ 1803 for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) { 1804 tp->recv_sack_cache[i].start_seq = 0; 1805 tp->recv_sack_cache[i].end_seq = 0; 1806 } 1807 for (j = 0; j < used_sacks; j++) 1808 tp->recv_sack_cache[i++] = sp[j]; 1809 1810 tcp_mark_lost_retrans(sk); 1811 1812 tcp_verify_left_out(tp); 1813 1814 if ((state.reord < tp->fackets_out) && 1815 ((inet_csk(sk)->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker)) 1816 tcp_update_reordering(sk, tp->fackets_out - state.reord, 0); 1817 1818 out: 1819 1820 #if FASTRETRANS_DEBUG > 0 1821 WARN_ON((int)tp->sacked_out < 0); 1822 WARN_ON((int)tp->lost_out < 0); 1823 WARN_ON((int)tp->retrans_out < 0); 1824 WARN_ON((int)tcp_packets_in_flight(tp) < 0); 1825 #endif 1826 *sack_rtt_us = state.rtt_us; 1827 return state.flag; 1828 } 1829 1830 /* Limits sacked_out so that sum with lost_out isn't ever larger than 1831 * packets_out. Returns false if sacked_out adjustement wasn't necessary. 1832 */ 1833 static bool tcp_limit_reno_sacked(struct tcp_sock *tp) 1834 { 1835 u32 holes; 1836 1837 holes = max(tp->lost_out, 1U); 1838 holes = min(holes, tp->packets_out); 1839 1840 if ((tp->sacked_out + holes) > tp->packets_out) { 1841 tp->sacked_out = tp->packets_out - holes; 1842 return true; 1843 } 1844 return false; 1845 } 1846 1847 /* If we receive more dupacks than we expected counting segments 1848 * in assumption of absent reordering, interpret this as reordering. 1849 * The only another reason could be bug in receiver TCP. 1850 */ 1851 static void tcp_check_reno_reordering(struct sock *sk, const int addend) 1852 { 1853 struct tcp_sock *tp = tcp_sk(sk); 1854 if (tcp_limit_reno_sacked(tp)) 1855 tcp_update_reordering(sk, tp->packets_out + addend, 0); 1856 } 1857 1858 /* Emulate SACKs for SACKless connection: account for a new dupack. */ 1859 1860 static void tcp_add_reno_sack(struct sock *sk) 1861 { 1862 struct tcp_sock *tp = tcp_sk(sk); 1863 tp->sacked_out++; 1864 tcp_check_reno_reordering(sk, 0); 1865 tcp_verify_left_out(tp); 1866 } 1867 1868 /* Account for ACK, ACKing some data in Reno Recovery phase. */ 1869 1870 static void tcp_remove_reno_sacks(struct sock *sk, int acked) 1871 { 1872 struct tcp_sock *tp = tcp_sk(sk); 1873 1874 if (acked > 0) { 1875 /* One ACK acked hole. The rest eat duplicate ACKs. */ 1876 if (acked - 1 >= tp->sacked_out) 1877 tp->sacked_out = 0; 1878 else 1879 tp->sacked_out -= acked - 1; 1880 } 1881 tcp_check_reno_reordering(sk, acked); 1882 tcp_verify_left_out(tp); 1883 } 1884 1885 static inline void tcp_reset_reno_sack(struct tcp_sock *tp) 1886 { 1887 tp->sacked_out = 0; 1888 } 1889 1890 static void tcp_clear_retrans_partial(struct tcp_sock *tp) 1891 { 1892 tp->retrans_out = 0; 1893 tp->lost_out = 0; 1894 1895 tp->undo_marker = 0; 1896 tp->undo_retrans = 0; 1897 } 1898 1899 void tcp_clear_retrans(struct tcp_sock *tp) 1900 { 1901 tcp_clear_retrans_partial(tp); 1902 1903 tp->fackets_out = 0; 1904 tp->sacked_out = 0; 1905 } 1906 1907 /* Enter Loss state. If "how" is not zero, forget all SACK information 1908 * and reset tags completely, otherwise preserve SACKs. If receiver 1909 * dropped its ofo queue, we will know this due to reneging detection. 1910 */ 1911 void tcp_enter_loss(struct sock *sk, int how) 1912 { 1913 const struct inet_connection_sock *icsk = inet_csk(sk); 1914 struct tcp_sock *tp = tcp_sk(sk); 1915 struct sk_buff *skb; 1916 bool new_recovery = false; 1917 1918 /* Reduce ssthresh if it has not yet been made inside this window. */ 1919 if (icsk->icsk_ca_state <= TCP_CA_Disorder || 1920 !after(tp->high_seq, tp->snd_una) || 1921 (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) { 1922 new_recovery = true; 1923 tp->prior_ssthresh = tcp_current_ssthresh(sk); 1924 tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk); 1925 tcp_ca_event(sk, CA_EVENT_LOSS); 1926 } 1927 tp->snd_cwnd = 1; 1928 tp->snd_cwnd_cnt = 0; 1929 tp->snd_cwnd_stamp = tcp_time_stamp; 1930 1931 tcp_clear_retrans_partial(tp); 1932 1933 if (tcp_is_reno(tp)) 1934 tcp_reset_reno_sack(tp); 1935 1936 tp->undo_marker = tp->snd_una; 1937 if (how) { 1938 tp->sacked_out = 0; 1939 tp->fackets_out = 0; 1940 } 1941 tcp_clear_all_retrans_hints(tp); 1942 1943 tcp_for_write_queue(skb, sk) { 1944 if (skb == tcp_send_head(sk)) 1945 break; 1946 1947 if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) 1948 tp->undo_marker = 0; 1949 1950 TCP_SKB_CB(skb)->sacked &= (~TCPCB_TAGBITS)|TCPCB_SACKED_ACKED; 1951 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_ACKED) || how) { 1952 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_ACKED; 1953 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1954 tp->lost_out += tcp_skb_pcount(skb); 1955 tp->retransmit_high = TCP_SKB_CB(skb)->end_seq; 1956 } 1957 } 1958 tcp_verify_left_out(tp); 1959 1960 /* Timeout in disordered state after receiving substantial DUPACKs 1961 * suggests that the degree of reordering is over-estimated. 1962 */ 1963 if (icsk->icsk_ca_state <= TCP_CA_Disorder && 1964 tp->sacked_out >= sysctl_tcp_reordering) 1965 tp->reordering = min_t(unsigned int, tp->reordering, 1966 sysctl_tcp_reordering); 1967 tcp_set_ca_state(sk, TCP_CA_Loss); 1968 tp->high_seq = tp->snd_nxt; 1969 TCP_ECN_queue_cwr(tp); 1970 1971 /* F-RTO RFC5682 sec 3.1 step 1: retransmit SND.UNA if no previous 1972 * loss recovery is underway except recurring timeout(s) on 1973 * the same SND.UNA (sec 3.2). Disable F-RTO on path MTU probing 1974 */ 1975 tp->frto = sysctl_tcp_frto && 1976 (new_recovery || icsk->icsk_retransmits) && 1977 !inet_csk(sk)->icsk_mtup.probe_size; 1978 } 1979 1980 /* If ACK arrived pointing to a remembered SACK, it means that our 1981 * remembered SACKs do not reflect real state of receiver i.e. 1982 * receiver _host_ is heavily congested (or buggy). 1983 * 1984 * Do processing similar to RTO timeout. 1985 */ 1986 static bool tcp_check_sack_reneging(struct sock *sk, int flag) 1987 { 1988 if (flag & FLAG_SACK_RENEGING) { 1989 struct inet_connection_sock *icsk = inet_csk(sk); 1990 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPSACKRENEGING); 1991 1992 tcp_enter_loss(sk, 1); 1993 icsk->icsk_retransmits++; 1994 tcp_retransmit_skb(sk, tcp_write_queue_head(sk)); 1995 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, 1996 icsk->icsk_rto, TCP_RTO_MAX); 1997 return true; 1998 } 1999 return false; 2000 } 2001 2002 static inline int tcp_fackets_out(const struct tcp_sock *tp) 2003 { 2004 return tcp_is_reno(tp) ? tp->sacked_out + 1 : tp->fackets_out; 2005 } 2006 2007 /* Heurestics to calculate number of duplicate ACKs. There's no dupACKs 2008 * counter when SACK is enabled (without SACK, sacked_out is used for 2009 * that purpose). 2010 * 2011 * Instead, with FACK TCP uses fackets_out that includes both SACKed 2012 * segments up to the highest received SACK block so far and holes in 2013 * between them. 2014 * 2015 * With reordering, holes may still be in flight, so RFC3517 recovery 2016 * uses pure sacked_out (total number of SACKed segments) even though 2017 * it violates the RFC that uses duplicate ACKs, often these are equal 2018 * but when e.g. out-of-window ACKs or packet duplication occurs, 2019 * they differ. Since neither occurs due to loss, TCP should really 2020 * ignore them. 2021 */ 2022 static inline int tcp_dupack_heuristics(const struct tcp_sock *tp) 2023 { 2024 return tcp_is_fack(tp) ? tp->fackets_out : tp->sacked_out + 1; 2025 } 2026 2027 static bool tcp_pause_early_retransmit(struct sock *sk, int flag) 2028 { 2029 struct tcp_sock *tp = tcp_sk(sk); 2030 unsigned long delay; 2031 2032 /* Delay early retransmit and entering fast recovery for 2033 * max(RTT/4, 2msec) unless ack has ECE mark, no RTT samples 2034 * available, or RTO is scheduled to fire first. 2035 */ 2036 if (sysctl_tcp_early_retrans < 2 || sysctl_tcp_early_retrans > 3 || 2037 (flag & FLAG_ECE) || !tp->srtt_us) 2038 return false; 2039 2040 delay = max(usecs_to_jiffies(tp->srtt_us >> 5), 2041 msecs_to_jiffies(2)); 2042 2043 if (!time_after(inet_csk(sk)->icsk_timeout, (jiffies + delay))) 2044 return false; 2045 2046 inet_csk_reset_xmit_timer(sk, ICSK_TIME_EARLY_RETRANS, delay, 2047 TCP_RTO_MAX); 2048 return true; 2049 } 2050 2051 /* Linux NewReno/SACK/FACK/ECN state machine. 2052 * -------------------------------------- 2053 * 2054 * "Open" Normal state, no dubious events, fast path. 2055 * "Disorder" In all the respects it is "Open", 2056 * but requires a bit more attention. It is entered when 2057 * we see some SACKs or dupacks. It is split of "Open" 2058 * mainly to move some processing from fast path to slow one. 2059 * "CWR" CWND was reduced due to some Congestion Notification event. 2060 * It can be ECN, ICMP source quench, local device congestion. 2061 * "Recovery" CWND was reduced, we are fast-retransmitting. 2062 * "Loss" CWND was reduced due to RTO timeout or SACK reneging. 2063 * 2064 * tcp_fastretrans_alert() is entered: 2065 * - each incoming ACK, if state is not "Open" 2066 * - when arrived ACK is unusual, namely: 2067 * * SACK 2068 * * Duplicate ACK. 2069 * * ECN ECE. 2070 * 2071 * Counting packets in flight is pretty simple. 2072 * 2073 * in_flight = packets_out - left_out + retrans_out 2074 * 2075 * packets_out is SND.NXT-SND.UNA counted in packets. 2076 * 2077 * retrans_out is number of retransmitted segments. 2078 * 2079 * left_out is number of segments left network, but not ACKed yet. 2080 * 2081 * left_out = sacked_out + lost_out 2082 * 2083 * sacked_out: Packets, which arrived to receiver out of order 2084 * and hence not ACKed. With SACKs this number is simply 2085 * amount of SACKed data. Even without SACKs 2086 * it is easy to give pretty reliable estimate of this number, 2087 * counting duplicate ACKs. 2088 * 2089 * lost_out: Packets lost by network. TCP has no explicit 2090 * "loss notification" feedback from network (for now). 2091 * It means that this number can be only _guessed_. 2092 * Actually, it is the heuristics to predict lossage that 2093 * distinguishes different algorithms. 2094 * 2095 * F.e. after RTO, when all the queue is considered as lost, 2096 * lost_out = packets_out and in_flight = retrans_out. 2097 * 2098 * Essentially, we have now two algorithms counting 2099 * lost packets. 2100 * 2101 * FACK: It is the simplest heuristics. As soon as we decided 2102 * that something is lost, we decide that _all_ not SACKed 2103 * packets until the most forward SACK are lost. I.e. 2104 * lost_out = fackets_out - sacked_out and left_out = fackets_out. 2105 * It is absolutely correct estimate, if network does not reorder 2106 * packets. And it loses any connection to reality when reordering 2107 * takes place. We use FACK by default until reordering 2108 * is suspected on the path to this destination. 2109 * 2110 * NewReno: when Recovery is entered, we assume that one segment 2111 * is lost (classic Reno). While we are in Recovery and 2112 * a partial ACK arrives, we assume that one more packet 2113 * is lost (NewReno). This heuristics are the same in NewReno 2114 * and SACK. 2115 * 2116 * Imagine, that's all! Forget about all this shamanism about CWND inflation 2117 * deflation etc. CWND is real congestion window, never inflated, changes 2118 * only according to classic VJ rules. 2119 * 2120 * Really tricky (and requiring careful tuning) part of algorithm 2121 * is hidden in functions tcp_time_to_recover() and tcp_xmit_retransmit_queue(). 2122 * The first determines the moment _when_ we should reduce CWND and, 2123 * hence, slow down forward transmission. In fact, it determines the moment 2124 * when we decide that hole is caused by loss, rather than by a reorder. 2125 * 2126 * tcp_xmit_retransmit_queue() decides, _what_ we should retransmit to fill 2127 * holes, caused by lost packets. 2128 * 2129 * And the most logically complicated part of algorithm is undo 2130 * heuristics. We detect false retransmits due to both too early 2131 * fast retransmit (reordering) and underestimated RTO, analyzing 2132 * timestamps and D-SACKs. When we detect that some segments were 2133 * retransmitted by mistake and CWND reduction was wrong, we undo 2134 * window reduction and abort recovery phase. This logic is hidden 2135 * inside several functions named tcp_try_undo_<something>. 2136 */ 2137 2138 /* This function decides, when we should leave Disordered state 2139 * and enter Recovery phase, reducing congestion window. 2140 * 2141 * Main question: may we further continue forward transmission 2142 * with the same cwnd? 2143 */ 2144 static bool tcp_time_to_recover(struct sock *sk, int flag) 2145 { 2146 struct tcp_sock *tp = tcp_sk(sk); 2147 __u32 packets_out; 2148 2149 /* Trick#1: The loss is proven. */ 2150 if (tp->lost_out) 2151 return true; 2152 2153 /* Not-A-Trick#2 : Classic rule... */ 2154 if (tcp_dupack_heuristics(tp) > tp->reordering) 2155 return true; 2156 2157 /* Trick#4: It is still not OK... But will it be useful to delay 2158 * recovery more? 2159 */ 2160 packets_out = tp->packets_out; 2161 if (packets_out <= tp->reordering && 2162 tp->sacked_out >= max_t(__u32, packets_out/2, sysctl_tcp_reordering) && 2163 !tcp_may_send_now(sk)) { 2164 /* We have nothing to send. This connection is limited 2165 * either by receiver window or by application. 2166 */ 2167 return true; 2168 } 2169 2170 /* If a thin stream is detected, retransmit after first 2171 * received dupack. Employ only if SACK is supported in order 2172 * to avoid possible corner-case series of spurious retransmissions 2173 * Use only if there are no unsent data. 2174 */ 2175 if ((tp->thin_dupack || sysctl_tcp_thin_dupack) && 2176 tcp_stream_is_thin(tp) && tcp_dupack_heuristics(tp) > 1 && 2177 tcp_is_sack(tp) && !tcp_send_head(sk)) 2178 return true; 2179 2180 /* Trick#6: TCP early retransmit, per RFC5827. To avoid spurious 2181 * retransmissions due to small network reorderings, we implement 2182 * Mitigation A.3 in the RFC and delay the retransmission for a short 2183 * interval if appropriate. 2184 */ 2185 if (tp->do_early_retrans && !tp->retrans_out && tp->sacked_out && 2186 (tp->packets_out >= (tp->sacked_out + 1) && tp->packets_out < 4) && 2187 !tcp_may_send_now(sk)) 2188 return !tcp_pause_early_retransmit(sk, flag); 2189 2190 return false; 2191 } 2192 2193 /* Detect loss in event "A" above by marking head of queue up as lost. 2194 * For FACK or non-SACK(Reno) senders, the first "packets" number of segments 2195 * are considered lost. For RFC3517 SACK, a segment is considered lost if it 2196 * has at least tp->reordering SACKed seqments above it; "packets" refers to 2197 * the maximum SACKed segments to pass before reaching this limit. 2198 */ 2199 static void tcp_mark_head_lost(struct sock *sk, int packets, int mark_head) 2200 { 2201 struct tcp_sock *tp = tcp_sk(sk); 2202 struct sk_buff *skb; 2203 int cnt, oldcnt; 2204 int err; 2205 unsigned int mss; 2206 /* Use SACK to deduce losses of new sequences sent during recovery */ 2207 const u32 loss_high = tcp_is_sack(tp) ? tp->snd_nxt : tp->high_seq; 2208 2209 WARN_ON(packets > tp->packets_out); 2210 if (tp->lost_skb_hint) { 2211 skb = tp->lost_skb_hint; 2212 cnt = tp->lost_cnt_hint; 2213 /* Head already handled? */ 2214 if (mark_head && skb != tcp_write_queue_head(sk)) 2215 return; 2216 } else { 2217 skb = tcp_write_queue_head(sk); 2218 cnt = 0; 2219 } 2220 2221 tcp_for_write_queue_from(skb, sk) { 2222 if (skb == tcp_send_head(sk)) 2223 break; 2224 /* TODO: do this better */ 2225 /* this is not the most efficient way to do this... */ 2226 tp->lost_skb_hint = skb; 2227 tp->lost_cnt_hint = cnt; 2228 2229 if (after(TCP_SKB_CB(skb)->end_seq, loss_high)) 2230 break; 2231 2232 oldcnt = cnt; 2233 if (tcp_is_fack(tp) || tcp_is_reno(tp) || 2234 (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) 2235 cnt += tcp_skb_pcount(skb); 2236 2237 if (cnt > packets) { 2238 if ((tcp_is_sack(tp) && !tcp_is_fack(tp)) || 2239 (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED) || 2240 (oldcnt >= packets)) 2241 break; 2242 2243 mss = skb_shinfo(skb)->gso_size; 2244 err = tcp_fragment(sk, skb, (packets - oldcnt) * mss, 2245 mss, GFP_ATOMIC); 2246 if (err < 0) 2247 break; 2248 cnt = packets; 2249 } 2250 2251 tcp_skb_mark_lost(tp, skb); 2252 2253 if (mark_head) 2254 break; 2255 } 2256 tcp_verify_left_out(tp); 2257 } 2258 2259 /* Account newly detected lost packet(s) */ 2260 2261 static void tcp_update_scoreboard(struct sock *sk, int fast_rexmit) 2262 { 2263 struct tcp_sock *tp = tcp_sk(sk); 2264 2265 if (tcp_is_reno(tp)) { 2266 tcp_mark_head_lost(sk, 1, 1); 2267 } else if (tcp_is_fack(tp)) { 2268 int lost = tp->fackets_out - tp->reordering; 2269 if (lost <= 0) 2270 lost = 1; 2271 tcp_mark_head_lost(sk, lost, 0); 2272 } else { 2273 int sacked_upto = tp->sacked_out - tp->reordering; 2274 if (sacked_upto >= 0) 2275 tcp_mark_head_lost(sk, sacked_upto, 0); 2276 else if (fast_rexmit) 2277 tcp_mark_head_lost(sk, 1, 1); 2278 } 2279 } 2280 2281 /* CWND moderation, preventing bursts due to too big ACKs 2282 * in dubious situations. 2283 */ 2284 static inline void tcp_moderate_cwnd(struct tcp_sock *tp) 2285 { 2286 tp->snd_cwnd = min(tp->snd_cwnd, 2287 tcp_packets_in_flight(tp) + tcp_max_burst(tp)); 2288 tp->snd_cwnd_stamp = tcp_time_stamp; 2289 } 2290 2291 /* Nothing was retransmitted or returned timestamp is less 2292 * than timestamp of the first retransmission. 2293 */ 2294 static inline bool tcp_packet_delayed(const struct tcp_sock *tp) 2295 { 2296 return !tp->retrans_stamp || 2297 (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 2298 before(tp->rx_opt.rcv_tsecr, tp->retrans_stamp)); 2299 } 2300 2301 /* Undo procedures. */ 2302 2303 #if FASTRETRANS_DEBUG > 1 2304 static void DBGUNDO(struct sock *sk, const char *msg) 2305 { 2306 struct tcp_sock *tp = tcp_sk(sk); 2307 struct inet_sock *inet = inet_sk(sk); 2308 2309 if (sk->sk_family == AF_INET) { 2310 pr_debug("Undo %s %pI4/%u c%u l%u ss%u/%u p%u\n", 2311 msg, 2312 &inet->inet_daddr, ntohs(inet->inet_dport), 2313 tp->snd_cwnd, tcp_left_out(tp), 2314 tp->snd_ssthresh, tp->prior_ssthresh, 2315 tp->packets_out); 2316 } 2317 #if IS_ENABLED(CONFIG_IPV6) 2318 else if (sk->sk_family == AF_INET6) { 2319 struct ipv6_pinfo *np = inet6_sk(sk); 2320 pr_debug("Undo %s %pI6/%u c%u l%u ss%u/%u p%u\n", 2321 msg, 2322 &np->daddr, ntohs(inet->inet_dport), 2323 tp->snd_cwnd, tcp_left_out(tp), 2324 tp->snd_ssthresh, tp->prior_ssthresh, 2325 tp->packets_out); 2326 } 2327 #endif 2328 } 2329 #else 2330 #define DBGUNDO(x...) do { } while (0) 2331 #endif 2332 2333 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss) 2334 { 2335 struct tcp_sock *tp = tcp_sk(sk); 2336 2337 if (unmark_loss) { 2338 struct sk_buff *skb; 2339 2340 tcp_for_write_queue(skb, sk) { 2341 if (skb == tcp_send_head(sk)) 2342 break; 2343 TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST; 2344 } 2345 tp->lost_out = 0; 2346 tcp_clear_all_retrans_hints(tp); 2347 } 2348 2349 if (tp->prior_ssthresh) { 2350 const struct inet_connection_sock *icsk = inet_csk(sk); 2351 2352 if (icsk->icsk_ca_ops->undo_cwnd) 2353 tp->snd_cwnd = icsk->icsk_ca_ops->undo_cwnd(sk); 2354 else 2355 tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh << 1); 2356 2357 if (tp->prior_ssthresh > tp->snd_ssthresh) { 2358 tp->snd_ssthresh = tp->prior_ssthresh; 2359 TCP_ECN_withdraw_cwr(tp); 2360 } 2361 } else { 2362 tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh); 2363 } 2364 tp->snd_cwnd_stamp = tcp_time_stamp; 2365 tp->undo_marker = 0; 2366 } 2367 2368 static inline bool tcp_may_undo(const struct tcp_sock *tp) 2369 { 2370 return tp->undo_marker && (!tp->undo_retrans || tcp_packet_delayed(tp)); 2371 } 2372 2373 /* People celebrate: "We love our President!" */ 2374 static bool tcp_try_undo_recovery(struct sock *sk) 2375 { 2376 struct tcp_sock *tp = tcp_sk(sk); 2377 2378 if (tcp_may_undo(tp)) { 2379 int mib_idx; 2380 2381 /* Happy end! We did not retransmit anything 2382 * or our original transmission succeeded. 2383 */ 2384 DBGUNDO(sk, inet_csk(sk)->icsk_ca_state == TCP_CA_Loss ? "loss" : "retrans"); 2385 tcp_undo_cwnd_reduction(sk, false); 2386 if (inet_csk(sk)->icsk_ca_state == TCP_CA_Loss) 2387 mib_idx = LINUX_MIB_TCPLOSSUNDO; 2388 else 2389 mib_idx = LINUX_MIB_TCPFULLUNDO; 2390 2391 NET_INC_STATS_BH(sock_net(sk), mib_idx); 2392 } 2393 if (tp->snd_una == tp->high_seq && tcp_is_reno(tp)) { 2394 /* Hold old state until something *above* high_seq 2395 * is ACKed. For Reno it is MUST to prevent false 2396 * fast retransmits (RFC2582). SACK TCP is safe. */ 2397 tcp_moderate_cwnd(tp); 2398 return true; 2399 } 2400 tcp_set_ca_state(sk, TCP_CA_Open); 2401 return false; 2402 } 2403 2404 /* Try to undo cwnd reduction, because D-SACKs acked all retransmitted data */ 2405 static bool tcp_try_undo_dsack(struct sock *sk) 2406 { 2407 struct tcp_sock *tp = tcp_sk(sk); 2408 2409 if (tp->undo_marker && !tp->undo_retrans) { 2410 DBGUNDO(sk, "D-SACK"); 2411 tcp_undo_cwnd_reduction(sk, false); 2412 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKUNDO); 2413 return true; 2414 } 2415 return false; 2416 } 2417 2418 /* We can clear retrans_stamp when there are no retransmissions in the 2419 * window. It would seem that it is trivially available for us in 2420 * tp->retrans_out, however, that kind of assumptions doesn't consider 2421 * what will happen if errors occur when sending retransmission for the 2422 * second time. ...It could the that such segment has only 2423 * TCPCB_EVER_RETRANS set at the present time. It seems that checking 2424 * the head skb is enough except for some reneging corner cases that 2425 * are not worth the effort. 2426 * 2427 * Main reason for all this complexity is the fact that connection dying 2428 * time now depends on the validity of the retrans_stamp, in particular, 2429 * that successive retransmissions of a segment must not advance 2430 * retrans_stamp under any conditions. 2431 */ 2432 static bool tcp_any_retrans_done(const struct sock *sk) 2433 { 2434 const struct tcp_sock *tp = tcp_sk(sk); 2435 struct sk_buff *skb; 2436 2437 if (tp->retrans_out) 2438 return true; 2439 2440 skb = tcp_write_queue_head(sk); 2441 if (unlikely(skb && TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS)) 2442 return true; 2443 2444 return false; 2445 } 2446 2447 /* Undo during loss recovery after partial ACK or using F-RTO. */ 2448 static bool tcp_try_undo_loss(struct sock *sk, bool frto_undo) 2449 { 2450 struct tcp_sock *tp = tcp_sk(sk); 2451 2452 if (frto_undo || tcp_may_undo(tp)) { 2453 tcp_undo_cwnd_reduction(sk, true); 2454 2455 DBGUNDO(sk, "partial loss"); 2456 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSSUNDO); 2457 if (frto_undo) 2458 NET_INC_STATS_BH(sock_net(sk), 2459 LINUX_MIB_TCPSPURIOUSRTOS); 2460 inet_csk(sk)->icsk_retransmits = 0; 2461 if (frto_undo || tcp_is_sack(tp)) 2462 tcp_set_ca_state(sk, TCP_CA_Open); 2463 return true; 2464 } 2465 return false; 2466 } 2467 2468 /* The cwnd reduction in CWR and Recovery use the PRR algorithm 2469 * https://datatracker.ietf.org/doc/draft-ietf-tcpm-proportional-rate-reduction/ 2470 * It computes the number of packets to send (sndcnt) based on packets newly 2471 * delivered: 2472 * 1) If the packets in flight is larger than ssthresh, PRR spreads the 2473 * cwnd reductions across a full RTT. 2474 * 2) If packets in flight is lower than ssthresh (such as due to excess 2475 * losses and/or application stalls), do not perform any further cwnd 2476 * reductions, but instead slow start up to ssthresh. 2477 */ 2478 static void tcp_init_cwnd_reduction(struct sock *sk, const bool set_ssthresh) 2479 { 2480 struct tcp_sock *tp = tcp_sk(sk); 2481 2482 tp->high_seq = tp->snd_nxt; 2483 tp->tlp_high_seq = 0; 2484 tp->snd_cwnd_cnt = 0; 2485 tp->prior_cwnd = tp->snd_cwnd; 2486 tp->prr_delivered = 0; 2487 tp->prr_out = 0; 2488 if (set_ssthresh) 2489 tp->snd_ssthresh = inet_csk(sk)->icsk_ca_ops->ssthresh(sk); 2490 TCP_ECN_queue_cwr(tp); 2491 } 2492 2493 static void tcp_cwnd_reduction(struct sock *sk, const int prior_unsacked, 2494 int fast_rexmit) 2495 { 2496 struct tcp_sock *tp = tcp_sk(sk); 2497 int sndcnt = 0; 2498 int delta = tp->snd_ssthresh - tcp_packets_in_flight(tp); 2499 int newly_acked_sacked = prior_unsacked - 2500 (tp->packets_out - tp->sacked_out); 2501 2502 tp->prr_delivered += newly_acked_sacked; 2503 if (tcp_packets_in_flight(tp) > tp->snd_ssthresh) { 2504 u64 dividend = (u64)tp->snd_ssthresh * tp->prr_delivered + 2505 tp->prior_cwnd - 1; 2506 sndcnt = div_u64(dividend, tp->prior_cwnd) - tp->prr_out; 2507 } else { 2508 sndcnt = min_t(int, delta, 2509 max_t(int, tp->prr_delivered - tp->prr_out, 2510 newly_acked_sacked) + 1); 2511 } 2512 2513 sndcnt = max(sndcnt, (fast_rexmit ? 1 : 0)); 2514 tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt; 2515 } 2516 2517 static inline void tcp_end_cwnd_reduction(struct sock *sk) 2518 { 2519 struct tcp_sock *tp = tcp_sk(sk); 2520 2521 /* Reset cwnd to ssthresh in CWR or Recovery (unless it's undone) */ 2522 if (inet_csk(sk)->icsk_ca_state == TCP_CA_CWR || 2523 (tp->undo_marker && tp->snd_ssthresh < TCP_INFINITE_SSTHRESH)) { 2524 tp->snd_cwnd = tp->snd_ssthresh; 2525 tp->snd_cwnd_stamp = tcp_time_stamp; 2526 } 2527 tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR); 2528 } 2529 2530 /* Enter CWR state. Disable cwnd undo since congestion is proven with ECN */ 2531 void tcp_enter_cwr(struct sock *sk, const int set_ssthresh) 2532 { 2533 struct tcp_sock *tp = tcp_sk(sk); 2534 2535 tp->prior_ssthresh = 0; 2536 if (inet_csk(sk)->icsk_ca_state < TCP_CA_CWR) { 2537 tp->undo_marker = 0; 2538 tcp_init_cwnd_reduction(sk, set_ssthresh); 2539 tcp_set_ca_state(sk, TCP_CA_CWR); 2540 } 2541 } 2542 2543 static void tcp_try_keep_open(struct sock *sk) 2544 { 2545 struct tcp_sock *tp = tcp_sk(sk); 2546 int state = TCP_CA_Open; 2547 2548 if (tcp_left_out(tp) || tcp_any_retrans_done(sk)) 2549 state = TCP_CA_Disorder; 2550 2551 if (inet_csk(sk)->icsk_ca_state != state) { 2552 tcp_set_ca_state(sk, state); 2553 tp->high_seq = tp->snd_nxt; 2554 } 2555 } 2556 2557 static void tcp_try_to_open(struct sock *sk, int flag, const int prior_unsacked) 2558 { 2559 struct tcp_sock *tp = tcp_sk(sk); 2560 2561 tcp_verify_left_out(tp); 2562 2563 if (!tcp_any_retrans_done(sk)) 2564 tp->retrans_stamp = 0; 2565 2566 if (flag & FLAG_ECE) 2567 tcp_enter_cwr(sk, 1); 2568 2569 if (inet_csk(sk)->icsk_ca_state != TCP_CA_CWR) { 2570 tcp_try_keep_open(sk); 2571 } else { 2572 tcp_cwnd_reduction(sk, prior_unsacked, 0); 2573 } 2574 } 2575 2576 static void tcp_mtup_probe_failed(struct sock *sk) 2577 { 2578 struct inet_connection_sock *icsk = inet_csk(sk); 2579 2580 icsk->icsk_mtup.search_high = icsk->icsk_mtup.probe_size - 1; 2581 icsk->icsk_mtup.probe_size = 0; 2582 } 2583 2584 static void tcp_mtup_probe_success(struct sock *sk) 2585 { 2586 struct tcp_sock *tp = tcp_sk(sk); 2587 struct inet_connection_sock *icsk = inet_csk(sk); 2588 2589 /* FIXME: breaks with very large cwnd */ 2590 tp->prior_ssthresh = tcp_current_ssthresh(sk); 2591 tp->snd_cwnd = tp->snd_cwnd * 2592 tcp_mss_to_mtu(sk, tp->mss_cache) / 2593 icsk->icsk_mtup.probe_size; 2594 tp->snd_cwnd_cnt = 0; 2595 tp->snd_cwnd_stamp = tcp_time_stamp; 2596 tp->snd_ssthresh = tcp_current_ssthresh(sk); 2597 2598 icsk->icsk_mtup.search_low = icsk->icsk_mtup.probe_size; 2599 icsk->icsk_mtup.probe_size = 0; 2600 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 2601 } 2602 2603 /* Do a simple retransmit without using the backoff mechanisms in 2604 * tcp_timer. This is used for path mtu discovery. 2605 * The socket is already locked here. 2606 */ 2607 void tcp_simple_retransmit(struct sock *sk) 2608 { 2609 const struct inet_connection_sock *icsk = inet_csk(sk); 2610 struct tcp_sock *tp = tcp_sk(sk); 2611 struct sk_buff *skb; 2612 unsigned int mss = tcp_current_mss(sk); 2613 u32 prior_lost = tp->lost_out; 2614 2615 tcp_for_write_queue(skb, sk) { 2616 if (skb == tcp_send_head(sk)) 2617 break; 2618 if (tcp_skb_seglen(skb) > mss && 2619 !(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) { 2620 if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) { 2621 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS; 2622 tp->retrans_out -= tcp_skb_pcount(skb); 2623 } 2624 tcp_skb_mark_lost_uncond_verify(tp, skb); 2625 } 2626 } 2627 2628 tcp_clear_retrans_hints_partial(tp); 2629 2630 if (prior_lost == tp->lost_out) 2631 return; 2632 2633 if (tcp_is_reno(tp)) 2634 tcp_limit_reno_sacked(tp); 2635 2636 tcp_verify_left_out(tp); 2637 2638 /* Don't muck with the congestion window here. 2639 * Reason is that we do not increase amount of _data_ 2640 * in network, but units changed and effective 2641 * cwnd/ssthresh really reduced now. 2642 */ 2643 if (icsk->icsk_ca_state != TCP_CA_Loss) { 2644 tp->high_seq = tp->snd_nxt; 2645 tp->snd_ssthresh = tcp_current_ssthresh(sk); 2646 tp->prior_ssthresh = 0; 2647 tp->undo_marker = 0; 2648 tcp_set_ca_state(sk, TCP_CA_Loss); 2649 } 2650 tcp_xmit_retransmit_queue(sk); 2651 } 2652 EXPORT_SYMBOL(tcp_simple_retransmit); 2653 2654 static void tcp_enter_recovery(struct sock *sk, bool ece_ack) 2655 { 2656 struct tcp_sock *tp = tcp_sk(sk); 2657 int mib_idx; 2658 2659 if (tcp_is_reno(tp)) 2660 mib_idx = LINUX_MIB_TCPRENORECOVERY; 2661 else 2662 mib_idx = LINUX_MIB_TCPSACKRECOVERY; 2663 2664 NET_INC_STATS_BH(sock_net(sk), mib_idx); 2665 2666 tp->prior_ssthresh = 0; 2667 tp->undo_marker = tp->snd_una; 2668 tp->undo_retrans = tp->retrans_out; 2669 2670 if (inet_csk(sk)->icsk_ca_state < TCP_CA_CWR) { 2671 if (!ece_ack) 2672 tp->prior_ssthresh = tcp_current_ssthresh(sk); 2673 tcp_init_cwnd_reduction(sk, true); 2674 } 2675 tcp_set_ca_state(sk, TCP_CA_Recovery); 2676 } 2677 2678 /* Process an ACK in CA_Loss state. Move to CA_Open if lost data are 2679 * recovered or spurious. Otherwise retransmits more on partial ACKs. 2680 */ 2681 static void tcp_process_loss(struct sock *sk, int flag, bool is_dupack) 2682 { 2683 struct inet_connection_sock *icsk = inet_csk(sk); 2684 struct tcp_sock *tp = tcp_sk(sk); 2685 bool recovered = !before(tp->snd_una, tp->high_seq); 2686 2687 if (tp->frto) { /* F-RTO RFC5682 sec 3.1 (sack enhanced version). */ 2688 /* Step 3.b. A timeout is spurious if not all data are 2689 * lost, i.e., never-retransmitted data are (s)acked. 2690 */ 2691 if (tcp_try_undo_loss(sk, flag & FLAG_ORIG_SACK_ACKED)) 2692 return; 2693 2694 if (after(tp->snd_nxt, tp->high_seq) && 2695 (flag & FLAG_DATA_SACKED || is_dupack)) { 2696 tp->frto = 0; /* Loss was real: 2nd part of step 3.a */ 2697 } else if (flag & FLAG_SND_UNA_ADVANCED && !recovered) { 2698 tp->high_seq = tp->snd_nxt; 2699 __tcp_push_pending_frames(sk, tcp_current_mss(sk), 2700 TCP_NAGLE_OFF); 2701 if (after(tp->snd_nxt, tp->high_seq)) 2702 return; /* Step 2.b */ 2703 tp->frto = 0; 2704 } 2705 } 2706 2707 if (recovered) { 2708 /* F-RTO RFC5682 sec 3.1 step 2.a and 1st part of step 3.a */ 2709 icsk->icsk_retransmits = 0; 2710 tcp_try_undo_recovery(sk); 2711 return; 2712 } 2713 if (flag & FLAG_DATA_ACKED) 2714 icsk->icsk_retransmits = 0; 2715 if (tcp_is_reno(tp)) { 2716 /* A Reno DUPACK means new data in F-RTO step 2.b above are 2717 * delivered. Lower inflight to clock out (re)tranmissions. 2718 */ 2719 if (after(tp->snd_nxt, tp->high_seq) && is_dupack) 2720 tcp_add_reno_sack(sk); 2721 else if (flag & FLAG_SND_UNA_ADVANCED) 2722 tcp_reset_reno_sack(tp); 2723 } 2724 if (tcp_try_undo_loss(sk, false)) 2725 return; 2726 tcp_xmit_retransmit_queue(sk); 2727 } 2728 2729 /* Undo during fast recovery after partial ACK. */ 2730 static bool tcp_try_undo_partial(struct sock *sk, const int acked, 2731 const int prior_unsacked) 2732 { 2733 struct tcp_sock *tp = tcp_sk(sk); 2734 2735 if (tp->undo_marker && tcp_packet_delayed(tp)) { 2736 /* Plain luck! Hole if filled with delayed 2737 * packet, rather than with a retransmit. 2738 */ 2739 tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1); 2740 2741 /* We are getting evidence that the reordering degree is higher 2742 * than we realized. If there are no retransmits out then we 2743 * can undo. Otherwise we clock out new packets but do not 2744 * mark more packets lost or retransmit more. 2745 */ 2746 if (tp->retrans_out) { 2747 tcp_cwnd_reduction(sk, prior_unsacked, 0); 2748 return true; 2749 } 2750 2751 if (!tcp_any_retrans_done(sk)) 2752 tp->retrans_stamp = 0; 2753 2754 DBGUNDO(sk, "partial recovery"); 2755 tcp_undo_cwnd_reduction(sk, true); 2756 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO); 2757 tcp_try_keep_open(sk); 2758 return true; 2759 } 2760 return false; 2761 } 2762 2763 /* Process an event, which can update packets-in-flight not trivially. 2764 * Main goal of this function is to calculate new estimate for left_out, 2765 * taking into account both packets sitting in receiver's buffer and 2766 * packets lost by network. 2767 * 2768 * Besides that it does CWND reduction, when packet loss is detected 2769 * and changes state of machine. 2770 * 2771 * It does _not_ decide what to send, it is made in function 2772 * tcp_xmit_retransmit_queue(). 2773 */ 2774 static void tcp_fastretrans_alert(struct sock *sk, const int acked, 2775 const int prior_unsacked, 2776 bool is_dupack, int flag) 2777 { 2778 struct inet_connection_sock *icsk = inet_csk(sk); 2779 struct tcp_sock *tp = tcp_sk(sk); 2780 bool do_lost = is_dupack || ((flag & FLAG_DATA_SACKED) && 2781 (tcp_fackets_out(tp) > tp->reordering)); 2782 int fast_rexmit = 0; 2783 2784 if (WARN_ON(!tp->packets_out && tp->sacked_out)) 2785 tp->sacked_out = 0; 2786 if (WARN_ON(!tp->sacked_out && tp->fackets_out)) 2787 tp->fackets_out = 0; 2788 2789 /* Now state machine starts. 2790 * A. ECE, hence prohibit cwnd undoing, the reduction is required. */ 2791 if (flag & FLAG_ECE) 2792 tp->prior_ssthresh = 0; 2793 2794 /* B. In all the states check for reneging SACKs. */ 2795 if (tcp_check_sack_reneging(sk, flag)) 2796 return; 2797 2798 /* C. Check consistency of the current state. */ 2799 tcp_verify_left_out(tp); 2800 2801 /* D. Check state exit conditions. State can be terminated 2802 * when high_seq is ACKed. */ 2803 if (icsk->icsk_ca_state == TCP_CA_Open) { 2804 WARN_ON(tp->retrans_out != 0); 2805 tp->retrans_stamp = 0; 2806 } else if (!before(tp->snd_una, tp->high_seq)) { 2807 switch (icsk->icsk_ca_state) { 2808 case TCP_CA_CWR: 2809 /* CWR is to be held something *above* high_seq 2810 * is ACKed for CWR bit to reach receiver. */ 2811 if (tp->snd_una != tp->high_seq) { 2812 tcp_end_cwnd_reduction(sk); 2813 tcp_set_ca_state(sk, TCP_CA_Open); 2814 } 2815 break; 2816 2817 case TCP_CA_Recovery: 2818 if (tcp_is_reno(tp)) 2819 tcp_reset_reno_sack(tp); 2820 if (tcp_try_undo_recovery(sk)) 2821 return; 2822 tcp_end_cwnd_reduction(sk); 2823 break; 2824 } 2825 } 2826 2827 /* E. Process state. */ 2828 switch (icsk->icsk_ca_state) { 2829 case TCP_CA_Recovery: 2830 if (!(flag & FLAG_SND_UNA_ADVANCED)) { 2831 if (tcp_is_reno(tp) && is_dupack) 2832 tcp_add_reno_sack(sk); 2833 } else { 2834 if (tcp_try_undo_partial(sk, acked, prior_unsacked)) 2835 return; 2836 /* Partial ACK arrived. Force fast retransmit. */ 2837 do_lost = tcp_is_reno(tp) || 2838 tcp_fackets_out(tp) > tp->reordering; 2839 } 2840 if (tcp_try_undo_dsack(sk)) { 2841 tcp_try_keep_open(sk); 2842 return; 2843 } 2844 break; 2845 case TCP_CA_Loss: 2846 tcp_process_loss(sk, flag, is_dupack); 2847 if (icsk->icsk_ca_state != TCP_CA_Open) 2848 return; 2849 /* Fall through to processing in Open state. */ 2850 default: 2851 if (tcp_is_reno(tp)) { 2852 if (flag & FLAG_SND_UNA_ADVANCED) 2853 tcp_reset_reno_sack(tp); 2854 if (is_dupack) 2855 tcp_add_reno_sack(sk); 2856 } 2857 2858 if (icsk->icsk_ca_state <= TCP_CA_Disorder) 2859 tcp_try_undo_dsack(sk); 2860 2861 if (!tcp_time_to_recover(sk, flag)) { 2862 tcp_try_to_open(sk, flag, prior_unsacked); 2863 return; 2864 } 2865 2866 /* MTU probe failure: don't reduce cwnd */ 2867 if (icsk->icsk_ca_state < TCP_CA_CWR && 2868 icsk->icsk_mtup.probe_size && 2869 tp->snd_una == tp->mtu_probe.probe_seq_start) { 2870 tcp_mtup_probe_failed(sk); 2871 /* Restores the reduction we did in tcp_mtup_probe() */ 2872 tp->snd_cwnd++; 2873 tcp_simple_retransmit(sk); 2874 return; 2875 } 2876 2877 /* Otherwise enter Recovery state */ 2878 tcp_enter_recovery(sk, (flag & FLAG_ECE)); 2879 fast_rexmit = 1; 2880 } 2881 2882 if (do_lost) 2883 tcp_update_scoreboard(sk, fast_rexmit); 2884 tcp_cwnd_reduction(sk, prior_unsacked, fast_rexmit); 2885 tcp_xmit_retransmit_queue(sk); 2886 } 2887 2888 static inline bool tcp_ack_update_rtt(struct sock *sk, const int flag, 2889 long seq_rtt_us, long sack_rtt_us) 2890 { 2891 const struct tcp_sock *tp = tcp_sk(sk); 2892 2893 /* Prefer RTT measured from ACK's timing to TS-ECR. This is because 2894 * broken middle-boxes or peers may corrupt TS-ECR fields. But 2895 * Karn's algorithm forbids taking RTT if some retransmitted data 2896 * is acked (RFC6298). 2897 */ 2898 if (flag & FLAG_RETRANS_DATA_ACKED) 2899 seq_rtt_us = -1L; 2900 2901 if (seq_rtt_us < 0) 2902 seq_rtt_us = sack_rtt_us; 2903 2904 /* RTTM Rule: A TSecr value received in a segment is used to 2905 * update the averaged RTT measurement only if the segment 2906 * acknowledges some new data, i.e., only if it advances the 2907 * left edge of the send window. 2908 * See draft-ietf-tcplw-high-performance-00, section 3.3. 2909 */ 2910 if (seq_rtt_us < 0 && tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 2911 flag & FLAG_ACKED) 2912 seq_rtt_us = jiffies_to_usecs(tcp_time_stamp - tp->rx_opt.rcv_tsecr); 2913 2914 if (seq_rtt_us < 0) 2915 return false; 2916 2917 tcp_rtt_estimator(sk, seq_rtt_us); 2918 tcp_set_rto(sk); 2919 2920 /* RFC6298: only reset backoff on valid RTT measurement. */ 2921 inet_csk(sk)->icsk_backoff = 0; 2922 return true; 2923 } 2924 2925 /* Compute time elapsed between (last) SYNACK and the ACK completing 3WHS. */ 2926 static void tcp_synack_rtt_meas(struct sock *sk, const u32 synack_stamp) 2927 { 2928 struct tcp_sock *tp = tcp_sk(sk); 2929 long seq_rtt_us = -1L; 2930 2931 if (synack_stamp && !tp->total_retrans) 2932 seq_rtt_us = jiffies_to_usecs(tcp_time_stamp - synack_stamp); 2933 2934 /* If the ACK acks both the SYNACK and the (Fast Open'd) data packets 2935 * sent in SYN_RECV, SYNACK RTT is the smooth RTT computed in tcp_ack() 2936 */ 2937 if (!tp->srtt_us) 2938 tcp_ack_update_rtt(sk, FLAG_SYN_ACKED, seq_rtt_us, -1L); 2939 } 2940 2941 static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 acked) 2942 { 2943 const struct inet_connection_sock *icsk = inet_csk(sk); 2944 2945 icsk->icsk_ca_ops->cong_avoid(sk, ack, acked); 2946 tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp; 2947 } 2948 2949 /* Restart timer after forward progress on connection. 2950 * RFC2988 recommends to restart timer to now+rto. 2951 */ 2952 void tcp_rearm_rto(struct sock *sk) 2953 { 2954 const struct inet_connection_sock *icsk = inet_csk(sk); 2955 struct tcp_sock *tp = tcp_sk(sk); 2956 2957 /* If the retrans timer is currently being used by Fast Open 2958 * for SYN-ACK retrans purpose, stay put. 2959 */ 2960 if (tp->fastopen_rsk) 2961 return; 2962 2963 if (!tp->packets_out) { 2964 inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS); 2965 } else { 2966 u32 rto = inet_csk(sk)->icsk_rto; 2967 /* Offset the time elapsed after installing regular RTO */ 2968 if (icsk->icsk_pending == ICSK_TIME_EARLY_RETRANS || 2969 icsk->icsk_pending == ICSK_TIME_LOSS_PROBE) { 2970 struct sk_buff *skb = tcp_write_queue_head(sk); 2971 const u32 rto_time_stamp = TCP_SKB_CB(skb)->when + rto; 2972 s32 delta = (s32)(rto_time_stamp - tcp_time_stamp); 2973 /* delta may not be positive if the socket is locked 2974 * when the retrans timer fires and is rescheduled. 2975 */ 2976 if (delta > 0) 2977 rto = delta; 2978 } 2979 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, rto, 2980 TCP_RTO_MAX); 2981 } 2982 } 2983 2984 /* This function is called when the delayed ER timer fires. TCP enters 2985 * fast recovery and performs fast-retransmit. 2986 */ 2987 void tcp_resume_early_retransmit(struct sock *sk) 2988 { 2989 struct tcp_sock *tp = tcp_sk(sk); 2990 2991 tcp_rearm_rto(sk); 2992 2993 /* Stop if ER is disabled after the delayed ER timer is scheduled */ 2994 if (!tp->do_early_retrans) 2995 return; 2996 2997 tcp_enter_recovery(sk, false); 2998 tcp_update_scoreboard(sk, 1); 2999 tcp_xmit_retransmit_queue(sk); 3000 } 3001 3002 /* If we get here, the whole TSO packet has not been acked. */ 3003 static u32 tcp_tso_acked(struct sock *sk, struct sk_buff *skb) 3004 { 3005 struct tcp_sock *tp = tcp_sk(sk); 3006 u32 packets_acked; 3007 3008 BUG_ON(!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)); 3009 3010 packets_acked = tcp_skb_pcount(skb); 3011 if (tcp_trim_head(sk, skb, tp->snd_una - TCP_SKB_CB(skb)->seq)) 3012 return 0; 3013 packets_acked -= tcp_skb_pcount(skb); 3014 3015 if (packets_acked) { 3016 BUG_ON(tcp_skb_pcount(skb) == 0); 3017 BUG_ON(!before(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq)); 3018 } 3019 3020 return packets_acked; 3021 } 3022 3023 /* Remove acknowledged frames from the retransmission queue. If our packet 3024 * is before the ack sequence we can discard it as it's confirmed to have 3025 * arrived at the other end. 3026 */ 3027 static int tcp_clean_rtx_queue(struct sock *sk, int prior_fackets, 3028 u32 prior_snd_una, long sack_rtt_us) 3029 { 3030 const struct inet_connection_sock *icsk = inet_csk(sk); 3031 struct skb_mstamp first_ackt, last_ackt, now; 3032 struct tcp_sock *tp = tcp_sk(sk); 3033 u32 prior_sacked = tp->sacked_out; 3034 u32 reord = tp->packets_out; 3035 bool fully_acked = true; 3036 long ca_seq_rtt_us = -1L; 3037 long seq_rtt_us = -1L; 3038 struct sk_buff *skb; 3039 u32 pkts_acked = 0; 3040 bool rtt_update; 3041 int flag = 0; 3042 3043 first_ackt.v64 = 0; 3044 3045 while ((skb = tcp_write_queue_head(sk)) && skb != tcp_send_head(sk)) { 3046 struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 3047 u8 sacked = scb->sacked; 3048 u32 acked_pcount; 3049 3050 /* Determine how many packets and what bytes were acked, tso and else */ 3051 if (after(scb->end_seq, tp->snd_una)) { 3052 if (tcp_skb_pcount(skb) == 1 || 3053 !after(tp->snd_una, scb->seq)) 3054 break; 3055 3056 acked_pcount = tcp_tso_acked(sk, skb); 3057 if (!acked_pcount) 3058 break; 3059 3060 fully_acked = false; 3061 } else { 3062 acked_pcount = tcp_skb_pcount(skb); 3063 } 3064 3065 if (sacked & TCPCB_RETRANS) { 3066 if (sacked & TCPCB_SACKED_RETRANS) 3067 tp->retrans_out -= acked_pcount; 3068 flag |= FLAG_RETRANS_DATA_ACKED; 3069 } else { 3070 last_ackt = skb->skb_mstamp; 3071 WARN_ON_ONCE(last_ackt.v64 == 0); 3072 if (!first_ackt.v64) 3073 first_ackt = last_ackt; 3074 3075 if (!(sacked & TCPCB_SACKED_ACKED)) 3076 reord = min(pkts_acked, reord); 3077 if (!after(scb->end_seq, tp->high_seq)) 3078 flag |= FLAG_ORIG_SACK_ACKED; 3079 } 3080 3081 if (sacked & TCPCB_SACKED_ACKED) 3082 tp->sacked_out -= acked_pcount; 3083 if (sacked & TCPCB_LOST) 3084 tp->lost_out -= acked_pcount; 3085 3086 tp->packets_out -= acked_pcount; 3087 pkts_acked += acked_pcount; 3088 3089 /* Initial outgoing SYN's get put onto the write_queue 3090 * just like anything else we transmit. It is not 3091 * true data, and if we misinform our callers that 3092 * this ACK acks real data, we will erroneously exit 3093 * connection startup slow start one packet too 3094 * quickly. This is severely frowned upon behavior. 3095 */ 3096 if (!(scb->tcp_flags & TCPHDR_SYN)) { 3097 flag |= FLAG_DATA_ACKED; 3098 } else { 3099 flag |= FLAG_SYN_ACKED; 3100 tp->retrans_stamp = 0; 3101 } 3102 3103 if (!fully_acked) 3104 break; 3105 3106 tcp_unlink_write_queue(skb, sk); 3107 sk_wmem_free_skb(sk, skb); 3108 if (skb == tp->retransmit_skb_hint) 3109 tp->retransmit_skb_hint = NULL; 3110 if (skb == tp->lost_skb_hint) 3111 tp->lost_skb_hint = NULL; 3112 } 3113 3114 if (likely(between(tp->snd_up, prior_snd_una, tp->snd_una))) 3115 tp->snd_up = tp->snd_una; 3116 3117 if (skb && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) 3118 flag |= FLAG_SACK_RENEGING; 3119 3120 skb_mstamp_get(&now); 3121 if (first_ackt.v64) { 3122 seq_rtt_us = skb_mstamp_us_delta(&now, &first_ackt); 3123 ca_seq_rtt_us = skb_mstamp_us_delta(&now, &last_ackt); 3124 } 3125 3126 rtt_update = tcp_ack_update_rtt(sk, flag, seq_rtt_us, sack_rtt_us); 3127 3128 if (flag & FLAG_ACKED) { 3129 const struct tcp_congestion_ops *ca_ops 3130 = inet_csk(sk)->icsk_ca_ops; 3131 3132 tcp_rearm_rto(sk); 3133 if (unlikely(icsk->icsk_mtup.probe_size && 3134 !after(tp->mtu_probe.probe_seq_end, tp->snd_una))) { 3135 tcp_mtup_probe_success(sk); 3136 } 3137 3138 if (tcp_is_reno(tp)) { 3139 tcp_remove_reno_sacks(sk, pkts_acked); 3140 } else { 3141 int delta; 3142 3143 /* Non-retransmitted hole got filled? That's reordering */ 3144 if (reord < prior_fackets) 3145 tcp_update_reordering(sk, tp->fackets_out - reord, 0); 3146 3147 delta = tcp_is_fack(tp) ? pkts_acked : 3148 prior_sacked - tp->sacked_out; 3149 tp->lost_cnt_hint -= min(tp->lost_cnt_hint, delta); 3150 } 3151 3152 tp->fackets_out -= min(pkts_acked, tp->fackets_out); 3153 3154 if (ca_ops->pkts_acked) 3155 ca_ops->pkts_acked(sk, pkts_acked, ca_seq_rtt_us); 3156 3157 } else if (skb && rtt_update && sack_rtt_us >= 0 && 3158 sack_rtt_us > skb_mstamp_us_delta(&now, &skb->skb_mstamp)) { 3159 /* Do not re-arm RTO if the sack RTT is measured from data sent 3160 * after when the head was last (re)transmitted. Otherwise the 3161 * timeout may continue to extend in loss recovery. 3162 */ 3163 tcp_rearm_rto(sk); 3164 } 3165 3166 #if FASTRETRANS_DEBUG > 0 3167 WARN_ON((int)tp->sacked_out < 0); 3168 WARN_ON((int)tp->lost_out < 0); 3169 WARN_ON((int)tp->retrans_out < 0); 3170 if (!tp->packets_out && tcp_is_sack(tp)) { 3171 icsk = inet_csk(sk); 3172 if (tp->lost_out) { 3173 pr_debug("Leak l=%u %d\n", 3174 tp->lost_out, icsk->icsk_ca_state); 3175 tp->lost_out = 0; 3176 } 3177 if (tp->sacked_out) { 3178 pr_debug("Leak s=%u %d\n", 3179 tp->sacked_out, icsk->icsk_ca_state); 3180 tp->sacked_out = 0; 3181 } 3182 if (tp->retrans_out) { 3183 pr_debug("Leak r=%u %d\n", 3184 tp->retrans_out, icsk->icsk_ca_state); 3185 tp->retrans_out = 0; 3186 } 3187 } 3188 #endif 3189 return flag; 3190 } 3191 3192 static void tcp_ack_probe(struct sock *sk) 3193 { 3194 const struct tcp_sock *tp = tcp_sk(sk); 3195 struct inet_connection_sock *icsk = inet_csk(sk); 3196 3197 /* Was it a usable window open? */ 3198 3199 if (!after(TCP_SKB_CB(tcp_send_head(sk))->end_seq, tcp_wnd_end(tp))) { 3200 icsk->icsk_backoff = 0; 3201 inet_csk_clear_xmit_timer(sk, ICSK_TIME_PROBE0); 3202 /* Socket must be waked up by subsequent tcp_data_snd_check(). 3203 * This function is not for random using! 3204 */ 3205 } else { 3206 inet_csk_reset_xmit_timer(sk, ICSK_TIME_PROBE0, 3207 min(icsk->icsk_rto << icsk->icsk_backoff, TCP_RTO_MAX), 3208 TCP_RTO_MAX); 3209 } 3210 } 3211 3212 static inline bool tcp_ack_is_dubious(const struct sock *sk, const int flag) 3213 { 3214 return !(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) || 3215 inet_csk(sk)->icsk_ca_state != TCP_CA_Open; 3216 } 3217 3218 /* Decide wheather to run the increase function of congestion control. */ 3219 static inline bool tcp_may_raise_cwnd(const struct sock *sk, const int flag) 3220 { 3221 if (tcp_in_cwnd_reduction(sk)) 3222 return false; 3223 3224 /* If reordering is high then always grow cwnd whenever data is 3225 * delivered regardless of its ordering. Otherwise stay conservative 3226 * and only grow cwnd on in-order delivery (RFC5681). A stretched ACK w/ 3227 * new SACK or ECE mark may first advance cwnd here and later reduce 3228 * cwnd in tcp_fastretrans_alert() based on more states. 3229 */ 3230 if (tcp_sk(sk)->reordering > sysctl_tcp_reordering) 3231 return flag & FLAG_FORWARD_PROGRESS; 3232 3233 return flag & FLAG_DATA_ACKED; 3234 } 3235 3236 /* Check that window update is acceptable. 3237 * The function assumes that snd_una<=ack<=snd_next. 3238 */ 3239 static inline bool tcp_may_update_window(const struct tcp_sock *tp, 3240 const u32 ack, const u32 ack_seq, 3241 const u32 nwin) 3242 { 3243 return after(ack, tp->snd_una) || 3244 after(ack_seq, tp->snd_wl1) || 3245 (ack_seq == tp->snd_wl1 && nwin > tp->snd_wnd); 3246 } 3247 3248 /* Update our send window. 3249 * 3250 * Window update algorithm, described in RFC793/RFC1122 (used in linux-2.2 3251 * and in FreeBSD. NetBSD's one is even worse.) is wrong. 3252 */ 3253 static int tcp_ack_update_window(struct sock *sk, const struct sk_buff *skb, u32 ack, 3254 u32 ack_seq) 3255 { 3256 struct tcp_sock *tp = tcp_sk(sk); 3257 int flag = 0; 3258 u32 nwin = ntohs(tcp_hdr(skb)->window); 3259 3260 if (likely(!tcp_hdr(skb)->syn)) 3261 nwin <<= tp->rx_opt.snd_wscale; 3262 3263 if (tcp_may_update_window(tp, ack, ack_seq, nwin)) { 3264 flag |= FLAG_WIN_UPDATE; 3265 tcp_update_wl(tp, ack_seq); 3266 3267 if (tp->snd_wnd != nwin) { 3268 tp->snd_wnd = nwin; 3269 3270 /* Note, it is the only place, where 3271 * fast path is recovered for sending TCP. 3272 */ 3273 tp->pred_flags = 0; 3274 tcp_fast_path_check(sk); 3275 3276 if (nwin > tp->max_window) { 3277 tp->max_window = nwin; 3278 tcp_sync_mss(sk, inet_csk(sk)->icsk_pmtu_cookie); 3279 } 3280 } 3281 } 3282 3283 tp->snd_una = ack; 3284 3285 return flag; 3286 } 3287 3288 /* RFC 5961 7 [ACK Throttling] */ 3289 static void tcp_send_challenge_ack(struct sock *sk) 3290 { 3291 /* unprotected vars, we dont care of overwrites */ 3292 static u32 challenge_timestamp; 3293 static unsigned int challenge_count; 3294 u32 now = jiffies / HZ; 3295 3296 if (now != challenge_timestamp) { 3297 challenge_timestamp = now; 3298 challenge_count = 0; 3299 } 3300 if (++challenge_count <= sysctl_tcp_challenge_ack_limit) { 3301 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK); 3302 tcp_send_ack(sk); 3303 } 3304 } 3305 3306 static void tcp_store_ts_recent(struct tcp_sock *tp) 3307 { 3308 tp->rx_opt.ts_recent = tp->rx_opt.rcv_tsval; 3309 tp->rx_opt.ts_recent_stamp = get_seconds(); 3310 } 3311 3312 static void tcp_replace_ts_recent(struct tcp_sock *tp, u32 seq) 3313 { 3314 if (tp->rx_opt.saw_tstamp && !after(seq, tp->rcv_wup)) { 3315 /* PAWS bug workaround wrt. ACK frames, the PAWS discard 3316 * extra check below makes sure this can only happen 3317 * for pure ACK frames. -DaveM 3318 * 3319 * Not only, also it occurs for expired timestamps. 3320 */ 3321 3322 if (tcp_paws_check(&tp->rx_opt, 0)) 3323 tcp_store_ts_recent(tp); 3324 } 3325 } 3326 3327 /* This routine deals with acks during a TLP episode. 3328 * Ref: loss detection algorithm in draft-dukkipati-tcpm-tcp-loss-probe. 3329 */ 3330 static void tcp_process_tlp_ack(struct sock *sk, u32 ack, int flag) 3331 { 3332 struct tcp_sock *tp = tcp_sk(sk); 3333 bool is_tlp_dupack = (ack == tp->tlp_high_seq) && 3334 !(flag & (FLAG_SND_UNA_ADVANCED | 3335 FLAG_NOT_DUP | FLAG_DATA_SACKED)); 3336 3337 /* Mark the end of TLP episode on receiving TLP dupack or when 3338 * ack is after tlp_high_seq. 3339 */ 3340 if (is_tlp_dupack) { 3341 tp->tlp_high_seq = 0; 3342 return; 3343 } 3344 3345 if (after(ack, tp->tlp_high_seq)) { 3346 tp->tlp_high_seq = 0; 3347 /* Don't reduce cwnd if DSACK arrives for TLP retrans. */ 3348 if (!(flag & FLAG_DSACKING_ACK)) { 3349 tcp_init_cwnd_reduction(sk, true); 3350 tcp_set_ca_state(sk, TCP_CA_CWR); 3351 tcp_end_cwnd_reduction(sk); 3352 tcp_try_keep_open(sk); 3353 NET_INC_STATS_BH(sock_net(sk), 3354 LINUX_MIB_TCPLOSSPROBERECOVERY); 3355 } 3356 } 3357 } 3358 3359 /* This routine deals with incoming acks, but not outgoing ones. */ 3360 static int tcp_ack(struct sock *sk, const struct sk_buff *skb, int flag) 3361 { 3362 struct inet_connection_sock *icsk = inet_csk(sk); 3363 struct tcp_sock *tp = tcp_sk(sk); 3364 u32 prior_snd_una = tp->snd_una; 3365 u32 ack_seq = TCP_SKB_CB(skb)->seq; 3366 u32 ack = TCP_SKB_CB(skb)->ack_seq; 3367 bool is_dupack = false; 3368 u32 prior_fackets; 3369 int prior_packets = tp->packets_out; 3370 const int prior_unsacked = tp->packets_out - tp->sacked_out; 3371 int acked = 0; /* Number of packets newly acked */ 3372 long sack_rtt_us = -1L; 3373 3374 /* If the ack is older than previous acks 3375 * then we can probably ignore it. 3376 */ 3377 if (before(ack, prior_snd_una)) { 3378 /* RFC 5961 5.2 [Blind Data Injection Attack].[Mitigation] */ 3379 if (before(ack, prior_snd_una - tp->max_window)) { 3380 tcp_send_challenge_ack(sk); 3381 return -1; 3382 } 3383 goto old_ack; 3384 } 3385 3386 /* If the ack includes data we haven't sent yet, discard 3387 * this segment (RFC793 Section 3.9). 3388 */ 3389 if (after(ack, tp->snd_nxt)) 3390 goto invalid_ack; 3391 3392 if (icsk->icsk_pending == ICSK_TIME_EARLY_RETRANS || 3393 icsk->icsk_pending == ICSK_TIME_LOSS_PROBE) 3394 tcp_rearm_rto(sk); 3395 3396 if (after(ack, prior_snd_una)) 3397 flag |= FLAG_SND_UNA_ADVANCED; 3398 3399 prior_fackets = tp->fackets_out; 3400 3401 /* ts_recent update must be made after we are sure that the packet 3402 * is in window. 3403 */ 3404 if (flag & FLAG_UPDATE_TS_RECENT) 3405 tcp_replace_ts_recent(tp, TCP_SKB_CB(skb)->seq); 3406 3407 if (!(flag & FLAG_SLOWPATH) && after(ack, prior_snd_una)) { 3408 /* Window is constant, pure forward advance. 3409 * No more checks are required. 3410 * Note, we use the fact that SND.UNA>=SND.WL2. 3411 */ 3412 tcp_update_wl(tp, ack_seq); 3413 tp->snd_una = ack; 3414 flag |= FLAG_WIN_UPDATE; 3415 3416 tcp_ca_event(sk, CA_EVENT_FAST_ACK); 3417 3418 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPACKS); 3419 } else { 3420 if (ack_seq != TCP_SKB_CB(skb)->end_seq) 3421 flag |= FLAG_DATA; 3422 else 3423 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPUREACKS); 3424 3425 flag |= tcp_ack_update_window(sk, skb, ack, ack_seq); 3426 3427 if (TCP_SKB_CB(skb)->sacked) 3428 flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una, 3429 &sack_rtt_us); 3430 3431 if (TCP_ECN_rcv_ecn_echo(tp, tcp_hdr(skb))) 3432 flag |= FLAG_ECE; 3433 3434 tcp_ca_event(sk, CA_EVENT_SLOW_ACK); 3435 } 3436 3437 /* We passed data and got it acked, remove any soft error 3438 * log. Something worked... 3439 */ 3440 sk->sk_err_soft = 0; 3441 icsk->icsk_probes_out = 0; 3442 tp->rcv_tstamp = tcp_time_stamp; 3443 if (!prior_packets) 3444 goto no_queue; 3445 3446 /* See if we can take anything off of the retransmit queue. */ 3447 acked = tp->packets_out; 3448 flag |= tcp_clean_rtx_queue(sk, prior_fackets, prior_snd_una, 3449 sack_rtt_us); 3450 acked -= tp->packets_out; 3451 3452 /* Advance cwnd if state allows */ 3453 if (tcp_may_raise_cwnd(sk, flag)) 3454 tcp_cong_avoid(sk, ack, acked); 3455 3456 if (tcp_ack_is_dubious(sk, flag)) { 3457 is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP)); 3458 tcp_fastretrans_alert(sk, acked, prior_unsacked, 3459 is_dupack, flag); 3460 } 3461 if (tp->tlp_high_seq) 3462 tcp_process_tlp_ack(sk, ack, flag); 3463 3464 if ((flag & FLAG_FORWARD_PROGRESS) || !(flag & FLAG_NOT_DUP)) { 3465 struct dst_entry *dst = __sk_dst_get(sk); 3466 if (dst) 3467 dst_confirm(dst); 3468 } 3469 3470 if (icsk->icsk_pending == ICSK_TIME_RETRANS) 3471 tcp_schedule_loss_probe(sk); 3472 tcp_update_pacing_rate(sk); 3473 return 1; 3474 3475 no_queue: 3476 /* If data was DSACKed, see if we can undo a cwnd reduction. */ 3477 if (flag & FLAG_DSACKING_ACK) 3478 tcp_fastretrans_alert(sk, acked, prior_unsacked, 3479 is_dupack, flag); 3480 /* If this ack opens up a zero window, clear backoff. It was 3481 * being used to time the probes, and is probably far higher than 3482 * it needs to be for normal retransmission. 3483 */ 3484 if (tcp_send_head(sk)) 3485 tcp_ack_probe(sk); 3486 3487 if (tp->tlp_high_seq) 3488 tcp_process_tlp_ack(sk, ack, flag); 3489 return 1; 3490 3491 invalid_ack: 3492 SOCK_DEBUG(sk, "Ack %u after %u:%u\n", ack, tp->snd_una, tp->snd_nxt); 3493 return -1; 3494 3495 old_ack: 3496 /* If data was SACKed, tag it and see if we should send more data. 3497 * If data was DSACKed, see if we can undo a cwnd reduction. 3498 */ 3499 if (TCP_SKB_CB(skb)->sacked) { 3500 flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una, 3501 &sack_rtt_us); 3502 tcp_fastretrans_alert(sk, acked, prior_unsacked, 3503 is_dupack, flag); 3504 } 3505 3506 SOCK_DEBUG(sk, "Ack %u before %u:%u\n", ack, tp->snd_una, tp->snd_nxt); 3507 return 0; 3508 } 3509 3510 /* Look for tcp options. Normally only called on SYN and SYNACK packets. 3511 * But, this can also be called on packets in the established flow when 3512 * the fast version below fails. 3513 */ 3514 void tcp_parse_options(const struct sk_buff *skb, 3515 struct tcp_options_received *opt_rx, int estab, 3516 struct tcp_fastopen_cookie *foc) 3517 { 3518 const unsigned char *ptr; 3519 const struct tcphdr *th = tcp_hdr(skb); 3520 int length = (th->doff * 4) - sizeof(struct tcphdr); 3521 3522 ptr = (const unsigned char *)(th + 1); 3523 opt_rx->saw_tstamp = 0; 3524 3525 while (length > 0) { 3526 int opcode = *ptr++; 3527 int opsize; 3528 3529 switch (opcode) { 3530 case TCPOPT_EOL: 3531 return; 3532 case TCPOPT_NOP: /* Ref: RFC 793 section 3.1 */ 3533 length--; 3534 continue; 3535 default: 3536 opsize = *ptr++; 3537 if (opsize < 2) /* "silly options" */ 3538 return; 3539 if (opsize > length) 3540 return; /* don't parse partial options */ 3541 switch (opcode) { 3542 case TCPOPT_MSS: 3543 if (opsize == TCPOLEN_MSS && th->syn && !estab) { 3544 u16 in_mss = get_unaligned_be16(ptr); 3545 if (in_mss) { 3546 if (opt_rx->user_mss && 3547 opt_rx->user_mss < in_mss) 3548 in_mss = opt_rx->user_mss; 3549 opt_rx->mss_clamp = in_mss; 3550 } 3551 } 3552 break; 3553 case TCPOPT_WINDOW: 3554 if (opsize == TCPOLEN_WINDOW && th->syn && 3555 !estab && sysctl_tcp_window_scaling) { 3556 __u8 snd_wscale = *(__u8 *)ptr; 3557 opt_rx->wscale_ok = 1; 3558 if (snd_wscale > 14) { 3559 net_info_ratelimited("%s: Illegal window scaling value %d >14 received\n", 3560 __func__, 3561 snd_wscale); 3562 snd_wscale = 14; 3563 } 3564 opt_rx->snd_wscale = snd_wscale; 3565 } 3566 break; 3567 case TCPOPT_TIMESTAMP: 3568 if ((opsize == TCPOLEN_TIMESTAMP) && 3569 ((estab && opt_rx->tstamp_ok) || 3570 (!estab && sysctl_tcp_timestamps))) { 3571 opt_rx->saw_tstamp = 1; 3572 opt_rx->rcv_tsval = get_unaligned_be32(ptr); 3573 opt_rx->rcv_tsecr = get_unaligned_be32(ptr + 4); 3574 } 3575 break; 3576 case TCPOPT_SACK_PERM: 3577 if (opsize == TCPOLEN_SACK_PERM && th->syn && 3578 !estab && sysctl_tcp_sack) { 3579 opt_rx->sack_ok = TCP_SACK_SEEN; 3580 tcp_sack_reset(opt_rx); 3581 } 3582 break; 3583 3584 case TCPOPT_SACK: 3585 if ((opsize >= (TCPOLEN_SACK_BASE + TCPOLEN_SACK_PERBLOCK)) && 3586 !((opsize - TCPOLEN_SACK_BASE) % TCPOLEN_SACK_PERBLOCK) && 3587 opt_rx->sack_ok) { 3588 TCP_SKB_CB(skb)->sacked = (ptr - 2) - (unsigned char *)th; 3589 } 3590 break; 3591 #ifdef CONFIG_TCP_MD5SIG 3592 case TCPOPT_MD5SIG: 3593 /* 3594 * The MD5 Hash has already been 3595 * checked (see tcp_v{4,6}_do_rcv()). 3596 */ 3597 break; 3598 #endif 3599 case TCPOPT_EXP: 3600 /* Fast Open option shares code 254 using a 3601 * 16 bits magic number. It's valid only in 3602 * SYN or SYN-ACK with an even size. 3603 */ 3604 if (opsize < TCPOLEN_EXP_FASTOPEN_BASE || 3605 get_unaligned_be16(ptr) != TCPOPT_FASTOPEN_MAGIC || 3606 foc == NULL || !th->syn || (opsize & 1)) 3607 break; 3608 foc->len = opsize - TCPOLEN_EXP_FASTOPEN_BASE; 3609 if (foc->len >= TCP_FASTOPEN_COOKIE_MIN && 3610 foc->len <= TCP_FASTOPEN_COOKIE_MAX) 3611 memcpy(foc->val, ptr + 2, foc->len); 3612 else if (foc->len != 0) 3613 foc->len = -1; 3614 break; 3615 3616 } 3617 ptr += opsize-2; 3618 length -= opsize; 3619 } 3620 } 3621 } 3622 EXPORT_SYMBOL(tcp_parse_options); 3623 3624 static bool tcp_parse_aligned_timestamp(struct tcp_sock *tp, const struct tcphdr *th) 3625 { 3626 const __be32 *ptr = (const __be32 *)(th + 1); 3627 3628 if (*ptr == htonl((TCPOPT_NOP << 24) | (TCPOPT_NOP << 16) 3629 | (TCPOPT_TIMESTAMP << 8) | TCPOLEN_TIMESTAMP)) { 3630 tp->rx_opt.saw_tstamp = 1; 3631 ++ptr; 3632 tp->rx_opt.rcv_tsval = ntohl(*ptr); 3633 ++ptr; 3634 if (*ptr) 3635 tp->rx_opt.rcv_tsecr = ntohl(*ptr) - tp->tsoffset; 3636 else 3637 tp->rx_opt.rcv_tsecr = 0; 3638 return true; 3639 } 3640 return false; 3641 } 3642 3643 /* Fast parse options. This hopes to only see timestamps. 3644 * If it is wrong it falls back on tcp_parse_options(). 3645 */ 3646 static bool tcp_fast_parse_options(const struct sk_buff *skb, 3647 const struct tcphdr *th, struct tcp_sock *tp) 3648 { 3649 /* In the spirit of fast parsing, compare doff directly to constant 3650 * values. Because equality is used, short doff can be ignored here. 3651 */ 3652 if (th->doff == (sizeof(*th) / 4)) { 3653 tp->rx_opt.saw_tstamp = 0; 3654 return false; 3655 } else if (tp->rx_opt.tstamp_ok && 3656 th->doff == ((sizeof(*th) + TCPOLEN_TSTAMP_ALIGNED) / 4)) { 3657 if (tcp_parse_aligned_timestamp(tp, th)) 3658 return true; 3659 } 3660 3661 tcp_parse_options(skb, &tp->rx_opt, 1, NULL); 3662 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr) 3663 tp->rx_opt.rcv_tsecr -= tp->tsoffset; 3664 3665 return true; 3666 } 3667 3668 #ifdef CONFIG_TCP_MD5SIG 3669 /* 3670 * Parse MD5 Signature option 3671 */ 3672 const u8 *tcp_parse_md5sig_option(const struct tcphdr *th) 3673 { 3674 int length = (th->doff << 2) - sizeof(*th); 3675 const u8 *ptr = (const u8 *)(th + 1); 3676 3677 /* If the TCP option is too short, we can short cut */ 3678 if (length < TCPOLEN_MD5SIG) 3679 return NULL; 3680 3681 while (length > 0) { 3682 int opcode = *ptr++; 3683 int opsize; 3684 3685 switch (opcode) { 3686 case TCPOPT_EOL: 3687 return NULL; 3688 case TCPOPT_NOP: 3689 length--; 3690 continue; 3691 default: 3692 opsize = *ptr++; 3693 if (opsize < 2 || opsize > length) 3694 return NULL; 3695 if (opcode == TCPOPT_MD5SIG) 3696 return opsize == TCPOLEN_MD5SIG ? ptr : NULL; 3697 } 3698 ptr += opsize - 2; 3699 length -= opsize; 3700 } 3701 return NULL; 3702 } 3703 EXPORT_SYMBOL(tcp_parse_md5sig_option); 3704 #endif 3705 3706 /* Sorry, PAWS as specified is broken wrt. pure-ACKs -DaveM 3707 * 3708 * It is not fatal. If this ACK does _not_ change critical state (seqs, window) 3709 * it can pass through stack. So, the following predicate verifies that 3710 * this segment is not used for anything but congestion avoidance or 3711 * fast retransmit. Moreover, we even are able to eliminate most of such 3712 * second order effects, if we apply some small "replay" window (~RTO) 3713 * to timestamp space. 3714 * 3715 * All these measures still do not guarantee that we reject wrapped ACKs 3716 * on networks with high bandwidth, when sequence space is recycled fastly, 3717 * but it guarantees that such events will be very rare and do not affect 3718 * connection seriously. This doesn't look nice, but alas, PAWS is really 3719 * buggy extension. 3720 * 3721 * [ Later note. Even worse! It is buggy for segments _with_ data. RFC 3722 * states that events when retransmit arrives after original data are rare. 3723 * It is a blatant lie. VJ forgot about fast retransmit! 8)8) It is 3724 * the biggest problem on large power networks even with minor reordering. 3725 * OK, let's give it small replay window. If peer clock is even 1hz, it is safe 3726 * up to bandwidth of 18Gigabit/sec. 8) ] 3727 */ 3728 3729 static int tcp_disordered_ack(const struct sock *sk, const struct sk_buff *skb) 3730 { 3731 const struct tcp_sock *tp = tcp_sk(sk); 3732 const struct tcphdr *th = tcp_hdr(skb); 3733 u32 seq = TCP_SKB_CB(skb)->seq; 3734 u32 ack = TCP_SKB_CB(skb)->ack_seq; 3735 3736 return (/* 1. Pure ACK with correct sequence number. */ 3737 (th->ack && seq == TCP_SKB_CB(skb)->end_seq && seq == tp->rcv_nxt) && 3738 3739 /* 2. ... and duplicate ACK. */ 3740 ack == tp->snd_una && 3741 3742 /* 3. ... and does not update window. */ 3743 !tcp_may_update_window(tp, ack, seq, ntohs(th->window) << tp->rx_opt.snd_wscale) && 3744 3745 /* 4. ... and sits in replay window. */ 3746 (s32)(tp->rx_opt.ts_recent - tp->rx_opt.rcv_tsval) <= (inet_csk(sk)->icsk_rto * 1024) / HZ); 3747 } 3748 3749 static inline bool tcp_paws_discard(const struct sock *sk, 3750 const struct sk_buff *skb) 3751 { 3752 const struct tcp_sock *tp = tcp_sk(sk); 3753 3754 return !tcp_paws_check(&tp->rx_opt, TCP_PAWS_WINDOW) && 3755 !tcp_disordered_ack(sk, skb); 3756 } 3757 3758 /* Check segment sequence number for validity. 3759 * 3760 * Segment controls are considered valid, if the segment 3761 * fits to the window after truncation to the window. Acceptability 3762 * of data (and SYN, FIN, of course) is checked separately. 3763 * See tcp_data_queue(), for example. 3764 * 3765 * Also, controls (RST is main one) are accepted using RCV.WUP instead 3766 * of RCV.NXT. Peer still did not advance his SND.UNA when we 3767 * delayed ACK, so that hisSND.UNA<=ourRCV.WUP. 3768 * (borrowed from freebsd) 3769 */ 3770 3771 static inline bool tcp_sequence(const struct tcp_sock *tp, u32 seq, u32 end_seq) 3772 { 3773 return !before(end_seq, tp->rcv_wup) && 3774 !after(seq, tp->rcv_nxt + tcp_receive_window(tp)); 3775 } 3776 3777 /* When we get a reset we do this. */ 3778 void tcp_reset(struct sock *sk) 3779 { 3780 /* We want the right error as BSD sees it (and indeed as we do). */ 3781 switch (sk->sk_state) { 3782 case TCP_SYN_SENT: 3783 sk->sk_err = ECONNREFUSED; 3784 break; 3785 case TCP_CLOSE_WAIT: 3786 sk->sk_err = EPIPE; 3787 break; 3788 case TCP_CLOSE: 3789 return; 3790 default: 3791 sk->sk_err = ECONNRESET; 3792 } 3793 /* This barrier is coupled with smp_rmb() in tcp_poll() */ 3794 smp_wmb(); 3795 3796 if (!sock_flag(sk, SOCK_DEAD)) 3797 sk->sk_error_report(sk); 3798 3799 tcp_done(sk); 3800 } 3801 3802 /* 3803 * Process the FIN bit. This now behaves as it is supposed to work 3804 * and the FIN takes effect when it is validly part of sequence 3805 * space. Not before when we get holes. 3806 * 3807 * If we are ESTABLISHED, a received fin moves us to CLOSE-WAIT 3808 * (and thence onto LAST-ACK and finally, CLOSE, we never enter 3809 * TIME-WAIT) 3810 * 3811 * If we are in FINWAIT-1, a received FIN indicates simultaneous 3812 * close and we go into CLOSING (and later onto TIME-WAIT) 3813 * 3814 * If we are in FINWAIT-2, a received FIN moves us to TIME-WAIT. 3815 */ 3816 static void tcp_fin(struct sock *sk) 3817 { 3818 struct tcp_sock *tp = tcp_sk(sk); 3819 const struct dst_entry *dst; 3820 3821 inet_csk_schedule_ack(sk); 3822 3823 sk->sk_shutdown |= RCV_SHUTDOWN; 3824 sock_set_flag(sk, SOCK_DONE); 3825 3826 switch (sk->sk_state) { 3827 case TCP_SYN_RECV: 3828 case TCP_ESTABLISHED: 3829 /* Move to CLOSE_WAIT */ 3830 tcp_set_state(sk, TCP_CLOSE_WAIT); 3831 dst = __sk_dst_get(sk); 3832 if (!dst || !dst_metric(dst, RTAX_QUICKACK)) 3833 inet_csk(sk)->icsk_ack.pingpong = 1; 3834 break; 3835 3836 case TCP_CLOSE_WAIT: 3837 case TCP_CLOSING: 3838 /* Received a retransmission of the FIN, do 3839 * nothing. 3840 */ 3841 break; 3842 case TCP_LAST_ACK: 3843 /* RFC793: Remain in the LAST-ACK state. */ 3844 break; 3845 3846 case TCP_FIN_WAIT1: 3847 /* This case occurs when a simultaneous close 3848 * happens, we must ack the received FIN and 3849 * enter the CLOSING state. 3850 */ 3851 tcp_send_ack(sk); 3852 tcp_set_state(sk, TCP_CLOSING); 3853 break; 3854 case TCP_FIN_WAIT2: 3855 /* Received a FIN -- send ACK and enter TIME_WAIT. */ 3856 tcp_send_ack(sk); 3857 tcp_time_wait(sk, TCP_TIME_WAIT, 0); 3858 break; 3859 default: 3860 /* Only TCP_LISTEN and TCP_CLOSE are left, in these 3861 * cases we should never reach this piece of code. 3862 */ 3863 pr_err("%s: Impossible, sk->sk_state=%d\n", 3864 __func__, sk->sk_state); 3865 break; 3866 } 3867 3868 /* It _is_ possible, that we have something out-of-order _after_ FIN. 3869 * Probably, we should reset in this case. For now drop them. 3870 */ 3871 __skb_queue_purge(&tp->out_of_order_queue); 3872 if (tcp_is_sack(tp)) 3873 tcp_sack_reset(&tp->rx_opt); 3874 sk_mem_reclaim(sk); 3875 3876 if (!sock_flag(sk, SOCK_DEAD)) { 3877 sk->sk_state_change(sk); 3878 3879 /* Do not send POLL_HUP for half duplex close. */ 3880 if (sk->sk_shutdown == SHUTDOWN_MASK || 3881 sk->sk_state == TCP_CLOSE) 3882 sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_HUP); 3883 else 3884 sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_IN); 3885 } 3886 } 3887 3888 static inline bool tcp_sack_extend(struct tcp_sack_block *sp, u32 seq, 3889 u32 end_seq) 3890 { 3891 if (!after(seq, sp->end_seq) && !after(sp->start_seq, end_seq)) { 3892 if (before(seq, sp->start_seq)) 3893 sp->start_seq = seq; 3894 if (after(end_seq, sp->end_seq)) 3895 sp->end_seq = end_seq; 3896 return true; 3897 } 3898 return false; 3899 } 3900 3901 static void tcp_dsack_set(struct sock *sk, u32 seq, u32 end_seq) 3902 { 3903 struct tcp_sock *tp = tcp_sk(sk); 3904 3905 if (tcp_is_sack(tp) && sysctl_tcp_dsack) { 3906 int mib_idx; 3907 3908 if (before(seq, tp->rcv_nxt)) 3909 mib_idx = LINUX_MIB_TCPDSACKOLDSENT; 3910 else 3911 mib_idx = LINUX_MIB_TCPDSACKOFOSENT; 3912 3913 NET_INC_STATS_BH(sock_net(sk), mib_idx); 3914 3915 tp->rx_opt.dsack = 1; 3916 tp->duplicate_sack[0].start_seq = seq; 3917 tp->duplicate_sack[0].end_seq = end_seq; 3918 } 3919 } 3920 3921 static void tcp_dsack_extend(struct sock *sk, u32 seq, u32 end_seq) 3922 { 3923 struct tcp_sock *tp = tcp_sk(sk); 3924 3925 if (!tp->rx_opt.dsack) 3926 tcp_dsack_set(sk, seq, end_seq); 3927 else 3928 tcp_sack_extend(tp->duplicate_sack, seq, end_seq); 3929 } 3930 3931 static void tcp_send_dupack(struct sock *sk, const struct sk_buff *skb) 3932 { 3933 struct tcp_sock *tp = tcp_sk(sk); 3934 3935 if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 3936 before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 3937 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST); 3938 tcp_enter_quickack_mode(sk); 3939 3940 if (tcp_is_sack(tp) && sysctl_tcp_dsack) { 3941 u32 end_seq = TCP_SKB_CB(skb)->end_seq; 3942 3943 if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) 3944 end_seq = tp->rcv_nxt; 3945 tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, end_seq); 3946 } 3947 } 3948 3949 tcp_send_ack(sk); 3950 } 3951 3952 /* These routines update the SACK block as out-of-order packets arrive or 3953 * in-order packets close up the sequence space. 3954 */ 3955 static void tcp_sack_maybe_coalesce(struct tcp_sock *tp) 3956 { 3957 int this_sack; 3958 struct tcp_sack_block *sp = &tp->selective_acks[0]; 3959 struct tcp_sack_block *swalk = sp + 1; 3960 3961 /* See if the recent change to the first SACK eats into 3962 * or hits the sequence space of other SACK blocks, if so coalesce. 3963 */ 3964 for (this_sack = 1; this_sack < tp->rx_opt.num_sacks;) { 3965 if (tcp_sack_extend(sp, swalk->start_seq, swalk->end_seq)) { 3966 int i; 3967 3968 /* Zap SWALK, by moving every further SACK up by one slot. 3969 * Decrease num_sacks. 3970 */ 3971 tp->rx_opt.num_sacks--; 3972 for (i = this_sack; i < tp->rx_opt.num_sacks; i++) 3973 sp[i] = sp[i + 1]; 3974 continue; 3975 } 3976 this_sack++, swalk++; 3977 } 3978 } 3979 3980 static void tcp_sack_new_ofo_skb(struct sock *sk, u32 seq, u32 end_seq) 3981 { 3982 struct tcp_sock *tp = tcp_sk(sk); 3983 struct tcp_sack_block *sp = &tp->selective_acks[0]; 3984 int cur_sacks = tp->rx_opt.num_sacks; 3985 int this_sack; 3986 3987 if (!cur_sacks) 3988 goto new_sack; 3989 3990 for (this_sack = 0; this_sack < cur_sacks; this_sack++, sp++) { 3991 if (tcp_sack_extend(sp, seq, end_seq)) { 3992 /* Rotate this_sack to the first one. */ 3993 for (; this_sack > 0; this_sack--, sp--) 3994 swap(*sp, *(sp - 1)); 3995 if (cur_sacks > 1) 3996 tcp_sack_maybe_coalesce(tp); 3997 return; 3998 } 3999 } 4000 4001 /* Could not find an adjacent existing SACK, build a new one, 4002 * put it at the front, and shift everyone else down. We 4003 * always know there is at least one SACK present already here. 4004 * 4005 * If the sack array is full, forget about the last one. 4006 */ 4007 if (this_sack >= TCP_NUM_SACKS) { 4008 this_sack--; 4009 tp->rx_opt.num_sacks--; 4010 sp--; 4011 } 4012 for (; this_sack > 0; this_sack--, sp--) 4013 *sp = *(sp - 1); 4014 4015 new_sack: 4016 /* Build the new head SACK, and we're done. */ 4017 sp->start_seq = seq; 4018 sp->end_seq = end_seq; 4019 tp->rx_opt.num_sacks++; 4020 } 4021 4022 /* RCV.NXT advances, some SACKs should be eaten. */ 4023 4024 static void tcp_sack_remove(struct tcp_sock *tp) 4025 { 4026 struct tcp_sack_block *sp = &tp->selective_acks[0]; 4027 int num_sacks = tp->rx_opt.num_sacks; 4028 int this_sack; 4029 4030 /* Empty ofo queue, hence, all the SACKs are eaten. Clear. */ 4031 if (skb_queue_empty(&tp->out_of_order_queue)) { 4032 tp->rx_opt.num_sacks = 0; 4033 return; 4034 } 4035 4036 for (this_sack = 0; this_sack < num_sacks;) { 4037 /* Check if the start of the sack is covered by RCV.NXT. */ 4038 if (!before(tp->rcv_nxt, sp->start_seq)) { 4039 int i; 4040 4041 /* RCV.NXT must cover all the block! */ 4042 WARN_ON(before(tp->rcv_nxt, sp->end_seq)); 4043 4044 /* Zap this SACK, by moving forward any other SACKS. */ 4045 for (i = this_sack+1; i < num_sacks; i++) 4046 tp->selective_acks[i-1] = tp->selective_acks[i]; 4047 num_sacks--; 4048 continue; 4049 } 4050 this_sack++; 4051 sp++; 4052 } 4053 tp->rx_opt.num_sacks = num_sacks; 4054 } 4055 4056 /* This one checks to see if we can put data from the 4057 * out_of_order queue into the receive_queue. 4058 */ 4059 static void tcp_ofo_queue(struct sock *sk) 4060 { 4061 struct tcp_sock *tp = tcp_sk(sk); 4062 __u32 dsack_high = tp->rcv_nxt; 4063 struct sk_buff *skb; 4064 4065 while ((skb = skb_peek(&tp->out_of_order_queue)) != NULL) { 4066 if (after(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) 4067 break; 4068 4069 if (before(TCP_SKB_CB(skb)->seq, dsack_high)) { 4070 __u32 dsack = dsack_high; 4071 if (before(TCP_SKB_CB(skb)->end_seq, dsack_high)) 4072 dsack_high = TCP_SKB_CB(skb)->end_seq; 4073 tcp_dsack_extend(sk, TCP_SKB_CB(skb)->seq, dsack); 4074 } 4075 4076 if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) { 4077 SOCK_DEBUG(sk, "ofo packet was already received\n"); 4078 __skb_unlink(skb, &tp->out_of_order_queue); 4079 __kfree_skb(skb); 4080 continue; 4081 } 4082 SOCK_DEBUG(sk, "ofo requeuing : rcv_next %X seq %X - %X\n", 4083 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, 4084 TCP_SKB_CB(skb)->end_seq); 4085 4086 __skb_unlink(skb, &tp->out_of_order_queue); 4087 __skb_queue_tail(&sk->sk_receive_queue, skb); 4088 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 4089 if (tcp_hdr(skb)->fin) 4090 tcp_fin(sk); 4091 } 4092 } 4093 4094 static bool tcp_prune_ofo_queue(struct sock *sk); 4095 static int tcp_prune_queue(struct sock *sk); 4096 4097 static int tcp_try_rmem_schedule(struct sock *sk, struct sk_buff *skb, 4098 unsigned int size) 4099 { 4100 if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf || 4101 !sk_rmem_schedule(sk, skb, size)) { 4102 4103 if (tcp_prune_queue(sk) < 0) 4104 return -1; 4105 4106 if (!sk_rmem_schedule(sk, skb, size)) { 4107 if (!tcp_prune_ofo_queue(sk)) 4108 return -1; 4109 4110 if (!sk_rmem_schedule(sk, skb, size)) 4111 return -1; 4112 } 4113 } 4114 return 0; 4115 } 4116 4117 /** 4118 * tcp_try_coalesce - try to merge skb to prior one 4119 * @sk: socket 4120 * @to: prior buffer 4121 * @from: buffer to add in queue 4122 * @fragstolen: pointer to boolean 4123 * 4124 * Before queueing skb @from after @to, try to merge them 4125 * to reduce overall memory use and queue lengths, if cost is small. 4126 * Packets in ofo or receive queues can stay a long time. 4127 * Better try to coalesce them right now to avoid future collapses. 4128 * Returns true if caller should free @from instead of queueing it 4129 */ 4130 static bool tcp_try_coalesce(struct sock *sk, 4131 struct sk_buff *to, 4132 struct sk_buff *from, 4133 bool *fragstolen) 4134 { 4135 int delta; 4136 4137 *fragstolen = false; 4138 4139 if (tcp_hdr(from)->fin) 4140 return false; 4141 4142 /* Its possible this segment overlaps with prior segment in queue */ 4143 if (TCP_SKB_CB(from)->seq != TCP_SKB_CB(to)->end_seq) 4144 return false; 4145 4146 if (!skb_try_coalesce(to, from, fragstolen, &delta)) 4147 return false; 4148 4149 atomic_add(delta, &sk->sk_rmem_alloc); 4150 sk_mem_charge(sk, delta); 4151 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPRCVCOALESCE); 4152 TCP_SKB_CB(to)->end_seq = TCP_SKB_CB(from)->end_seq; 4153 TCP_SKB_CB(to)->ack_seq = TCP_SKB_CB(from)->ack_seq; 4154 return true; 4155 } 4156 4157 static void tcp_data_queue_ofo(struct sock *sk, struct sk_buff *skb) 4158 { 4159 struct tcp_sock *tp = tcp_sk(sk); 4160 struct sk_buff *skb1; 4161 u32 seq, end_seq; 4162 4163 TCP_ECN_check_ce(tp, skb); 4164 4165 if (unlikely(tcp_try_rmem_schedule(sk, skb, skb->truesize))) { 4166 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPOFODROP); 4167 __kfree_skb(skb); 4168 return; 4169 } 4170 4171 /* Disable header prediction. */ 4172 tp->pred_flags = 0; 4173 inet_csk_schedule_ack(sk); 4174 4175 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPOFOQUEUE); 4176 SOCK_DEBUG(sk, "out of order segment: rcv_next %X seq %X - %X\n", 4177 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq); 4178 4179 skb1 = skb_peek_tail(&tp->out_of_order_queue); 4180 if (!skb1) { 4181 /* Initial out of order segment, build 1 SACK. */ 4182 if (tcp_is_sack(tp)) { 4183 tp->rx_opt.num_sacks = 1; 4184 tp->selective_acks[0].start_seq = TCP_SKB_CB(skb)->seq; 4185 tp->selective_acks[0].end_seq = 4186 TCP_SKB_CB(skb)->end_seq; 4187 } 4188 __skb_queue_head(&tp->out_of_order_queue, skb); 4189 goto end; 4190 } 4191 4192 seq = TCP_SKB_CB(skb)->seq; 4193 end_seq = TCP_SKB_CB(skb)->end_seq; 4194 4195 if (seq == TCP_SKB_CB(skb1)->end_seq) { 4196 bool fragstolen; 4197 4198 if (!tcp_try_coalesce(sk, skb1, skb, &fragstolen)) { 4199 __skb_queue_after(&tp->out_of_order_queue, skb1, skb); 4200 } else { 4201 tcp_grow_window(sk, skb); 4202 kfree_skb_partial(skb, fragstolen); 4203 skb = NULL; 4204 } 4205 4206 if (!tp->rx_opt.num_sacks || 4207 tp->selective_acks[0].end_seq != seq) 4208 goto add_sack; 4209 4210 /* Common case: data arrive in order after hole. */ 4211 tp->selective_acks[0].end_seq = end_seq; 4212 goto end; 4213 } 4214 4215 /* Find place to insert this segment. */ 4216 while (1) { 4217 if (!after(TCP_SKB_CB(skb1)->seq, seq)) 4218 break; 4219 if (skb_queue_is_first(&tp->out_of_order_queue, skb1)) { 4220 skb1 = NULL; 4221 break; 4222 } 4223 skb1 = skb_queue_prev(&tp->out_of_order_queue, skb1); 4224 } 4225 4226 /* Do skb overlap to previous one? */ 4227 if (skb1 && before(seq, TCP_SKB_CB(skb1)->end_seq)) { 4228 if (!after(end_seq, TCP_SKB_CB(skb1)->end_seq)) { 4229 /* All the bits are present. Drop. */ 4230 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPOFOMERGE); 4231 __kfree_skb(skb); 4232 skb = NULL; 4233 tcp_dsack_set(sk, seq, end_seq); 4234 goto add_sack; 4235 } 4236 if (after(seq, TCP_SKB_CB(skb1)->seq)) { 4237 /* Partial overlap. */ 4238 tcp_dsack_set(sk, seq, 4239 TCP_SKB_CB(skb1)->end_seq); 4240 } else { 4241 if (skb_queue_is_first(&tp->out_of_order_queue, 4242 skb1)) 4243 skb1 = NULL; 4244 else 4245 skb1 = skb_queue_prev( 4246 &tp->out_of_order_queue, 4247 skb1); 4248 } 4249 } 4250 if (!skb1) 4251 __skb_queue_head(&tp->out_of_order_queue, skb); 4252 else 4253 __skb_queue_after(&tp->out_of_order_queue, skb1, skb); 4254 4255 /* And clean segments covered by new one as whole. */ 4256 while (!skb_queue_is_last(&tp->out_of_order_queue, skb)) { 4257 skb1 = skb_queue_next(&tp->out_of_order_queue, skb); 4258 4259 if (!after(end_seq, TCP_SKB_CB(skb1)->seq)) 4260 break; 4261 if (before(end_seq, TCP_SKB_CB(skb1)->end_seq)) { 4262 tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq, 4263 end_seq); 4264 break; 4265 } 4266 __skb_unlink(skb1, &tp->out_of_order_queue); 4267 tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq, 4268 TCP_SKB_CB(skb1)->end_seq); 4269 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPOFOMERGE); 4270 __kfree_skb(skb1); 4271 } 4272 4273 add_sack: 4274 if (tcp_is_sack(tp)) 4275 tcp_sack_new_ofo_skb(sk, seq, end_seq); 4276 end: 4277 if (skb) { 4278 tcp_grow_window(sk, skb); 4279 skb_set_owner_r(skb, sk); 4280 } 4281 } 4282 4283 static int __must_check tcp_queue_rcv(struct sock *sk, struct sk_buff *skb, int hdrlen, 4284 bool *fragstolen) 4285 { 4286 int eaten; 4287 struct sk_buff *tail = skb_peek_tail(&sk->sk_receive_queue); 4288 4289 __skb_pull(skb, hdrlen); 4290 eaten = (tail && 4291 tcp_try_coalesce(sk, tail, skb, fragstolen)) ? 1 : 0; 4292 tcp_sk(sk)->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 4293 if (!eaten) { 4294 __skb_queue_tail(&sk->sk_receive_queue, skb); 4295 skb_set_owner_r(skb, sk); 4296 } 4297 return eaten; 4298 } 4299 4300 int tcp_send_rcvq(struct sock *sk, struct msghdr *msg, size_t size) 4301 { 4302 struct sk_buff *skb = NULL; 4303 struct tcphdr *th; 4304 bool fragstolen; 4305 4306 if (size == 0) 4307 return 0; 4308 4309 skb = alloc_skb(size + sizeof(*th), sk->sk_allocation); 4310 if (!skb) 4311 goto err; 4312 4313 if (tcp_try_rmem_schedule(sk, skb, size + sizeof(*th))) 4314 goto err_free; 4315 4316 th = (struct tcphdr *)skb_put(skb, sizeof(*th)); 4317 skb_reset_transport_header(skb); 4318 memset(th, 0, sizeof(*th)); 4319 4320 if (memcpy_fromiovec(skb_put(skb, size), msg->msg_iov, size)) 4321 goto err_free; 4322 4323 TCP_SKB_CB(skb)->seq = tcp_sk(sk)->rcv_nxt; 4324 TCP_SKB_CB(skb)->end_seq = TCP_SKB_CB(skb)->seq + size; 4325 TCP_SKB_CB(skb)->ack_seq = tcp_sk(sk)->snd_una - 1; 4326 4327 if (tcp_queue_rcv(sk, skb, sizeof(*th), &fragstolen)) { 4328 WARN_ON_ONCE(fragstolen); /* should not happen */ 4329 __kfree_skb(skb); 4330 } 4331 return size; 4332 4333 err_free: 4334 kfree_skb(skb); 4335 err: 4336 return -ENOMEM; 4337 } 4338 4339 static void tcp_data_queue(struct sock *sk, struct sk_buff *skb) 4340 { 4341 const struct tcphdr *th = tcp_hdr(skb); 4342 struct tcp_sock *tp = tcp_sk(sk); 4343 int eaten = -1; 4344 bool fragstolen = false; 4345 4346 if (TCP_SKB_CB(skb)->seq == TCP_SKB_CB(skb)->end_seq) 4347 goto drop; 4348 4349 skb_dst_drop(skb); 4350 __skb_pull(skb, th->doff * 4); 4351 4352 TCP_ECN_accept_cwr(tp, skb); 4353 4354 tp->rx_opt.dsack = 0; 4355 4356 /* Queue data for delivery to the user. 4357 * Packets in sequence go to the receive queue. 4358 * Out of sequence packets to the out_of_order_queue. 4359 */ 4360 if (TCP_SKB_CB(skb)->seq == tp->rcv_nxt) { 4361 if (tcp_receive_window(tp) == 0) 4362 goto out_of_window; 4363 4364 /* Ok. In sequence. In window. */ 4365 if (tp->ucopy.task == current && 4366 tp->copied_seq == tp->rcv_nxt && tp->ucopy.len && 4367 sock_owned_by_user(sk) && !tp->urg_data) { 4368 int chunk = min_t(unsigned int, skb->len, 4369 tp->ucopy.len); 4370 4371 __set_current_state(TASK_RUNNING); 4372 4373 local_bh_enable(); 4374 if (!skb_copy_datagram_iovec(skb, 0, tp->ucopy.iov, chunk)) { 4375 tp->ucopy.len -= chunk; 4376 tp->copied_seq += chunk; 4377 eaten = (chunk == skb->len); 4378 tcp_rcv_space_adjust(sk); 4379 } 4380 local_bh_disable(); 4381 } 4382 4383 if (eaten <= 0) { 4384 queue_and_out: 4385 if (eaten < 0 && 4386 tcp_try_rmem_schedule(sk, skb, skb->truesize)) 4387 goto drop; 4388 4389 eaten = tcp_queue_rcv(sk, skb, 0, &fragstolen); 4390 } 4391 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 4392 if (skb->len) 4393 tcp_event_data_recv(sk, skb); 4394 if (th->fin) 4395 tcp_fin(sk); 4396 4397 if (!skb_queue_empty(&tp->out_of_order_queue)) { 4398 tcp_ofo_queue(sk); 4399 4400 /* RFC2581. 4.2. SHOULD send immediate ACK, when 4401 * gap in queue is filled. 4402 */ 4403 if (skb_queue_empty(&tp->out_of_order_queue)) 4404 inet_csk(sk)->icsk_ack.pingpong = 0; 4405 } 4406 4407 if (tp->rx_opt.num_sacks) 4408 tcp_sack_remove(tp); 4409 4410 tcp_fast_path_check(sk); 4411 4412 if (eaten > 0) 4413 kfree_skb_partial(skb, fragstolen); 4414 if (!sock_flag(sk, SOCK_DEAD)) 4415 sk->sk_data_ready(sk); 4416 return; 4417 } 4418 4419 if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) { 4420 /* A retransmit, 2nd most common case. Force an immediate ack. */ 4421 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_DELAYEDACKLOST); 4422 tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq); 4423 4424 out_of_window: 4425 tcp_enter_quickack_mode(sk); 4426 inet_csk_schedule_ack(sk); 4427 drop: 4428 __kfree_skb(skb); 4429 return; 4430 } 4431 4432 /* Out of window. F.e. zero window probe. */ 4433 if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt + tcp_receive_window(tp))) 4434 goto out_of_window; 4435 4436 tcp_enter_quickack_mode(sk); 4437 4438 if (before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 4439 /* Partial packet, seq < rcv_next < end_seq */ 4440 SOCK_DEBUG(sk, "partial packet: rcv_next %X seq %X - %X\n", 4441 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, 4442 TCP_SKB_CB(skb)->end_seq); 4443 4444 tcp_dsack_set(sk, TCP_SKB_CB(skb)->seq, tp->rcv_nxt); 4445 4446 /* If window is closed, drop tail of packet. But after 4447 * remembering D-SACK for its head made in previous line. 4448 */ 4449 if (!tcp_receive_window(tp)) 4450 goto out_of_window; 4451 goto queue_and_out; 4452 } 4453 4454 tcp_data_queue_ofo(sk, skb); 4455 } 4456 4457 static struct sk_buff *tcp_collapse_one(struct sock *sk, struct sk_buff *skb, 4458 struct sk_buff_head *list) 4459 { 4460 struct sk_buff *next = NULL; 4461 4462 if (!skb_queue_is_last(list, skb)) 4463 next = skb_queue_next(list, skb); 4464 4465 __skb_unlink(skb, list); 4466 __kfree_skb(skb); 4467 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPRCVCOLLAPSED); 4468 4469 return next; 4470 } 4471 4472 /* Collapse contiguous sequence of skbs head..tail with 4473 * sequence numbers start..end. 4474 * 4475 * If tail is NULL, this means until the end of the list. 4476 * 4477 * Segments with FIN/SYN are not collapsed (only because this 4478 * simplifies code) 4479 */ 4480 static void 4481 tcp_collapse(struct sock *sk, struct sk_buff_head *list, 4482 struct sk_buff *head, struct sk_buff *tail, 4483 u32 start, u32 end) 4484 { 4485 struct sk_buff *skb, *n; 4486 bool end_of_skbs; 4487 4488 /* First, check that queue is collapsible and find 4489 * the point where collapsing can be useful. */ 4490 skb = head; 4491 restart: 4492 end_of_skbs = true; 4493 skb_queue_walk_from_safe(list, skb, n) { 4494 if (skb == tail) 4495 break; 4496 /* No new bits? It is possible on ofo queue. */ 4497 if (!before(start, TCP_SKB_CB(skb)->end_seq)) { 4498 skb = tcp_collapse_one(sk, skb, list); 4499 if (!skb) 4500 break; 4501 goto restart; 4502 } 4503 4504 /* The first skb to collapse is: 4505 * - not SYN/FIN and 4506 * - bloated or contains data before "start" or 4507 * overlaps to the next one. 4508 */ 4509 if (!tcp_hdr(skb)->syn && !tcp_hdr(skb)->fin && 4510 (tcp_win_from_space(skb->truesize) > skb->len || 4511 before(TCP_SKB_CB(skb)->seq, start))) { 4512 end_of_skbs = false; 4513 break; 4514 } 4515 4516 if (!skb_queue_is_last(list, skb)) { 4517 struct sk_buff *next = skb_queue_next(list, skb); 4518 if (next != tail && 4519 TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(next)->seq) { 4520 end_of_skbs = false; 4521 break; 4522 } 4523 } 4524 4525 /* Decided to skip this, advance start seq. */ 4526 start = TCP_SKB_CB(skb)->end_seq; 4527 } 4528 if (end_of_skbs || tcp_hdr(skb)->syn || tcp_hdr(skb)->fin) 4529 return; 4530 4531 while (before(start, end)) { 4532 struct sk_buff *nskb; 4533 unsigned int header = skb_headroom(skb); 4534 int copy = SKB_MAX_ORDER(header, 0); 4535 4536 /* Too big header? This can happen with IPv6. */ 4537 if (copy < 0) 4538 return; 4539 if (end - start < copy) 4540 copy = end - start; 4541 nskb = alloc_skb(copy + header, GFP_ATOMIC); 4542 if (!nskb) 4543 return; 4544 4545 skb_set_mac_header(nskb, skb_mac_header(skb) - skb->head); 4546 skb_set_network_header(nskb, (skb_network_header(skb) - 4547 skb->head)); 4548 skb_set_transport_header(nskb, (skb_transport_header(skb) - 4549 skb->head)); 4550 skb_reserve(nskb, header); 4551 memcpy(nskb->head, skb->head, header); 4552 memcpy(nskb->cb, skb->cb, sizeof(skb->cb)); 4553 TCP_SKB_CB(nskb)->seq = TCP_SKB_CB(nskb)->end_seq = start; 4554 __skb_queue_before(list, skb, nskb); 4555 skb_set_owner_r(nskb, sk); 4556 4557 /* Copy data, releasing collapsed skbs. */ 4558 while (copy > 0) { 4559 int offset = start - TCP_SKB_CB(skb)->seq; 4560 int size = TCP_SKB_CB(skb)->end_seq - start; 4561 4562 BUG_ON(offset < 0); 4563 if (size > 0) { 4564 size = min(copy, size); 4565 if (skb_copy_bits(skb, offset, skb_put(nskb, size), size)) 4566 BUG(); 4567 TCP_SKB_CB(nskb)->end_seq += size; 4568 copy -= size; 4569 start += size; 4570 } 4571 if (!before(start, TCP_SKB_CB(skb)->end_seq)) { 4572 skb = tcp_collapse_one(sk, skb, list); 4573 if (!skb || 4574 skb == tail || 4575 tcp_hdr(skb)->syn || 4576 tcp_hdr(skb)->fin) 4577 return; 4578 } 4579 } 4580 } 4581 } 4582 4583 /* Collapse ofo queue. Algorithm: select contiguous sequence of skbs 4584 * and tcp_collapse() them until all the queue is collapsed. 4585 */ 4586 static void tcp_collapse_ofo_queue(struct sock *sk) 4587 { 4588 struct tcp_sock *tp = tcp_sk(sk); 4589 struct sk_buff *skb = skb_peek(&tp->out_of_order_queue); 4590 struct sk_buff *head; 4591 u32 start, end; 4592 4593 if (skb == NULL) 4594 return; 4595 4596 start = TCP_SKB_CB(skb)->seq; 4597 end = TCP_SKB_CB(skb)->end_seq; 4598 head = skb; 4599 4600 for (;;) { 4601 struct sk_buff *next = NULL; 4602 4603 if (!skb_queue_is_last(&tp->out_of_order_queue, skb)) 4604 next = skb_queue_next(&tp->out_of_order_queue, skb); 4605 skb = next; 4606 4607 /* Segment is terminated when we see gap or when 4608 * we are at the end of all the queue. */ 4609 if (!skb || 4610 after(TCP_SKB_CB(skb)->seq, end) || 4611 before(TCP_SKB_CB(skb)->end_seq, start)) { 4612 tcp_collapse(sk, &tp->out_of_order_queue, 4613 head, skb, start, end); 4614 head = skb; 4615 if (!skb) 4616 break; 4617 /* Start new segment */ 4618 start = TCP_SKB_CB(skb)->seq; 4619 end = TCP_SKB_CB(skb)->end_seq; 4620 } else { 4621 if (before(TCP_SKB_CB(skb)->seq, start)) 4622 start = TCP_SKB_CB(skb)->seq; 4623 if (after(TCP_SKB_CB(skb)->end_seq, end)) 4624 end = TCP_SKB_CB(skb)->end_seq; 4625 } 4626 } 4627 } 4628 4629 /* 4630 * Purge the out-of-order queue. 4631 * Return true if queue was pruned. 4632 */ 4633 static bool tcp_prune_ofo_queue(struct sock *sk) 4634 { 4635 struct tcp_sock *tp = tcp_sk(sk); 4636 bool res = false; 4637 4638 if (!skb_queue_empty(&tp->out_of_order_queue)) { 4639 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_OFOPRUNED); 4640 __skb_queue_purge(&tp->out_of_order_queue); 4641 4642 /* Reset SACK state. A conforming SACK implementation will 4643 * do the same at a timeout based retransmit. When a connection 4644 * is in a sad state like this, we care only about integrity 4645 * of the connection not performance. 4646 */ 4647 if (tp->rx_opt.sack_ok) 4648 tcp_sack_reset(&tp->rx_opt); 4649 sk_mem_reclaim(sk); 4650 res = true; 4651 } 4652 return res; 4653 } 4654 4655 /* Reduce allocated memory if we can, trying to get 4656 * the socket within its memory limits again. 4657 * 4658 * Return less than zero if we should start dropping frames 4659 * until the socket owning process reads some of the data 4660 * to stabilize the situation. 4661 */ 4662 static int tcp_prune_queue(struct sock *sk) 4663 { 4664 struct tcp_sock *tp = tcp_sk(sk); 4665 4666 SOCK_DEBUG(sk, "prune_queue: c=%x\n", tp->copied_seq); 4667 4668 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PRUNECALLED); 4669 4670 if (atomic_read(&sk->sk_rmem_alloc) >= sk->sk_rcvbuf) 4671 tcp_clamp_window(sk); 4672 else if (sk_under_memory_pressure(sk)) 4673 tp->rcv_ssthresh = min(tp->rcv_ssthresh, 4U * tp->advmss); 4674 4675 tcp_collapse_ofo_queue(sk); 4676 if (!skb_queue_empty(&sk->sk_receive_queue)) 4677 tcp_collapse(sk, &sk->sk_receive_queue, 4678 skb_peek(&sk->sk_receive_queue), 4679 NULL, 4680 tp->copied_seq, tp->rcv_nxt); 4681 sk_mem_reclaim(sk); 4682 4683 if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf) 4684 return 0; 4685 4686 /* Collapsing did not help, destructive actions follow. 4687 * This must not ever occur. */ 4688 4689 tcp_prune_ofo_queue(sk); 4690 4691 if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf) 4692 return 0; 4693 4694 /* If we are really being abused, tell the caller to silently 4695 * drop receive data on the floor. It will get retransmitted 4696 * and hopefully then we'll have sufficient space. 4697 */ 4698 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_RCVPRUNED); 4699 4700 /* Massive buffer overcommit. */ 4701 tp->pred_flags = 0; 4702 return -1; 4703 } 4704 4705 static bool tcp_should_expand_sndbuf(const struct sock *sk) 4706 { 4707 const struct tcp_sock *tp = tcp_sk(sk); 4708 4709 /* If the user specified a specific send buffer setting, do 4710 * not modify it. 4711 */ 4712 if (sk->sk_userlocks & SOCK_SNDBUF_LOCK) 4713 return false; 4714 4715 /* If we are under global TCP memory pressure, do not expand. */ 4716 if (sk_under_memory_pressure(sk)) 4717 return false; 4718 4719 /* If we are under soft global TCP memory pressure, do not expand. */ 4720 if (sk_memory_allocated(sk) >= sk_prot_mem_limits(sk, 0)) 4721 return false; 4722 4723 /* If we filled the congestion window, do not expand. */ 4724 if (tp->packets_out >= tp->snd_cwnd) 4725 return false; 4726 4727 return true; 4728 } 4729 4730 /* When incoming ACK allowed to free some skb from write_queue, 4731 * we remember this event in flag SOCK_QUEUE_SHRUNK and wake up socket 4732 * on the exit from tcp input handler. 4733 * 4734 * PROBLEM: sndbuf expansion does not work well with largesend. 4735 */ 4736 static void tcp_new_space(struct sock *sk) 4737 { 4738 struct tcp_sock *tp = tcp_sk(sk); 4739 4740 if (tcp_should_expand_sndbuf(sk)) { 4741 tcp_sndbuf_expand(sk); 4742 tp->snd_cwnd_stamp = tcp_time_stamp; 4743 } 4744 4745 sk->sk_write_space(sk); 4746 } 4747 4748 static void tcp_check_space(struct sock *sk) 4749 { 4750 if (sock_flag(sk, SOCK_QUEUE_SHRUNK)) { 4751 sock_reset_flag(sk, SOCK_QUEUE_SHRUNK); 4752 if (sk->sk_socket && 4753 test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) 4754 tcp_new_space(sk); 4755 } 4756 } 4757 4758 static inline void tcp_data_snd_check(struct sock *sk) 4759 { 4760 tcp_push_pending_frames(sk); 4761 tcp_check_space(sk); 4762 } 4763 4764 /* 4765 * Check if sending an ack is needed. 4766 */ 4767 static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible) 4768 { 4769 struct tcp_sock *tp = tcp_sk(sk); 4770 4771 /* More than one full frame received... */ 4772 if (((tp->rcv_nxt - tp->rcv_wup) > inet_csk(sk)->icsk_ack.rcv_mss && 4773 /* ... and right edge of window advances far enough. 4774 * (tcp_recvmsg() will send ACK otherwise). Or... 4775 */ 4776 __tcp_select_window(sk) >= tp->rcv_wnd) || 4777 /* We ACK each frame or... */ 4778 tcp_in_quickack_mode(sk) || 4779 /* We have out of order data. */ 4780 (ofo_possible && skb_peek(&tp->out_of_order_queue))) { 4781 /* Then ack it now */ 4782 tcp_send_ack(sk); 4783 } else { 4784 /* Else, send delayed ack. */ 4785 tcp_send_delayed_ack(sk); 4786 } 4787 } 4788 4789 static inline void tcp_ack_snd_check(struct sock *sk) 4790 { 4791 if (!inet_csk_ack_scheduled(sk)) { 4792 /* We sent a data segment already. */ 4793 return; 4794 } 4795 __tcp_ack_snd_check(sk, 1); 4796 } 4797 4798 /* 4799 * This routine is only called when we have urgent data 4800 * signaled. Its the 'slow' part of tcp_urg. It could be 4801 * moved inline now as tcp_urg is only called from one 4802 * place. We handle URGent data wrong. We have to - as 4803 * BSD still doesn't use the correction from RFC961. 4804 * For 1003.1g we should support a new option TCP_STDURG to permit 4805 * either form (or just set the sysctl tcp_stdurg). 4806 */ 4807 4808 static void tcp_check_urg(struct sock *sk, const struct tcphdr *th) 4809 { 4810 struct tcp_sock *tp = tcp_sk(sk); 4811 u32 ptr = ntohs(th->urg_ptr); 4812 4813 if (ptr && !sysctl_tcp_stdurg) 4814 ptr--; 4815 ptr += ntohl(th->seq); 4816 4817 /* Ignore urgent data that we've already seen and read. */ 4818 if (after(tp->copied_seq, ptr)) 4819 return; 4820 4821 /* Do not replay urg ptr. 4822 * 4823 * NOTE: interesting situation not covered by specs. 4824 * Misbehaving sender may send urg ptr, pointing to segment, 4825 * which we already have in ofo queue. We are not able to fetch 4826 * such data and will stay in TCP_URG_NOTYET until will be eaten 4827 * by recvmsg(). Seems, we are not obliged to handle such wicked 4828 * situations. But it is worth to think about possibility of some 4829 * DoSes using some hypothetical application level deadlock. 4830 */ 4831 if (before(ptr, tp->rcv_nxt)) 4832 return; 4833 4834 /* Do we already have a newer (or duplicate) urgent pointer? */ 4835 if (tp->urg_data && !after(ptr, tp->urg_seq)) 4836 return; 4837 4838 /* Tell the world about our new urgent pointer. */ 4839 sk_send_sigurg(sk); 4840 4841 /* We may be adding urgent data when the last byte read was 4842 * urgent. To do this requires some care. We cannot just ignore 4843 * tp->copied_seq since we would read the last urgent byte again 4844 * as data, nor can we alter copied_seq until this data arrives 4845 * or we break the semantics of SIOCATMARK (and thus sockatmark()) 4846 * 4847 * NOTE. Double Dutch. Rendering to plain English: author of comment 4848 * above did something sort of send("A", MSG_OOB); send("B", MSG_OOB); 4849 * and expect that both A and B disappear from stream. This is _wrong_. 4850 * Though this happens in BSD with high probability, this is occasional. 4851 * Any application relying on this is buggy. Note also, that fix "works" 4852 * only in this artificial test. Insert some normal data between A and B and we will 4853 * decline of BSD again. Verdict: it is better to remove to trap 4854 * buggy users. 4855 */ 4856 if (tp->urg_seq == tp->copied_seq && tp->urg_data && 4857 !sock_flag(sk, SOCK_URGINLINE) && tp->copied_seq != tp->rcv_nxt) { 4858 struct sk_buff *skb = skb_peek(&sk->sk_receive_queue); 4859 tp->copied_seq++; 4860 if (skb && !before(tp->copied_seq, TCP_SKB_CB(skb)->end_seq)) { 4861 __skb_unlink(skb, &sk->sk_receive_queue); 4862 __kfree_skb(skb); 4863 } 4864 } 4865 4866 tp->urg_data = TCP_URG_NOTYET; 4867 tp->urg_seq = ptr; 4868 4869 /* Disable header prediction. */ 4870 tp->pred_flags = 0; 4871 } 4872 4873 /* This is the 'fast' part of urgent handling. */ 4874 static void tcp_urg(struct sock *sk, struct sk_buff *skb, const struct tcphdr *th) 4875 { 4876 struct tcp_sock *tp = tcp_sk(sk); 4877 4878 /* Check if we get a new urgent pointer - normally not. */ 4879 if (th->urg) 4880 tcp_check_urg(sk, th); 4881 4882 /* Do we wait for any urgent data? - normally not... */ 4883 if (tp->urg_data == TCP_URG_NOTYET) { 4884 u32 ptr = tp->urg_seq - ntohl(th->seq) + (th->doff * 4) - 4885 th->syn; 4886 4887 /* Is the urgent pointer pointing into this packet? */ 4888 if (ptr < skb->len) { 4889 u8 tmp; 4890 if (skb_copy_bits(skb, ptr, &tmp, 1)) 4891 BUG(); 4892 tp->urg_data = TCP_URG_VALID | tmp; 4893 if (!sock_flag(sk, SOCK_DEAD)) 4894 sk->sk_data_ready(sk); 4895 } 4896 } 4897 } 4898 4899 static int tcp_copy_to_iovec(struct sock *sk, struct sk_buff *skb, int hlen) 4900 { 4901 struct tcp_sock *tp = tcp_sk(sk); 4902 int chunk = skb->len - hlen; 4903 int err; 4904 4905 local_bh_enable(); 4906 if (skb_csum_unnecessary(skb)) 4907 err = skb_copy_datagram_iovec(skb, hlen, tp->ucopy.iov, chunk); 4908 else 4909 err = skb_copy_and_csum_datagram_iovec(skb, hlen, 4910 tp->ucopy.iov); 4911 4912 if (!err) { 4913 tp->ucopy.len -= chunk; 4914 tp->copied_seq += chunk; 4915 tcp_rcv_space_adjust(sk); 4916 } 4917 4918 local_bh_disable(); 4919 return err; 4920 } 4921 4922 static __sum16 __tcp_checksum_complete_user(struct sock *sk, 4923 struct sk_buff *skb) 4924 { 4925 __sum16 result; 4926 4927 if (sock_owned_by_user(sk)) { 4928 local_bh_enable(); 4929 result = __tcp_checksum_complete(skb); 4930 local_bh_disable(); 4931 } else { 4932 result = __tcp_checksum_complete(skb); 4933 } 4934 return result; 4935 } 4936 4937 static inline bool tcp_checksum_complete_user(struct sock *sk, 4938 struct sk_buff *skb) 4939 { 4940 return !skb_csum_unnecessary(skb) && 4941 __tcp_checksum_complete_user(sk, skb); 4942 } 4943 4944 #ifdef CONFIG_NET_DMA 4945 static bool tcp_dma_try_early_copy(struct sock *sk, struct sk_buff *skb, 4946 int hlen) 4947 { 4948 struct tcp_sock *tp = tcp_sk(sk); 4949 int chunk = skb->len - hlen; 4950 int dma_cookie; 4951 bool copied_early = false; 4952 4953 if (tp->ucopy.wakeup) 4954 return false; 4955 4956 if (!tp->ucopy.dma_chan && tp->ucopy.pinned_list) 4957 tp->ucopy.dma_chan = net_dma_find_channel(); 4958 4959 if (tp->ucopy.dma_chan && skb_csum_unnecessary(skb)) { 4960 4961 dma_cookie = dma_skb_copy_datagram_iovec(tp->ucopy.dma_chan, 4962 skb, hlen, 4963 tp->ucopy.iov, chunk, 4964 tp->ucopy.pinned_list); 4965 4966 if (dma_cookie < 0) 4967 goto out; 4968 4969 tp->ucopy.dma_cookie = dma_cookie; 4970 copied_early = true; 4971 4972 tp->ucopy.len -= chunk; 4973 tp->copied_seq += chunk; 4974 tcp_rcv_space_adjust(sk); 4975 4976 if ((tp->ucopy.len == 0) || 4977 (tcp_flag_word(tcp_hdr(skb)) & TCP_FLAG_PSH) || 4978 (atomic_read(&sk->sk_rmem_alloc) > (sk->sk_rcvbuf >> 1))) { 4979 tp->ucopy.wakeup = 1; 4980 sk->sk_data_ready(sk); 4981 } 4982 } else if (chunk > 0) { 4983 tp->ucopy.wakeup = 1; 4984 sk->sk_data_ready(sk); 4985 } 4986 out: 4987 return copied_early; 4988 } 4989 #endif /* CONFIG_NET_DMA */ 4990 4991 /* Does PAWS and seqno based validation of an incoming segment, flags will 4992 * play significant role here. 4993 */ 4994 static bool tcp_validate_incoming(struct sock *sk, struct sk_buff *skb, 4995 const struct tcphdr *th, int syn_inerr) 4996 { 4997 struct tcp_sock *tp = tcp_sk(sk); 4998 4999 /* RFC1323: H1. Apply PAWS check first. */ 5000 if (tcp_fast_parse_options(skb, th, tp) && tp->rx_opt.saw_tstamp && 5001 tcp_paws_discard(sk, skb)) { 5002 if (!th->rst) { 5003 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PAWSESTABREJECTED); 5004 tcp_send_dupack(sk, skb); 5005 goto discard; 5006 } 5007 /* Reset is accepted even if it did not pass PAWS. */ 5008 } 5009 5010 /* Step 1: check sequence number */ 5011 if (!tcp_sequence(tp, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq)) { 5012 /* RFC793, page 37: "In all states except SYN-SENT, all reset 5013 * (RST) segments are validated by checking their SEQ-fields." 5014 * And page 69: "If an incoming segment is not acceptable, 5015 * an acknowledgment should be sent in reply (unless the RST 5016 * bit is set, if so drop the segment and return)". 5017 */ 5018 if (!th->rst) { 5019 if (th->syn) 5020 goto syn_challenge; 5021 tcp_send_dupack(sk, skb); 5022 } 5023 goto discard; 5024 } 5025 5026 /* Step 2: check RST bit */ 5027 if (th->rst) { 5028 /* RFC 5961 3.2 : 5029 * If sequence number exactly matches RCV.NXT, then 5030 * RESET the connection 5031 * else 5032 * Send a challenge ACK 5033 */ 5034 if (TCP_SKB_CB(skb)->seq == tp->rcv_nxt) 5035 tcp_reset(sk); 5036 else 5037 tcp_send_challenge_ack(sk); 5038 goto discard; 5039 } 5040 5041 /* step 3: check security and precedence [ignored] */ 5042 5043 /* step 4: Check for a SYN 5044 * RFC 5691 4.2 : Send a challenge ack 5045 */ 5046 if (th->syn) { 5047 syn_challenge: 5048 if (syn_inerr) 5049 TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS); 5050 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPSYNCHALLENGE); 5051 tcp_send_challenge_ack(sk); 5052 goto discard; 5053 } 5054 5055 return true; 5056 5057 discard: 5058 __kfree_skb(skb); 5059 return false; 5060 } 5061 5062 /* 5063 * TCP receive function for the ESTABLISHED state. 5064 * 5065 * It is split into a fast path and a slow path. The fast path is 5066 * disabled when: 5067 * - A zero window was announced from us - zero window probing 5068 * is only handled properly in the slow path. 5069 * - Out of order segments arrived. 5070 * - Urgent data is expected. 5071 * - There is no buffer space left 5072 * - Unexpected TCP flags/window values/header lengths are received 5073 * (detected by checking the TCP header against pred_flags) 5074 * - Data is sent in both directions. Fast path only supports pure senders 5075 * or pure receivers (this means either the sequence number or the ack 5076 * value must stay constant) 5077 * - Unexpected TCP option. 5078 * 5079 * When these conditions are not satisfied it drops into a standard 5080 * receive procedure patterned after RFC793 to handle all cases. 5081 * The first three cases are guaranteed by proper pred_flags setting, 5082 * the rest is checked inline. Fast processing is turned on in 5083 * tcp_data_queue when everything is OK. 5084 */ 5085 void tcp_rcv_established(struct sock *sk, struct sk_buff *skb, 5086 const struct tcphdr *th, unsigned int len) 5087 { 5088 struct tcp_sock *tp = tcp_sk(sk); 5089 5090 if (unlikely(sk->sk_rx_dst == NULL)) 5091 inet_csk(sk)->icsk_af_ops->sk_rx_dst_set(sk, skb); 5092 /* 5093 * Header prediction. 5094 * The code loosely follows the one in the famous 5095 * "30 instruction TCP receive" Van Jacobson mail. 5096 * 5097 * Van's trick is to deposit buffers into socket queue 5098 * on a device interrupt, to call tcp_recv function 5099 * on the receive process context and checksum and copy 5100 * the buffer to user space. smart... 5101 * 5102 * Our current scheme is not silly either but we take the 5103 * extra cost of the net_bh soft interrupt processing... 5104 * We do checksum and copy also but from device to kernel. 5105 */ 5106 5107 tp->rx_opt.saw_tstamp = 0; 5108 5109 /* pred_flags is 0xS?10 << 16 + snd_wnd 5110 * if header_prediction is to be made 5111 * 'S' will always be tp->tcp_header_len >> 2 5112 * '?' will be 0 for the fast path, otherwise pred_flags is 0 to 5113 * turn it off (when there are holes in the receive 5114 * space for instance) 5115 * PSH flag is ignored. 5116 */ 5117 5118 if ((tcp_flag_word(th) & TCP_HP_BITS) == tp->pred_flags && 5119 TCP_SKB_CB(skb)->seq == tp->rcv_nxt && 5120 !after(TCP_SKB_CB(skb)->ack_seq, tp->snd_nxt)) { 5121 int tcp_header_len = tp->tcp_header_len; 5122 5123 /* Timestamp header prediction: tcp_header_len 5124 * is automatically equal to th->doff*4 due to pred_flags 5125 * match. 5126 */ 5127 5128 /* Check timestamp */ 5129 if (tcp_header_len == sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) { 5130 /* No? Slow path! */ 5131 if (!tcp_parse_aligned_timestamp(tp, th)) 5132 goto slow_path; 5133 5134 /* If PAWS failed, check it more carefully in slow path */ 5135 if ((s32)(tp->rx_opt.rcv_tsval - tp->rx_opt.ts_recent) < 0) 5136 goto slow_path; 5137 5138 /* DO NOT update ts_recent here, if checksum fails 5139 * and timestamp was corrupted part, it will result 5140 * in a hung connection since we will drop all 5141 * future packets due to the PAWS test. 5142 */ 5143 } 5144 5145 if (len <= tcp_header_len) { 5146 /* Bulk data transfer: sender */ 5147 if (len == tcp_header_len) { 5148 /* Predicted packet is in window by definition. 5149 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 5150 * Hence, check seq<=rcv_wup reduces to: 5151 */ 5152 if (tcp_header_len == 5153 (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) && 5154 tp->rcv_nxt == tp->rcv_wup) 5155 tcp_store_ts_recent(tp); 5156 5157 /* We know that such packets are checksummed 5158 * on entry. 5159 */ 5160 tcp_ack(sk, skb, 0); 5161 __kfree_skb(skb); 5162 tcp_data_snd_check(sk); 5163 return; 5164 } else { /* Header too small */ 5165 TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS); 5166 goto discard; 5167 } 5168 } else { 5169 int eaten = 0; 5170 int copied_early = 0; 5171 bool fragstolen = false; 5172 5173 if (tp->copied_seq == tp->rcv_nxt && 5174 len - tcp_header_len <= tp->ucopy.len) { 5175 #ifdef CONFIG_NET_DMA 5176 if (tp->ucopy.task == current && 5177 sock_owned_by_user(sk) && 5178 tcp_dma_try_early_copy(sk, skb, tcp_header_len)) { 5179 copied_early = 1; 5180 eaten = 1; 5181 } 5182 #endif 5183 if (tp->ucopy.task == current && 5184 sock_owned_by_user(sk) && !copied_early) { 5185 __set_current_state(TASK_RUNNING); 5186 5187 if (!tcp_copy_to_iovec(sk, skb, tcp_header_len)) 5188 eaten = 1; 5189 } 5190 if (eaten) { 5191 /* Predicted packet is in window by definition. 5192 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 5193 * Hence, check seq<=rcv_wup reduces to: 5194 */ 5195 if (tcp_header_len == 5196 (sizeof(struct tcphdr) + 5197 TCPOLEN_TSTAMP_ALIGNED) && 5198 tp->rcv_nxt == tp->rcv_wup) 5199 tcp_store_ts_recent(tp); 5200 5201 tcp_rcv_rtt_measure_ts(sk, skb); 5202 5203 __skb_pull(skb, tcp_header_len); 5204 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 5205 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPHITSTOUSER); 5206 } 5207 if (copied_early) 5208 tcp_cleanup_rbuf(sk, skb->len); 5209 } 5210 if (!eaten) { 5211 if (tcp_checksum_complete_user(sk, skb)) 5212 goto csum_error; 5213 5214 if ((int)skb->truesize > sk->sk_forward_alloc) 5215 goto step5; 5216 5217 /* Predicted packet is in window by definition. 5218 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 5219 * Hence, check seq<=rcv_wup reduces to: 5220 */ 5221 if (tcp_header_len == 5222 (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) && 5223 tp->rcv_nxt == tp->rcv_wup) 5224 tcp_store_ts_recent(tp); 5225 5226 tcp_rcv_rtt_measure_ts(sk, skb); 5227 5228 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPHITS); 5229 5230 /* Bulk data transfer: receiver */ 5231 eaten = tcp_queue_rcv(sk, skb, tcp_header_len, 5232 &fragstolen); 5233 } 5234 5235 tcp_event_data_recv(sk, skb); 5236 5237 if (TCP_SKB_CB(skb)->ack_seq != tp->snd_una) { 5238 /* Well, only one small jumplet in fast path... */ 5239 tcp_ack(sk, skb, FLAG_DATA); 5240 tcp_data_snd_check(sk); 5241 if (!inet_csk_ack_scheduled(sk)) 5242 goto no_ack; 5243 } 5244 5245 if (!copied_early || tp->rcv_nxt != tp->rcv_wup) 5246 __tcp_ack_snd_check(sk, 0); 5247 no_ack: 5248 #ifdef CONFIG_NET_DMA 5249 if (copied_early) 5250 __skb_queue_tail(&sk->sk_async_wait_queue, skb); 5251 else 5252 #endif 5253 if (eaten) 5254 kfree_skb_partial(skb, fragstolen); 5255 sk->sk_data_ready(sk); 5256 return; 5257 } 5258 } 5259 5260 slow_path: 5261 if (len < (th->doff << 2) || tcp_checksum_complete_user(sk, skb)) 5262 goto csum_error; 5263 5264 if (!th->ack && !th->rst) 5265 goto discard; 5266 5267 /* 5268 * Standard slow path. 5269 */ 5270 5271 if (!tcp_validate_incoming(sk, skb, th, 1)) 5272 return; 5273 5274 step5: 5275 if (tcp_ack(sk, skb, FLAG_SLOWPATH | FLAG_UPDATE_TS_RECENT) < 0) 5276 goto discard; 5277 5278 tcp_rcv_rtt_measure_ts(sk, skb); 5279 5280 /* Process urgent data. */ 5281 tcp_urg(sk, skb, th); 5282 5283 /* step 7: process the segment text */ 5284 tcp_data_queue(sk, skb); 5285 5286 tcp_data_snd_check(sk); 5287 tcp_ack_snd_check(sk); 5288 return; 5289 5290 csum_error: 5291 TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_CSUMERRORS); 5292 TCP_INC_STATS_BH(sock_net(sk), TCP_MIB_INERRS); 5293 5294 discard: 5295 __kfree_skb(skb); 5296 } 5297 EXPORT_SYMBOL(tcp_rcv_established); 5298 5299 void tcp_finish_connect(struct sock *sk, struct sk_buff *skb) 5300 { 5301 struct tcp_sock *tp = tcp_sk(sk); 5302 struct inet_connection_sock *icsk = inet_csk(sk); 5303 5304 tcp_set_state(sk, TCP_ESTABLISHED); 5305 5306 if (skb != NULL) { 5307 icsk->icsk_af_ops->sk_rx_dst_set(sk, skb); 5308 security_inet_conn_established(sk, skb); 5309 } 5310 5311 /* Make sure socket is routed, for correct metrics. */ 5312 icsk->icsk_af_ops->rebuild_header(sk); 5313 5314 tcp_init_metrics(sk); 5315 5316 tcp_init_congestion_control(sk); 5317 5318 /* Prevent spurious tcp_cwnd_restart() on first data 5319 * packet. 5320 */ 5321 tp->lsndtime = tcp_time_stamp; 5322 5323 tcp_init_buffer_space(sk); 5324 5325 if (sock_flag(sk, SOCK_KEEPOPEN)) 5326 inet_csk_reset_keepalive_timer(sk, keepalive_time_when(tp)); 5327 5328 if (!tp->rx_opt.snd_wscale) 5329 __tcp_fast_path_on(tp, tp->snd_wnd); 5330 else 5331 tp->pred_flags = 0; 5332 5333 if (!sock_flag(sk, SOCK_DEAD)) { 5334 sk->sk_state_change(sk); 5335 sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT); 5336 } 5337 } 5338 5339 static bool tcp_rcv_fastopen_synack(struct sock *sk, struct sk_buff *synack, 5340 struct tcp_fastopen_cookie *cookie) 5341 { 5342 struct tcp_sock *tp = tcp_sk(sk); 5343 struct sk_buff *data = tp->syn_data ? tcp_write_queue_head(sk) : NULL; 5344 u16 mss = tp->rx_opt.mss_clamp; 5345 bool syn_drop; 5346 5347 if (mss == tp->rx_opt.user_mss) { 5348 struct tcp_options_received opt; 5349 5350 /* Get original SYNACK MSS value if user MSS sets mss_clamp */ 5351 tcp_clear_options(&opt); 5352 opt.user_mss = opt.mss_clamp = 0; 5353 tcp_parse_options(synack, &opt, 0, NULL); 5354 mss = opt.mss_clamp; 5355 } 5356 5357 if (!tp->syn_fastopen) /* Ignore an unsolicited cookie */ 5358 cookie->len = -1; 5359 5360 /* The SYN-ACK neither has cookie nor acknowledges the data. Presumably 5361 * the remote receives only the retransmitted (regular) SYNs: either 5362 * the original SYN-data or the corresponding SYN-ACK is lost. 5363 */ 5364 syn_drop = (cookie->len <= 0 && data && tp->total_retrans); 5365 5366 tcp_fastopen_cache_set(sk, mss, cookie, syn_drop); 5367 5368 if (data) { /* Retransmit unacked data in SYN */ 5369 tcp_for_write_queue_from(data, sk) { 5370 if (data == tcp_send_head(sk) || 5371 __tcp_retransmit_skb(sk, data)) 5372 break; 5373 } 5374 tcp_rearm_rto(sk); 5375 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPFASTOPENACTIVEFAIL); 5376 return true; 5377 } 5378 tp->syn_data_acked = tp->syn_data; 5379 if (tp->syn_data_acked) 5380 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPFASTOPENACTIVE); 5381 return false; 5382 } 5383 5384 static int tcp_rcv_synsent_state_process(struct sock *sk, struct sk_buff *skb, 5385 const struct tcphdr *th, unsigned int len) 5386 { 5387 struct inet_connection_sock *icsk = inet_csk(sk); 5388 struct tcp_sock *tp = tcp_sk(sk); 5389 struct tcp_fastopen_cookie foc = { .len = -1 }; 5390 int saved_clamp = tp->rx_opt.mss_clamp; 5391 5392 tcp_parse_options(skb, &tp->rx_opt, 0, &foc); 5393 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr) 5394 tp->rx_opt.rcv_tsecr -= tp->tsoffset; 5395 5396 if (th->ack) { 5397 /* rfc793: 5398 * "If the state is SYN-SENT then 5399 * first check the ACK bit 5400 * If the ACK bit is set 5401 * If SEG.ACK =< ISS, or SEG.ACK > SND.NXT, send 5402 * a reset (unless the RST bit is set, if so drop 5403 * the segment and return)" 5404 */ 5405 if (!after(TCP_SKB_CB(skb)->ack_seq, tp->snd_una) || 5406 after(TCP_SKB_CB(skb)->ack_seq, tp->snd_nxt)) 5407 goto reset_and_undo; 5408 5409 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 5410 !between(tp->rx_opt.rcv_tsecr, tp->retrans_stamp, 5411 tcp_time_stamp)) { 5412 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_PAWSACTIVEREJECTED); 5413 goto reset_and_undo; 5414 } 5415 5416 /* Now ACK is acceptable. 5417 * 5418 * "If the RST bit is set 5419 * If the ACK was acceptable then signal the user "error: 5420 * connection reset", drop the segment, enter CLOSED state, 5421 * delete TCB, and return." 5422 */ 5423 5424 if (th->rst) { 5425 tcp_reset(sk); 5426 goto discard; 5427 } 5428 5429 /* rfc793: 5430 * "fifth, if neither of the SYN or RST bits is set then 5431 * drop the segment and return." 5432 * 5433 * See note below! 5434 * --ANK(990513) 5435 */ 5436 if (!th->syn) 5437 goto discard_and_undo; 5438 5439 /* rfc793: 5440 * "If the SYN bit is on ... 5441 * are acceptable then ... 5442 * (our SYN has been ACKed), change the connection 5443 * state to ESTABLISHED..." 5444 */ 5445 5446 TCP_ECN_rcv_synack(tp, th); 5447 5448 tcp_init_wl(tp, TCP_SKB_CB(skb)->seq); 5449 tcp_ack(sk, skb, FLAG_SLOWPATH); 5450 5451 /* Ok.. it's good. Set up sequence numbers and 5452 * move to established. 5453 */ 5454 tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1; 5455 tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1; 5456 5457 /* RFC1323: The window in SYN & SYN/ACK segments is 5458 * never scaled. 5459 */ 5460 tp->snd_wnd = ntohs(th->window); 5461 5462 if (!tp->rx_opt.wscale_ok) { 5463 tp->rx_opt.snd_wscale = tp->rx_opt.rcv_wscale = 0; 5464 tp->window_clamp = min(tp->window_clamp, 65535U); 5465 } 5466 5467 if (tp->rx_opt.saw_tstamp) { 5468 tp->rx_opt.tstamp_ok = 1; 5469 tp->tcp_header_len = 5470 sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED; 5471 tp->advmss -= TCPOLEN_TSTAMP_ALIGNED; 5472 tcp_store_ts_recent(tp); 5473 } else { 5474 tp->tcp_header_len = sizeof(struct tcphdr); 5475 } 5476 5477 if (tcp_is_sack(tp) && sysctl_tcp_fack) 5478 tcp_enable_fack(tp); 5479 5480 tcp_mtup_init(sk); 5481 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 5482 tcp_initialize_rcv_mss(sk); 5483 5484 /* Remember, tcp_poll() does not lock socket! 5485 * Change state from SYN-SENT only after copied_seq 5486 * is initialized. */ 5487 tp->copied_seq = tp->rcv_nxt; 5488 5489 smp_mb(); 5490 5491 tcp_finish_connect(sk, skb); 5492 5493 if ((tp->syn_fastopen || tp->syn_data) && 5494 tcp_rcv_fastopen_synack(sk, skb, &foc)) 5495 return -1; 5496 5497 if (sk->sk_write_pending || 5498 icsk->icsk_accept_queue.rskq_defer_accept || 5499 icsk->icsk_ack.pingpong) { 5500 /* Save one ACK. Data will be ready after 5501 * several ticks, if write_pending is set. 5502 * 5503 * It may be deleted, but with this feature tcpdumps 5504 * look so _wonderfully_ clever, that I was not able 5505 * to stand against the temptation 8) --ANK 5506 */ 5507 inet_csk_schedule_ack(sk); 5508 icsk->icsk_ack.lrcvtime = tcp_time_stamp; 5509 tcp_enter_quickack_mode(sk); 5510 inet_csk_reset_xmit_timer(sk, ICSK_TIME_DACK, 5511 TCP_DELACK_MAX, TCP_RTO_MAX); 5512 5513 discard: 5514 __kfree_skb(skb); 5515 return 0; 5516 } else { 5517 tcp_send_ack(sk); 5518 } 5519 return -1; 5520 } 5521 5522 /* No ACK in the segment */ 5523 5524 if (th->rst) { 5525 /* rfc793: 5526 * "If the RST bit is set 5527 * 5528 * Otherwise (no ACK) drop the segment and return." 5529 */ 5530 5531 goto discard_and_undo; 5532 } 5533 5534 /* PAWS check. */ 5535 if (tp->rx_opt.ts_recent_stamp && tp->rx_opt.saw_tstamp && 5536 tcp_paws_reject(&tp->rx_opt, 0)) 5537 goto discard_and_undo; 5538 5539 if (th->syn) { 5540 /* We see SYN without ACK. It is attempt of 5541 * simultaneous connect with crossed SYNs. 5542 * Particularly, it can be connect to self. 5543 */ 5544 tcp_set_state(sk, TCP_SYN_RECV); 5545 5546 if (tp->rx_opt.saw_tstamp) { 5547 tp->rx_opt.tstamp_ok = 1; 5548 tcp_store_ts_recent(tp); 5549 tp->tcp_header_len = 5550 sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED; 5551 } else { 5552 tp->tcp_header_len = sizeof(struct tcphdr); 5553 } 5554 5555 tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1; 5556 tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1; 5557 5558 /* RFC1323: The window in SYN & SYN/ACK segments is 5559 * never scaled. 5560 */ 5561 tp->snd_wnd = ntohs(th->window); 5562 tp->snd_wl1 = TCP_SKB_CB(skb)->seq; 5563 tp->max_window = tp->snd_wnd; 5564 5565 TCP_ECN_rcv_syn(tp, th); 5566 5567 tcp_mtup_init(sk); 5568 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 5569 tcp_initialize_rcv_mss(sk); 5570 5571 tcp_send_synack(sk); 5572 #if 0 5573 /* Note, we could accept data and URG from this segment. 5574 * There are no obstacles to make this (except that we must 5575 * either change tcp_recvmsg() to prevent it from returning data 5576 * before 3WHS completes per RFC793, or employ TCP Fast Open). 5577 * 5578 * However, if we ignore data in ACKless segments sometimes, 5579 * we have no reasons to accept it sometimes. 5580 * Also, seems the code doing it in step6 of tcp_rcv_state_process 5581 * is not flawless. So, discard packet for sanity. 5582 * Uncomment this return to process the data. 5583 */ 5584 return -1; 5585 #else 5586 goto discard; 5587 #endif 5588 } 5589 /* "fifth, if neither of the SYN or RST bits is set then 5590 * drop the segment and return." 5591 */ 5592 5593 discard_and_undo: 5594 tcp_clear_options(&tp->rx_opt); 5595 tp->rx_opt.mss_clamp = saved_clamp; 5596 goto discard; 5597 5598 reset_and_undo: 5599 tcp_clear_options(&tp->rx_opt); 5600 tp->rx_opt.mss_clamp = saved_clamp; 5601 return 1; 5602 } 5603 5604 /* 5605 * This function implements the receiving procedure of RFC 793 for 5606 * all states except ESTABLISHED and TIME_WAIT. 5607 * It's called from both tcp_v4_rcv and tcp_v6_rcv and should be 5608 * address independent. 5609 */ 5610 5611 int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb, 5612 const struct tcphdr *th, unsigned int len) 5613 { 5614 struct tcp_sock *tp = tcp_sk(sk); 5615 struct inet_connection_sock *icsk = inet_csk(sk); 5616 struct request_sock *req; 5617 int queued = 0; 5618 bool acceptable; 5619 u32 synack_stamp; 5620 5621 tp->rx_opt.saw_tstamp = 0; 5622 5623 switch (sk->sk_state) { 5624 case TCP_CLOSE: 5625 goto discard; 5626 5627 case TCP_LISTEN: 5628 if (th->ack) 5629 return 1; 5630 5631 if (th->rst) 5632 goto discard; 5633 5634 if (th->syn) { 5635 if (th->fin) 5636 goto discard; 5637 if (icsk->icsk_af_ops->conn_request(sk, skb) < 0) 5638 return 1; 5639 5640 /* Now we have several options: In theory there is 5641 * nothing else in the frame. KA9Q has an option to 5642 * send data with the syn, BSD accepts data with the 5643 * syn up to the [to be] advertised window and 5644 * Solaris 2.1 gives you a protocol error. For now 5645 * we just ignore it, that fits the spec precisely 5646 * and avoids incompatibilities. It would be nice in 5647 * future to drop through and process the data. 5648 * 5649 * Now that TTCP is starting to be used we ought to 5650 * queue this data. 5651 * But, this leaves one open to an easy denial of 5652 * service attack, and SYN cookies can't defend 5653 * against this problem. So, we drop the data 5654 * in the interest of security over speed unless 5655 * it's still in use. 5656 */ 5657 kfree_skb(skb); 5658 return 0; 5659 } 5660 goto discard; 5661 5662 case TCP_SYN_SENT: 5663 queued = tcp_rcv_synsent_state_process(sk, skb, th, len); 5664 if (queued >= 0) 5665 return queued; 5666 5667 /* Do step6 onward by hand. */ 5668 tcp_urg(sk, skb, th); 5669 __kfree_skb(skb); 5670 tcp_data_snd_check(sk); 5671 return 0; 5672 } 5673 5674 req = tp->fastopen_rsk; 5675 if (req != NULL) { 5676 WARN_ON_ONCE(sk->sk_state != TCP_SYN_RECV && 5677 sk->sk_state != TCP_FIN_WAIT1); 5678 5679 if (tcp_check_req(sk, skb, req, NULL, true) == NULL) 5680 goto discard; 5681 } 5682 5683 if (!th->ack && !th->rst) 5684 goto discard; 5685 5686 if (!tcp_validate_incoming(sk, skb, th, 0)) 5687 return 0; 5688 5689 /* step 5: check the ACK field */ 5690 acceptable = tcp_ack(sk, skb, FLAG_SLOWPATH | 5691 FLAG_UPDATE_TS_RECENT) > 0; 5692 5693 switch (sk->sk_state) { 5694 case TCP_SYN_RECV: 5695 if (!acceptable) 5696 return 1; 5697 5698 /* Once we leave TCP_SYN_RECV, we no longer need req 5699 * so release it. 5700 */ 5701 if (req) { 5702 synack_stamp = tcp_rsk(req)->snt_synack; 5703 tp->total_retrans = req->num_retrans; 5704 reqsk_fastopen_remove(sk, req, false); 5705 } else { 5706 synack_stamp = tp->lsndtime; 5707 /* Make sure socket is routed, for correct metrics. */ 5708 icsk->icsk_af_ops->rebuild_header(sk); 5709 tcp_init_congestion_control(sk); 5710 5711 tcp_mtup_init(sk); 5712 tp->copied_seq = tp->rcv_nxt; 5713 tcp_init_buffer_space(sk); 5714 } 5715 smp_mb(); 5716 tcp_set_state(sk, TCP_ESTABLISHED); 5717 sk->sk_state_change(sk); 5718 5719 /* Note, that this wakeup is only for marginal crossed SYN case. 5720 * Passively open sockets are not waked up, because 5721 * sk->sk_sleep == NULL and sk->sk_socket == NULL. 5722 */ 5723 if (sk->sk_socket) 5724 sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT); 5725 5726 tp->snd_una = TCP_SKB_CB(skb)->ack_seq; 5727 tp->snd_wnd = ntohs(th->window) << tp->rx_opt.snd_wscale; 5728 tcp_init_wl(tp, TCP_SKB_CB(skb)->seq); 5729 tcp_synack_rtt_meas(sk, synack_stamp); 5730 5731 if (tp->rx_opt.tstamp_ok) 5732 tp->advmss -= TCPOLEN_TSTAMP_ALIGNED; 5733 5734 if (req) { 5735 /* Re-arm the timer because data may have been sent out. 5736 * This is similar to the regular data transmission case 5737 * when new data has just been ack'ed. 5738 * 5739 * (TFO) - we could try to be more aggressive and 5740 * retransmitting any data sooner based on when they 5741 * are sent out. 5742 */ 5743 tcp_rearm_rto(sk); 5744 } else 5745 tcp_init_metrics(sk); 5746 5747 tcp_update_pacing_rate(sk); 5748 5749 /* Prevent spurious tcp_cwnd_restart() on first data packet */ 5750 tp->lsndtime = tcp_time_stamp; 5751 5752 tcp_initialize_rcv_mss(sk); 5753 tcp_fast_path_on(tp); 5754 break; 5755 5756 case TCP_FIN_WAIT1: { 5757 struct dst_entry *dst; 5758 int tmo; 5759 5760 /* If we enter the TCP_FIN_WAIT1 state and we are a 5761 * Fast Open socket and this is the first acceptable 5762 * ACK we have received, this would have acknowledged 5763 * our SYNACK so stop the SYNACK timer. 5764 */ 5765 if (req != NULL) { 5766 /* Return RST if ack_seq is invalid. 5767 * Note that RFC793 only says to generate a 5768 * DUPACK for it but for TCP Fast Open it seems 5769 * better to treat this case like TCP_SYN_RECV 5770 * above. 5771 */ 5772 if (!acceptable) 5773 return 1; 5774 /* We no longer need the request sock. */ 5775 reqsk_fastopen_remove(sk, req, false); 5776 tcp_rearm_rto(sk); 5777 } 5778 if (tp->snd_una != tp->write_seq) 5779 break; 5780 5781 tcp_set_state(sk, TCP_FIN_WAIT2); 5782 sk->sk_shutdown |= SEND_SHUTDOWN; 5783 5784 dst = __sk_dst_get(sk); 5785 if (dst) 5786 dst_confirm(dst); 5787 5788 if (!sock_flag(sk, SOCK_DEAD)) { 5789 /* Wake up lingering close() */ 5790 sk->sk_state_change(sk); 5791 break; 5792 } 5793 5794 if (tp->linger2 < 0 || 5795 (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 5796 after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt))) { 5797 tcp_done(sk); 5798 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPABORTONDATA); 5799 return 1; 5800 } 5801 5802 tmo = tcp_fin_time(sk); 5803 if (tmo > TCP_TIMEWAIT_LEN) { 5804 inet_csk_reset_keepalive_timer(sk, tmo - TCP_TIMEWAIT_LEN); 5805 } else if (th->fin || sock_owned_by_user(sk)) { 5806 /* Bad case. We could lose such FIN otherwise. 5807 * It is not a big problem, but it looks confusing 5808 * and not so rare event. We still can lose it now, 5809 * if it spins in bh_lock_sock(), but it is really 5810 * marginal case. 5811 */ 5812 inet_csk_reset_keepalive_timer(sk, tmo); 5813 } else { 5814 tcp_time_wait(sk, TCP_FIN_WAIT2, tmo); 5815 goto discard; 5816 } 5817 break; 5818 } 5819 5820 case TCP_CLOSING: 5821 if (tp->snd_una == tp->write_seq) { 5822 tcp_time_wait(sk, TCP_TIME_WAIT, 0); 5823 goto discard; 5824 } 5825 break; 5826 5827 case TCP_LAST_ACK: 5828 if (tp->snd_una == tp->write_seq) { 5829 tcp_update_metrics(sk); 5830 tcp_done(sk); 5831 goto discard; 5832 } 5833 break; 5834 } 5835 5836 /* step 6: check the URG bit */ 5837 tcp_urg(sk, skb, th); 5838 5839 /* step 7: process the segment text */ 5840 switch (sk->sk_state) { 5841 case TCP_CLOSE_WAIT: 5842 case TCP_CLOSING: 5843 case TCP_LAST_ACK: 5844 if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) 5845 break; 5846 case TCP_FIN_WAIT1: 5847 case TCP_FIN_WAIT2: 5848 /* RFC 793 says to queue data in these states, 5849 * RFC 1122 says we MUST send a reset. 5850 * BSD 4.4 also does reset. 5851 */ 5852 if (sk->sk_shutdown & RCV_SHUTDOWN) { 5853 if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 5854 after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt)) { 5855 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPABORTONDATA); 5856 tcp_reset(sk); 5857 return 1; 5858 } 5859 } 5860 /* Fall through */ 5861 case TCP_ESTABLISHED: 5862 tcp_data_queue(sk, skb); 5863 queued = 1; 5864 break; 5865 } 5866 5867 /* tcp_data could move socket to TIME-WAIT */ 5868 if (sk->sk_state != TCP_CLOSE) { 5869 tcp_data_snd_check(sk); 5870 tcp_ack_snd_check(sk); 5871 } 5872 5873 if (!queued) { 5874 discard: 5875 __kfree_skb(skb); 5876 } 5877 return 0; 5878 } 5879 EXPORT_SYMBOL(tcp_rcv_state_process); 5880