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