tcp_input.c revision 80246ab36ec8baf7d107254adb166baa555a59f8
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 * Version: $Id: tcp_input.c,v 1.243 2002/02/01 22:01:04 davem Exp $ 9 * 10 * Authors: Ross Biro 11 * Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG> 12 * Mark Evans, <evansmp@uhura.aston.ac.uk> 13 * Corey Minyard <wf-rch!minyard@relay.EU.net> 14 * Florian La Roche, <flla@stud.uni-sb.de> 15 * Charles Hedrick, <hedrick@klinzhai.rutgers.edu> 16 * Linus Torvalds, <torvalds@cs.helsinki.fi> 17 * Alan Cox, <gw4pts@gw4pts.ampr.org> 18 * Matthew Dillon, <dillon@apollo.west.oic.com> 19 * Arnt Gulbrandsen, <agulbra@nvg.unit.no> 20 * Jorge Cwik, <jorge@laser.satlink.net> 21 */ 22 23/* 24 * Changes: 25 * Pedro Roque : Fast Retransmit/Recovery. 26 * Two receive queues. 27 * Retransmit queue handled by TCP. 28 * Better retransmit timer handling. 29 * New congestion avoidance. 30 * Header prediction. 31 * Variable renaming. 32 * 33 * Eric : Fast Retransmit. 34 * Randy Scott : MSS option defines. 35 * Eric Schenk : Fixes to slow start algorithm. 36 * Eric Schenk : Yet another double ACK bug. 37 * Eric Schenk : Delayed ACK bug fixes. 38 * Eric Schenk : Floyd style fast retrans war avoidance. 39 * David S. Miller : Don't allow zero congestion window. 40 * Eric Schenk : Fix retransmitter so that it sends 41 * next packet on ack of previous packet. 42 * Andi Kleen : Moved open_request checking here 43 * and process RSTs for open_requests. 44 * Andi Kleen : Better prune_queue, and other fixes. 45 * Andrey Savochkin: Fix RTT measurements in the presence of 46 * timestamps. 47 * Andrey Savochkin: Check sequence numbers correctly when 48 * removing SACKs due to in sequence incoming 49 * data segments. 50 * Andi Kleen: Make sure we never ack data there is not 51 * enough room for. Also make this condition 52 * a fatal error if it might still happen. 53 * Andi Kleen: Add tcp_measure_rcv_mss to make 54 * connections with MSS<min(MTU,ann. MSS) 55 * work without delayed acks. 56 * Andi Kleen: Process packets with PSH set in the 57 * fast path. 58 * J Hadi Salim: ECN support 59 * Andrei Gurtov, 60 * Pasi Sarolahti, 61 * Panu Kuhlberg: Experimental audit of TCP (re)transmission 62 * engine. Lots of bugs are found. 63 * Pasi Sarolahti: F-RTO for dealing with spurious RTOs 64 */ 65 66#include <linux/mm.h> 67#include <linux/module.h> 68#include <linux/sysctl.h> 69#include <net/tcp.h> 70#include <net/inet_common.h> 71#include <linux/ipsec.h> 72#include <asm/unaligned.h> 73#include <net/netdma.h> 74 75int sysctl_tcp_timestamps __read_mostly = 1; 76int sysctl_tcp_window_scaling __read_mostly = 1; 77int sysctl_tcp_sack __read_mostly = 1; 78int sysctl_tcp_fack __read_mostly = 1; 79int sysctl_tcp_reordering __read_mostly = TCP_FASTRETRANS_THRESH; 80int sysctl_tcp_ecn __read_mostly; 81int sysctl_tcp_dsack __read_mostly = 1; 82int sysctl_tcp_app_win __read_mostly = 31; 83int sysctl_tcp_adv_win_scale __read_mostly = 2; 84 85int sysctl_tcp_stdurg __read_mostly; 86int sysctl_tcp_rfc1337 __read_mostly; 87int sysctl_tcp_max_orphans __read_mostly = NR_FILE; 88int sysctl_tcp_frto __read_mostly; 89int sysctl_tcp_nometrics_save __read_mostly; 90 91int sysctl_tcp_moderate_rcvbuf __read_mostly = 1; 92int sysctl_tcp_abc __read_mostly; 93 94#define FLAG_DATA 0x01 /* Incoming frame contained data. */ 95#define FLAG_WIN_UPDATE 0x02 /* Incoming ACK was a window update. */ 96#define FLAG_DATA_ACKED 0x04 /* This ACK acknowledged new data. */ 97#define FLAG_RETRANS_DATA_ACKED 0x08 /* "" "" some of which was retransmitted. */ 98#define FLAG_SYN_ACKED 0x10 /* This ACK acknowledged SYN. */ 99#define FLAG_DATA_SACKED 0x20 /* New SACK. */ 100#define FLAG_ECE 0x40 /* ECE in this ACK */ 101#define FLAG_DATA_LOST 0x80 /* SACK detected data lossage. */ 102#define FLAG_SLOWPATH 0x100 /* Do not skip RFC checks for window update.*/ 103 104#define FLAG_ACKED (FLAG_DATA_ACKED|FLAG_SYN_ACKED) 105#define FLAG_NOT_DUP (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED) 106#define FLAG_CA_ALERT (FLAG_DATA_SACKED|FLAG_ECE) 107#define FLAG_FORWARD_PROGRESS (FLAG_ACKED|FLAG_DATA_SACKED) 108 109#define IsReno(tp) ((tp)->rx_opt.sack_ok == 0) 110#define IsFack(tp) ((tp)->rx_opt.sack_ok & 2) 111#define IsDSack(tp) ((tp)->rx_opt.sack_ok & 4) 112 113#define TCP_REMNANT (TCP_FLAG_FIN|TCP_FLAG_URG|TCP_FLAG_SYN|TCP_FLAG_PSH) 114 115/* Adapt the MSS value used to make delayed ack decision to the 116 * real world. 117 */ 118static void tcp_measure_rcv_mss(struct sock *sk, 119 const struct sk_buff *skb) 120{ 121 struct inet_connection_sock *icsk = inet_csk(sk); 122 const unsigned int lss = icsk->icsk_ack.last_seg_size; 123 unsigned int len; 124 125 icsk->icsk_ack.last_seg_size = 0; 126 127 /* skb->len may jitter because of SACKs, even if peer 128 * sends good full-sized frames. 129 */ 130 len = skb_shinfo(skb)->gso_size ?: skb->len; 131 if (len >= icsk->icsk_ack.rcv_mss) { 132 icsk->icsk_ack.rcv_mss = len; 133 } else { 134 /* Otherwise, we make more careful check taking into account, 135 * that SACKs block is variable. 136 * 137 * "len" is invariant segment length, including TCP header. 138 */ 139 len += skb->data - skb->h.raw; 140 if (len >= TCP_MIN_RCVMSS + sizeof(struct tcphdr) || 141 /* If PSH is not set, packet should be 142 * full sized, provided peer TCP is not badly broken. 143 * This observation (if it is correct 8)) allows 144 * to handle super-low mtu links fairly. 145 */ 146 (len >= TCP_MIN_MSS + sizeof(struct tcphdr) && 147 !(tcp_flag_word(skb->h.th)&TCP_REMNANT))) { 148 /* Subtract also invariant (if peer is RFC compliant), 149 * tcp header plus fixed timestamp option length. 150 * Resulting "len" is MSS free of SACK jitter. 151 */ 152 len -= tcp_sk(sk)->tcp_header_len; 153 icsk->icsk_ack.last_seg_size = len; 154 if (len == lss) { 155 icsk->icsk_ack.rcv_mss = len; 156 return; 157 } 158 } 159 if (icsk->icsk_ack.pending & ICSK_ACK_PUSHED) 160 icsk->icsk_ack.pending |= ICSK_ACK_PUSHED2; 161 icsk->icsk_ack.pending |= ICSK_ACK_PUSHED; 162 } 163} 164 165static void tcp_incr_quickack(struct sock *sk) 166{ 167 struct inet_connection_sock *icsk = inet_csk(sk); 168 unsigned quickacks = tcp_sk(sk)->rcv_wnd / (2 * icsk->icsk_ack.rcv_mss); 169 170 if (quickacks==0) 171 quickacks=2; 172 if (quickacks > icsk->icsk_ack.quick) 173 icsk->icsk_ack.quick = min(quickacks, TCP_MAX_QUICKACKS); 174} 175 176void tcp_enter_quickack_mode(struct sock *sk) 177{ 178 struct inet_connection_sock *icsk = inet_csk(sk); 179 tcp_incr_quickack(sk); 180 icsk->icsk_ack.pingpong = 0; 181 icsk->icsk_ack.ato = TCP_ATO_MIN; 182} 183 184/* Send ACKs quickly, if "quick" count is not exhausted 185 * and the session is not interactive. 186 */ 187 188static inline int tcp_in_quickack_mode(const struct sock *sk) 189{ 190 const struct inet_connection_sock *icsk = inet_csk(sk); 191 return icsk->icsk_ack.quick && !icsk->icsk_ack.pingpong; 192} 193 194/* Buffer size and advertised window tuning. 195 * 196 * 1. Tuning sk->sk_sndbuf, when connection enters established state. 197 */ 198 199static void tcp_fixup_sndbuf(struct sock *sk) 200{ 201 int sndmem = tcp_sk(sk)->rx_opt.mss_clamp + MAX_TCP_HEADER + 16 + 202 sizeof(struct sk_buff); 203 204 if (sk->sk_sndbuf < 3 * sndmem) 205 sk->sk_sndbuf = min(3 * sndmem, sysctl_tcp_wmem[2]); 206} 207 208/* 2. Tuning advertised window (window_clamp, rcv_ssthresh) 209 * 210 * All tcp_full_space() is split to two parts: "network" buffer, allocated 211 * forward and advertised in receiver window (tp->rcv_wnd) and 212 * "application buffer", required to isolate scheduling/application 213 * latencies from network. 214 * window_clamp is maximal advertised window. It can be less than 215 * tcp_full_space(), in this case tcp_full_space() - window_clamp 216 * is reserved for "application" buffer. The less window_clamp is 217 * the smoother our behaviour from viewpoint of network, but the lower 218 * throughput and the higher sensitivity of the connection to losses. 8) 219 * 220 * rcv_ssthresh is more strict window_clamp used at "slow start" 221 * phase to predict further behaviour of this connection. 222 * It is used for two goals: 223 * - to enforce header prediction at sender, even when application 224 * requires some significant "application buffer". It is check #1. 225 * - to prevent pruning of receive queue because of misprediction 226 * of receiver window. Check #2. 227 * 228 * The scheme does not work when sender sends good segments opening 229 * window and then starts to feed us spaghetti. But it should work 230 * in common situations. Otherwise, we have to rely on queue collapsing. 231 */ 232 233/* Slow part of check#2. */ 234static int __tcp_grow_window(const struct sock *sk, struct tcp_sock *tp, 235 const struct sk_buff *skb) 236{ 237 /* Optimize this! */ 238 int truesize = tcp_win_from_space(skb->truesize)/2; 239 int window = tcp_win_from_space(sysctl_tcp_rmem[2])/2; 240 241 while (tp->rcv_ssthresh <= window) { 242 if (truesize <= skb->len) 243 return 2 * inet_csk(sk)->icsk_ack.rcv_mss; 244 245 truesize >>= 1; 246 window >>= 1; 247 } 248 return 0; 249} 250 251static void tcp_grow_window(struct sock *sk, struct tcp_sock *tp, 252 struct sk_buff *skb) 253{ 254 /* Check #1 */ 255 if (tp->rcv_ssthresh < tp->window_clamp && 256 (int)tp->rcv_ssthresh < tcp_space(sk) && 257 !tcp_memory_pressure) { 258 int incr; 259 260 /* Check #2. Increase window, if skb with such overhead 261 * will fit to rcvbuf in future. 262 */ 263 if (tcp_win_from_space(skb->truesize) <= skb->len) 264 incr = 2*tp->advmss; 265 else 266 incr = __tcp_grow_window(sk, tp, skb); 267 268 if (incr) { 269 tp->rcv_ssthresh = min(tp->rcv_ssthresh + incr, tp->window_clamp); 270 inet_csk(sk)->icsk_ack.quick |= 1; 271 } 272 } 273} 274 275/* 3. Tuning rcvbuf, when connection enters established state. */ 276 277static void tcp_fixup_rcvbuf(struct sock *sk) 278{ 279 struct tcp_sock *tp = tcp_sk(sk); 280 int rcvmem = tp->advmss + MAX_TCP_HEADER + 16 + sizeof(struct sk_buff); 281 282 /* Try to select rcvbuf so that 4 mss-sized segments 283 * will fit to window and corresponding skbs will fit to our rcvbuf. 284 * (was 3; 4 is minimum to allow fast retransmit to work.) 285 */ 286 while (tcp_win_from_space(rcvmem) < tp->advmss) 287 rcvmem += 128; 288 if (sk->sk_rcvbuf < 4 * rcvmem) 289 sk->sk_rcvbuf = min(4 * rcvmem, sysctl_tcp_rmem[2]); 290} 291 292/* 4. Try to fixup all. It is made immediately after connection enters 293 * established state. 294 */ 295static void tcp_init_buffer_space(struct sock *sk) 296{ 297 struct tcp_sock *tp = tcp_sk(sk); 298 int maxwin; 299 300 if (!(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) 301 tcp_fixup_rcvbuf(sk); 302 if (!(sk->sk_userlocks & SOCK_SNDBUF_LOCK)) 303 tcp_fixup_sndbuf(sk); 304 305 tp->rcvq_space.space = tp->rcv_wnd; 306 307 maxwin = tcp_full_space(sk); 308 309 if (tp->window_clamp >= maxwin) { 310 tp->window_clamp = maxwin; 311 312 if (sysctl_tcp_app_win && maxwin > 4 * tp->advmss) 313 tp->window_clamp = max(maxwin - 314 (maxwin >> sysctl_tcp_app_win), 315 4 * tp->advmss); 316 } 317 318 /* Force reservation of one segment. */ 319 if (sysctl_tcp_app_win && 320 tp->window_clamp > 2 * tp->advmss && 321 tp->window_clamp + tp->advmss > maxwin) 322 tp->window_clamp = max(2 * tp->advmss, maxwin - tp->advmss); 323 324 tp->rcv_ssthresh = min(tp->rcv_ssthresh, tp->window_clamp); 325 tp->snd_cwnd_stamp = tcp_time_stamp; 326} 327 328/* 5. Recalculate window clamp after socket hit its memory bounds. */ 329static void tcp_clamp_window(struct sock *sk, struct tcp_sock *tp) 330{ 331 struct inet_connection_sock *icsk = inet_csk(sk); 332 333 icsk->icsk_ack.quick = 0; 334 335 if (sk->sk_rcvbuf < sysctl_tcp_rmem[2] && 336 !(sk->sk_userlocks & SOCK_RCVBUF_LOCK) && 337 !tcp_memory_pressure && 338 atomic_read(&tcp_memory_allocated) < sysctl_tcp_mem[0]) { 339 sk->sk_rcvbuf = min(atomic_read(&sk->sk_rmem_alloc), 340 sysctl_tcp_rmem[2]); 341 } 342 if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf) 343 tp->rcv_ssthresh = min(tp->window_clamp, 2U*tp->advmss); 344} 345 346 347/* Initialize RCV_MSS value. 348 * RCV_MSS is an our guess about MSS used by the peer. 349 * We haven't any direct information about the MSS. 350 * It's better to underestimate the RCV_MSS rather than overestimate. 351 * Overestimations make us ACKing less frequently than needed. 352 * Underestimations are more easy to detect and fix by tcp_measure_rcv_mss(). 353 */ 354void tcp_initialize_rcv_mss(struct sock *sk) 355{ 356 struct tcp_sock *tp = tcp_sk(sk); 357 unsigned int hint = min_t(unsigned int, tp->advmss, tp->mss_cache); 358 359 hint = min(hint, tp->rcv_wnd/2); 360 hint = min(hint, TCP_MIN_RCVMSS); 361 hint = max(hint, TCP_MIN_MSS); 362 363 inet_csk(sk)->icsk_ack.rcv_mss = hint; 364} 365 366/* Receiver "autotuning" code. 367 * 368 * The algorithm for RTT estimation w/o timestamps is based on 369 * Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL. 370 * <http://www.lanl.gov/radiant/website/pubs/drs/lacsi2001.ps> 371 * 372 * More detail on this code can be found at 373 * <http://www.psc.edu/~jheffner/senior_thesis.ps>, 374 * though this reference is out of date. A new paper 375 * is pending. 376 */ 377static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep) 378{ 379 u32 new_sample = tp->rcv_rtt_est.rtt; 380 long m = sample; 381 382 if (m == 0) 383 m = 1; 384 385 if (new_sample != 0) { 386 /* If we sample in larger samples in the non-timestamp 387 * case, we could grossly overestimate the RTT especially 388 * with chatty applications or bulk transfer apps which 389 * are stalled on filesystem I/O. 390 * 391 * Also, since we are only going for a minimum in the 392 * non-timestamp case, we do not smooth things out 393 * else with timestamps disabled convergence takes too 394 * long. 395 */ 396 if (!win_dep) { 397 m -= (new_sample >> 3); 398 new_sample += m; 399 } else if (m < new_sample) 400 new_sample = m << 3; 401 } else { 402 /* No previous measure. */ 403 new_sample = m << 3; 404 } 405 406 if (tp->rcv_rtt_est.rtt != new_sample) 407 tp->rcv_rtt_est.rtt = new_sample; 408} 409 410static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp) 411{ 412 if (tp->rcv_rtt_est.time == 0) 413 goto new_measure; 414 if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq)) 415 return; 416 tcp_rcv_rtt_update(tp, 417 jiffies - tp->rcv_rtt_est.time, 418 1); 419 420new_measure: 421 tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd; 422 tp->rcv_rtt_est.time = tcp_time_stamp; 423} 424 425static inline void tcp_rcv_rtt_measure_ts(struct sock *sk, const struct sk_buff *skb) 426{ 427 struct tcp_sock *tp = tcp_sk(sk); 428 if (tp->rx_opt.rcv_tsecr && 429 (TCP_SKB_CB(skb)->end_seq - 430 TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss)) 431 tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0); 432} 433 434/* 435 * This function should be called every time data is copied to user space. 436 * It calculates the appropriate TCP receive buffer space. 437 */ 438void tcp_rcv_space_adjust(struct sock *sk) 439{ 440 struct tcp_sock *tp = tcp_sk(sk); 441 int time; 442 int space; 443 444 if (tp->rcvq_space.time == 0) 445 goto new_measure; 446 447 time = tcp_time_stamp - tp->rcvq_space.time; 448 if (time < (tp->rcv_rtt_est.rtt >> 3) || 449 tp->rcv_rtt_est.rtt == 0) 450 return; 451 452 space = 2 * (tp->copied_seq - tp->rcvq_space.seq); 453 454 space = max(tp->rcvq_space.space, space); 455 456 if (tp->rcvq_space.space != space) { 457 int rcvmem; 458 459 tp->rcvq_space.space = space; 460 461 if (sysctl_tcp_moderate_rcvbuf && 462 !(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) { 463 int new_clamp = space; 464 465 /* Receive space grows, normalize in order to 466 * take into account packet headers and sk_buff 467 * structure overhead. 468 */ 469 space /= tp->advmss; 470 if (!space) 471 space = 1; 472 rcvmem = (tp->advmss + MAX_TCP_HEADER + 473 16 + sizeof(struct sk_buff)); 474 while (tcp_win_from_space(rcvmem) < tp->advmss) 475 rcvmem += 128; 476 space *= rcvmem; 477 space = min(space, sysctl_tcp_rmem[2]); 478 if (space > sk->sk_rcvbuf) { 479 sk->sk_rcvbuf = space; 480 481 /* Make the window clamp follow along. */ 482 tp->window_clamp = new_clamp; 483 } 484 } 485 } 486 487new_measure: 488 tp->rcvq_space.seq = tp->copied_seq; 489 tp->rcvq_space.time = tcp_time_stamp; 490} 491 492/* There is something which you must keep in mind when you analyze the 493 * behavior of the tp->ato delayed ack timeout interval. When a 494 * connection starts up, we want to ack as quickly as possible. The 495 * problem is that "good" TCP's do slow start at the beginning of data 496 * transmission. The means that until we send the first few ACK's the 497 * sender will sit on his end and only queue most of his data, because 498 * he can only send snd_cwnd unacked packets at any given time. For 499 * each ACK we send, he increments snd_cwnd and transmits more of his 500 * queue. -DaveM 501 */ 502static void tcp_event_data_recv(struct sock *sk, struct tcp_sock *tp, struct sk_buff *skb) 503{ 504 struct inet_connection_sock *icsk = inet_csk(sk); 505 u32 now; 506 507 inet_csk_schedule_ack(sk); 508 509 tcp_measure_rcv_mss(sk, skb); 510 511 tcp_rcv_rtt_measure(tp); 512 513 now = tcp_time_stamp; 514 515 if (!icsk->icsk_ack.ato) { 516 /* The _first_ data packet received, initialize 517 * delayed ACK engine. 518 */ 519 tcp_incr_quickack(sk); 520 icsk->icsk_ack.ato = TCP_ATO_MIN; 521 } else { 522 int m = now - icsk->icsk_ack.lrcvtime; 523 524 if (m <= TCP_ATO_MIN/2) { 525 /* The fastest case is the first. */ 526 icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + TCP_ATO_MIN / 2; 527 } else if (m < icsk->icsk_ack.ato) { 528 icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + m; 529 if (icsk->icsk_ack.ato > icsk->icsk_rto) 530 icsk->icsk_ack.ato = icsk->icsk_rto; 531 } else if (m > icsk->icsk_rto) { 532 /* Too long gap. Apparently sender failed to 533 * restart window, so that we send ACKs quickly. 534 */ 535 tcp_incr_quickack(sk); 536 sk_stream_mem_reclaim(sk); 537 } 538 } 539 icsk->icsk_ack.lrcvtime = now; 540 541 TCP_ECN_check_ce(tp, skb); 542 543 if (skb->len >= 128) 544 tcp_grow_window(sk, tp, skb); 545} 546 547/* Called to compute a smoothed rtt estimate. The data fed to this 548 * routine either comes from timestamps, or from segments that were 549 * known _not_ to have been retransmitted [see Karn/Partridge 550 * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88 551 * piece by Van Jacobson. 552 * NOTE: the next three routines used to be one big routine. 553 * To save cycles in the RFC 1323 implementation it was better to break 554 * it up into three procedures. -- erics 555 */ 556static void tcp_rtt_estimator(struct sock *sk, const __u32 mrtt) 557{ 558 struct tcp_sock *tp = tcp_sk(sk); 559 long m = mrtt; /* RTT */ 560 561 /* The following amusing code comes from Jacobson's 562 * article in SIGCOMM '88. Note that rtt and mdev 563 * are scaled versions of rtt and mean deviation. 564 * This is designed to be as fast as possible 565 * m stands for "measurement". 566 * 567 * On a 1990 paper the rto value is changed to: 568 * RTO = rtt + 4 * mdev 569 * 570 * Funny. This algorithm seems to be very broken. 571 * These formulae increase RTO, when it should be decreased, increase 572 * too slowly, when it should be increased quickly, decrease too quickly 573 * etc. I guess in BSD RTO takes ONE value, so that it is absolutely 574 * does not matter how to _calculate_ it. Seems, it was trap 575 * that VJ failed to avoid. 8) 576 */ 577 if(m == 0) 578 m = 1; 579 if (tp->srtt != 0) { 580 m -= (tp->srtt >> 3); /* m is now error in rtt est */ 581 tp->srtt += m; /* rtt = 7/8 rtt + 1/8 new */ 582 if (m < 0) { 583 m = -m; /* m is now abs(error) */ 584 m -= (tp->mdev >> 2); /* similar update on mdev */ 585 /* This is similar to one of Eifel findings. 586 * Eifel blocks mdev updates when rtt decreases. 587 * This solution is a bit different: we use finer gain 588 * for mdev in this case (alpha*beta). 589 * Like Eifel it also prevents growth of rto, 590 * but also it limits too fast rto decreases, 591 * happening in pure Eifel. 592 */ 593 if (m > 0) 594 m >>= 3; 595 } else { 596 m -= (tp->mdev >> 2); /* similar update on mdev */ 597 } 598 tp->mdev += m; /* mdev = 3/4 mdev + 1/4 new */ 599 if (tp->mdev > tp->mdev_max) { 600 tp->mdev_max = tp->mdev; 601 if (tp->mdev_max > tp->rttvar) 602 tp->rttvar = tp->mdev_max; 603 } 604 if (after(tp->snd_una, tp->rtt_seq)) { 605 if (tp->mdev_max < tp->rttvar) 606 tp->rttvar -= (tp->rttvar-tp->mdev_max)>>2; 607 tp->rtt_seq = tp->snd_nxt; 608 tp->mdev_max = TCP_RTO_MIN; 609 } 610 } else { 611 /* no previous measure. */ 612 tp->srtt = m<<3; /* take the measured time to be rtt */ 613 tp->mdev = m<<1; /* make sure rto = 3*rtt */ 614 tp->mdev_max = tp->rttvar = max(tp->mdev, TCP_RTO_MIN); 615 tp->rtt_seq = tp->snd_nxt; 616 } 617} 618 619/* Calculate rto without backoff. This is the second half of Van Jacobson's 620 * routine referred to above. 621 */ 622static inline void tcp_set_rto(struct sock *sk) 623{ 624 const struct tcp_sock *tp = tcp_sk(sk); 625 /* Old crap is replaced with new one. 8) 626 * 627 * More seriously: 628 * 1. If rtt variance happened to be less 50msec, it is hallucination. 629 * It cannot be less due to utterly erratic ACK generation made 630 * at least by solaris and freebsd. "Erratic ACKs" has _nothing_ 631 * to do with delayed acks, because at cwnd>2 true delack timeout 632 * is invisible. Actually, Linux-2.4 also generates erratic 633 * ACKs in some circumstances. 634 */ 635 inet_csk(sk)->icsk_rto = (tp->srtt >> 3) + tp->rttvar; 636 637 /* 2. Fixups made earlier cannot be right. 638 * If we do not estimate RTO correctly without them, 639 * all the algo is pure shit and should be replaced 640 * with correct one. It is exactly, which we pretend to do. 641 */ 642} 643 644/* NOTE: clamping at TCP_RTO_MIN is not required, current algo 645 * guarantees that rto is higher. 646 */ 647static inline void tcp_bound_rto(struct sock *sk) 648{ 649 if (inet_csk(sk)->icsk_rto > TCP_RTO_MAX) 650 inet_csk(sk)->icsk_rto = TCP_RTO_MAX; 651} 652 653/* Save metrics learned by this TCP session. 654 This function is called only, when TCP finishes successfully 655 i.e. when it enters TIME-WAIT or goes from LAST-ACK to CLOSE. 656 */ 657void tcp_update_metrics(struct sock *sk) 658{ 659 struct tcp_sock *tp = tcp_sk(sk); 660 struct dst_entry *dst = __sk_dst_get(sk); 661 662 if (sysctl_tcp_nometrics_save) 663 return; 664 665 dst_confirm(dst); 666 667 if (dst && (dst->flags&DST_HOST)) { 668 const struct inet_connection_sock *icsk = inet_csk(sk); 669 int m; 670 671 if (icsk->icsk_backoff || !tp->srtt) { 672 /* This session failed to estimate rtt. Why? 673 * Probably, no packets returned in time. 674 * Reset our results. 675 */ 676 if (!(dst_metric_locked(dst, RTAX_RTT))) 677 dst->metrics[RTAX_RTT-1] = 0; 678 return; 679 } 680 681 m = dst_metric(dst, RTAX_RTT) - tp->srtt; 682 683 /* If newly calculated rtt larger than stored one, 684 * store new one. Otherwise, use EWMA. Remember, 685 * rtt overestimation is always better than underestimation. 686 */ 687 if (!(dst_metric_locked(dst, RTAX_RTT))) { 688 if (m <= 0) 689 dst->metrics[RTAX_RTT-1] = tp->srtt; 690 else 691 dst->metrics[RTAX_RTT-1] -= (m>>3); 692 } 693 694 if (!(dst_metric_locked(dst, RTAX_RTTVAR))) { 695 if (m < 0) 696 m = -m; 697 698 /* Scale deviation to rttvar fixed point */ 699 m >>= 1; 700 if (m < tp->mdev) 701 m = tp->mdev; 702 703 if (m >= dst_metric(dst, RTAX_RTTVAR)) 704 dst->metrics[RTAX_RTTVAR-1] = m; 705 else 706 dst->metrics[RTAX_RTTVAR-1] -= 707 (dst->metrics[RTAX_RTTVAR-1] - m)>>2; 708 } 709 710 if (tp->snd_ssthresh >= 0xFFFF) { 711 /* Slow start still did not finish. */ 712 if (dst_metric(dst, RTAX_SSTHRESH) && 713 !dst_metric_locked(dst, RTAX_SSTHRESH) && 714 (tp->snd_cwnd >> 1) > dst_metric(dst, RTAX_SSTHRESH)) 715 dst->metrics[RTAX_SSTHRESH-1] = tp->snd_cwnd >> 1; 716 if (!dst_metric_locked(dst, RTAX_CWND) && 717 tp->snd_cwnd > dst_metric(dst, RTAX_CWND)) 718 dst->metrics[RTAX_CWND-1] = tp->snd_cwnd; 719 } else if (tp->snd_cwnd > tp->snd_ssthresh && 720 icsk->icsk_ca_state == TCP_CA_Open) { 721 /* Cong. avoidance phase, cwnd is reliable. */ 722 if (!dst_metric_locked(dst, RTAX_SSTHRESH)) 723 dst->metrics[RTAX_SSTHRESH-1] = 724 max(tp->snd_cwnd >> 1, tp->snd_ssthresh); 725 if (!dst_metric_locked(dst, RTAX_CWND)) 726 dst->metrics[RTAX_CWND-1] = (dst->metrics[RTAX_CWND-1] + tp->snd_cwnd) >> 1; 727 } else { 728 /* Else slow start did not finish, cwnd is non-sense, 729 ssthresh may be also invalid. 730 */ 731 if (!dst_metric_locked(dst, RTAX_CWND)) 732 dst->metrics[RTAX_CWND-1] = (dst->metrics[RTAX_CWND-1] + tp->snd_ssthresh) >> 1; 733 if (dst->metrics[RTAX_SSTHRESH-1] && 734 !dst_metric_locked(dst, RTAX_SSTHRESH) && 735 tp->snd_ssthresh > dst->metrics[RTAX_SSTHRESH-1]) 736 dst->metrics[RTAX_SSTHRESH-1] = tp->snd_ssthresh; 737 } 738 739 if (!dst_metric_locked(dst, RTAX_REORDERING)) { 740 if (dst->metrics[RTAX_REORDERING-1] < tp->reordering && 741 tp->reordering != sysctl_tcp_reordering) 742 dst->metrics[RTAX_REORDERING-1] = tp->reordering; 743 } 744 } 745} 746 747/* Numbers are taken from RFC2414. */ 748__u32 tcp_init_cwnd(struct tcp_sock *tp, struct dst_entry *dst) 749{ 750 __u32 cwnd = (dst ? dst_metric(dst, RTAX_INITCWND) : 0); 751 752 if (!cwnd) { 753 if (tp->mss_cache > 1460) 754 cwnd = 2; 755 else 756 cwnd = (tp->mss_cache > 1095) ? 3 : 4; 757 } 758 return min_t(__u32, cwnd, tp->snd_cwnd_clamp); 759} 760 761/* Set slow start threshold and cwnd not falling to slow start */ 762void tcp_enter_cwr(struct sock *sk) 763{ 764 struct tcp_sock *tp = tcp_sk(sk); 765 766 tp->prior_ssthresh = 0; 767 tp->bytes_acked = 0; 768 if (inet_csk(sk)->icsk_ca_state < TCP_CA_CWR) { 769 tp->undo_marker = 0; 770 tp->snd_ssthresh = inet_csk(sk)->icsk_ca_ops->ssthresh(sk); 771 tp->snd_cwnd = min(tp->snd_cwnd, 772 tcp_packets_in_flight(tp) + 1U); 773 tp->snd_cwnd_cnt = 0; 774 tp->high_seq = tp->snd_nxt; 775 tp->snd_cwnd_stamp = tcp_time_stamp; 776 TCP_ECN_queue_cwr(tp); 777 778 tcp_set_ca_state(sk, TCP_CA_CWR); 779 } 780} 781 782/* Initialize metrics on socket. */ 783 784static void tcp_init_metrics(struct sock *sk) 785{ 786 struct tcp_sock *tp = tcp_sk(sk); 787 struct dst_entry *dst = __sk_dst_get(sk); 788 789 if (dst == NULL) 790 goto reset; 791 792 dst_confirm(dst); 793 794 if (dst_metric_locked(dst, RTAX_CWND)) 795 tp->snd_cwnd_clamp = dst_metric(dst, RTAX_CWND); 796 if (dst_metric(dst, RTAX_SSTHRESH)) { 797 tp->snd_ssthresh = dst_metric(dst, RTAX_SSTHRESH); 798 if (tp->snd_ssthresh > tp->snd_cwnd_clamp) 799 tp->snd_ssthresh = tp->snd_cwnd_clamp; 800 } 801 if (dst_metric(dst, RTAX_REORDERING) && 802 tp->reordering != dst_metric(dst, RTAX_REORDERING)) { 803 tp->rx_opt.sack_ok &= ~2; 804 tp->reordering = dst_metric(dst, RTAX_REORDERING); 805 } 806 807 if (dst_metric(dst, RTAX_RTT) == 0) 808 goto reset; 809 810 if (!tp->srtt && dst_metric(dst, RTAX_RTT) < (TCP_TIMEOUT_INIT << 3)) 811 goto reset; 812 813 /* Initial rtt is determined from SYN,SYN-ACK. 814 * The segment is small and rtt may appear much 815 * less than real one. Use per-dst memory 816 * to make it more realistic. 817 * 818 * A bit of theory. RTT is time passed after "normal" sized packet 819 * is sent until it is ACKed. In normal circumstances sending small 820 * packets force peer to delay ACKs and calculation is correct too. 821 * The algorithm is adaptive and, provided we follow specs, it 822 * NEVER underestimate RTT. BUT! If peer tries to make some clever 823 * tricks sort of "quick acks" for time long enough to decrease RTT 824 * to low value, and then abruptly stops to do it and starts to delay 825 * ACKs, wait for troubles. 826 */ 827 if (dst_metric(dst, RTAX_RTT) > tp->srtt) { 828 tp->srtt = dst_metric(dst, RTAX_RTT); 829 tp->rtt_seq = tp->snd_nxt; 830 } 831 if (dst_metric(dst, RTAX_RTTVAR) > tp->mdev) { 832 tp->mdev = dst_metric(dst, RTAX_RTTVAR); 833 tp->mdev_max = tp->rttvar = max(tp->mdev, TCP_RTO_MIN); 834 } 835 tcp_set_rto(sk); 836 tcp_bound_rto(sk); 837 if (inet_csk(sk)->icsk_rto < TCP_TIMEOUT_INIT && !tp->rx_opt.saw_tstamp) 838 goto reset; 839 tp->snd_cwnd = tcp_init_cwnd(tp, dst); 840 tp->snd_cwnd_stamp = tcp_time_stamp; 841 return; 842 843reset: 844 /* Play conservative. If timestamps are not 845 * supported, TCP will fail to recalculate correct 846 * rtt, if initial rto is too small. FORGET ALL AND RESET! 847 */ 848 if (!tp->rx_opt.saw_tstamp && tp->srtt) { 849 tp->srtt = 0; 850 tp->mdev = tp->mdev_max = tp->rttvar = TCP_TIMEOUT_INIT; 851 inet_csk(sk)->icsk_rto = TCP_TIMEOUT_INIT; 852 } 853} 854 855static void tcp_update_reordering(struct sock *sk, const int metric, 856 const int ts) 857{ 858 struct tcp_sock *tp = tcp_sk(sk); 859 if (metric > tp->reordering) { 860 tp->reordering = min(TCP_MAX_REORDERING, metric); 861 862 /* This exciting event is worth to be remembered. 8) */ 863 if (ts) 864 NET_INC_STATS_BH(LINUX_MIB_TCPTSREORDER); 865 else if (IsReno(tp)) 866 NET_INC_STATS_BH(LINUX_MIB_TCPRENOREORDER); 867 else if (IsFack(tp)) 868 NET_INC_STATS_BH(LINUX_MIB_TCPFACKREORDER); 869 else 870 NET_INC_STATS_BH(LINUX_MIB_TCPSACKREORDER); 871#if FASTRETRANS_DEBUG > 1 872 printk(KERN_DEBUG "Disorder%d %d %u f%u s%u rr%d\n", 873 tp->rx_opt.sack_ok, inet_csk(sk)->icsk_ca_state, 874 tp->reordering, 875 tp->fackets_out, 876 tp->sacked_out, 877 tp->undo_marker ? tp->undo_retrans : 0); 878#endif 879 /* Disable FACK yet. */ 880 tp->rx_opt.sack_ok &= ~2; 881 } 882} 883 884/* This procedure tags the retransmission queue when SACKs arrive. 885 * 886 * We have three tag bits: SACKED(S), RETRANS(R) and LOST(L). 887 * Packets in queue with these bits set are counted in variables 888 * sacked_out, retrans_out and lost_out, correspondingly. 889 * 890 * Valid combinations are: 891 * Tag InFlight Description 892 * 0 1 - orig segment is in flight. 893 * S 0 - nothing flies, orig reached receiver. 894 * L 0 - nothing flies, orig lost by net. 895 * R 2 - both orig and retransmit are in flight. 896 * L|R 1 - orig is lost, retransmit is in flight. 897 * S|R 1 - orig reached receiver, retrans is still in flight. 898 * (L|S|R is logically valid, it could occur when L|R is sacked, 899 * but it is equivalent to plain S and code short-curcuits it to S. 900 * L|S is logically invalid, it would mean -1 packet in flight 8)) 901 * 902 * These 6 states form finite state machine, controlled by the following events: 903 * 1. New ACK (+SACK) arrives. (tcp_sacktag_write_queue()) 904 * 2. Retransmission. (tcp_retransmit_skb(), tcp_xmit_retransmit_queue()) 905 * 3. Loss detection event of one of three flavors: 906 * A. Scoreboard estimator decided the packet is lost. 907 * A'. Reno "three dupacks" marks head of queue lost. 908 * A''. Its FACK modfication, head until snd.fack is lost. 909 * B. SACK arrives sacking data transmitted after never retransmitted 910 * hole was sent out. 911 * C. SACK arrives sacking SND.NXT at the moment, when the 912 * segment was retransmitted. 913 * 4. D-SACK added new rule: D-SACK changes any tag to S. 914 * 915 * It is pleasant to note, that state diagram turns out to be commutative, 916 * so that we are allowed not to be bothered by order of our actions, 917 * when multiple events arrive simultaneously. (see the function below). 918 * 919 * Reordering detection. 920 * -------------------- 921 * Reordering metric is maximal distance, which a packet can be displaced 922 * in packet stream. With SACKs we can estimate it: 923 * 924 * 1. SACK fills old hole and the corresponding segment was not 925 * ever retransmitted -> reordering. Alas, we cannot use it 926 * when segment was retransmitted. 927 * 2. The last flaw is solved with D-SACK. D-SACK arrives 928 * for retransmitted and already SACKed segment -> reordering.. 929 * Both of these heuristics are not used in Loss state, when we cannot 930 * account for retransmits accurately. 931 */ 932static int 933tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_una) 934{ 935 const struct inet_connection_sock *icsk = inet_csk(sk); 936 struct tcp_sock *tp = tcp_sk(sk); 937 unsigned char *ptr = ack_skb->h.raw + TCP_SKB_CB(ack_skb)->sacked; 938 struct tcp_sack_block_wire *sp = (struct tcp_sack_block_wire *)(ptr+2); 939 int num_sacks = (ptr[1] - TCPOLEN_SACK_BASE)>>3; 940 int reord = tp->packets_out; 941 int prior_fackets; 942 u32 lost_retrans = 0; 943 int flag = 0; 944 int dup_sack = 0; 945 int i; 946 947 if (!tp->sacked_out) 948 tp->fackets_out = 0; 949 prior_fackets = tp->fackets_out; 950 951 /* SACK fastpath: 952 * if the only SACK change is the increase of the end_seq of 953 * the first block then only apply that SACK block 954 * and use retrans queue hinting otherwise slowpath */ 955 flag = 1; 956 for (i = 0; i< num_sacks; i++) { 957 __u32 start_seq = ntohl(sp[i].start_seq); 958 __u32 end_seq = ntohl(sp[i].end_seq); 959 960 if (i == 0){ 961 if (tp->recv_sack_cache[i].start_seq != start_seq) 962 flag = 0; 963 } else { 964 if ((tp->recv_sack_cache[i].start_seq != start_seq) || 965 (tp->recv_sack_cache[i].end_seq != end_seq)) 966 flag = 0; 967 } 968 tp->recv_sack_cache[i].start_seq = start_seq; 969 tp->recv_sack_cache[i].end_seq = end_seq; 970 971 /* Check for D-SACK. */ 972 if (i == 0) { 973 u32 ack = TCP_SKB_CB(ack_skb)->ack_seq; 974 975 if (before(start_seq, ack)) { 976 dup_sack = 1; 977 tp->rx_opt.sack_ok |= 4; 978 NET_INC_STATS_BH(LINUX_MIB_TCPDSACKRECV); 979 } else if (num_sacks > 1 && 980 !after(end_seq, ntohl(sp[1].end_seq)) && 981 !before(start_seq, ntohl(sp[1].start_seq))) { 982 dup_sack = 1; 983 tp->rx_opt.sack_ok |= 4; 984 NET_INC_STATS_BH(LINUX_MIB_TCPDSACKOFORECV); 985 } 986 987 /* D-SACK for already forgotten data... 988 * Do dumb counting. */ 989 if (dup_sack && 990 !after(end_seq, prior_snd_una) && 991 after(end_seq, tp->undo_marker)) 992 tp->undo_retrans--; 993 994 /* Eliminate too old ACKs, but take into 995 * account more or less fresh ones, they can 996 * contain valid SACK info. 997 */ 998 if (before(ack, prior_snd_una - tp->max_window)) 999 return 0; 1000 } 1001 } 1002 1003 if (flag) 1004 num_sacks = 1; 1005 else { 1006 int j; 1007 tp->fastpath_skb_hint = NULL; 1008 1009 /* order SACK blocks to allow in order walk of the retrans queue */ 1010 for (i = num_sacks-1; i > 0; i--) { 1011 for (j = 0; j < i; j++){ 1012 if (after(ntohl(sp[j].start_seq), 1013 ntohl(sp[j+1].start_seq))){ 1014 sp[j].start_seq = htonl(tp->recv_sack_cache[j+1].start_seq); 1015 sp[j].end_seq = htonl(tp->recv_sack_cache[j+1].end_seq); 1016 sp[j+1].start_seq = htonl(tp->recv_sack_cache[j].start_seq); 1017 sp[j+1].end_seq = htonl(tp->recv_sack_cache[j].end_seq); 1018 } 1019 1020 } 1021 } 1022 } 1023 1024 /* clear flag as used for different purpose in following code */ 1025 flag = 0; 1026 1027 for (i=0; i<num_sacks; i++, sp++) { 1028 struct sk_buff *skb; 1029 __u32 start_seq = ntohl(sp->start_seq); 1030 __u32 end_seq = ntohl(sp->end_seq); 1031 int fack_count; 1032 1033 /* Use SACK fastpath hint if valid */ 1034 if (tp->fastpath_skb_hint) { 1035 skb = tp->fastpath_skb_hint; 1036 fack_count = tp->fastpath_cnt_hint; 1037 } else { 1038 skb = sk->sk_write_queue.next; 1039 fack_count = 0; 1040 } 1041 1042 /* Event "B" in the comment above. */ 1043 if (after(end_seq, tp->high_seq)) 1044 flag |= FLAG_DATA_LOST; 1045 1046 sk_stream_for_retrans_queue_from(skb, sk) { 1047 int in_sack, pcount; 1048 u8 sacked; 1049 1050 tp->fastpath_skb_hint = skb; 1051 tp->fastpath_cnt_hint = fack_count; 1052 1053 /* The retransmission queue is always in order, so 1054 * we can short-circuit the walk early. 1055 */ 1056 if (!before(TCP_SKB_CB(skb)->seq, end_seq)) 1057 break; 1058 1059 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) && 1060 !before(end_seq, TCP_SKB_CB(skb)->end_seq); 1061 1062 pcount = tcp_skb_pcount(skb); 1063 1064 if (pcount > 1 && !in_sack && 1065 after(TCP_SKB_CB(skb)->end_seq, start_seq)) { 1066 unsigned int pkt_len; 1067 1068 in_sack = !after(start_seq, 1069 TCP_SKB_CB(skb)->seq); 1070 1071 if (!in_sack) 1072 pkt_len = (start_seq - 1073 TCP_SKB_CB(skb)->seq); 1074 else 1075 pkt_len = (end_seq - 1076 TCP_SKB_CB(skb)->seq); 1077 if (tcp_fragment(sk, skb, pkt_len, skb_shinfo(skb)->gso_size)) 1078 break; 1079 pcount = tcp_skb_pcount(skb); 1080 } 1081 1082 fack_count += pcount; 1083 1084 sacked = TCP_SKB_CB(skb)->sacked; 1085 1086 /* Account D-SACK for retransmitted packet. */ 1087 if ((dup_sack && in_sack) && 1088 (sacked & TCPCB_RETRANS) && 1089 after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker)) 1090 tp->undo_retrans--; 1091 1092 /* The frame is ACKed. */ 1093 if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) { 1094 if (sacked&TCPCB_RETRANS) { 1095 if ((dup_sack && in_sack) && 1096 (sacked&TCPCB_SACKED_ACKED)) 1097 reord = min(fack_count, reord); 1098 } else { 1099 /* If it was in a hole, we detected reordering. */ 1100 if (fack_count < prior_fackets && 1101 !(sacked&TCPCB_SACKED_ACKED)) 1102 reord = min(fack_count, reord); 1103 } 1104 1105 /* Nothing to do; acked frame is about to be dropped. */ 1106 continue; 1107 } 1108 1109 if ((sacked&TCPCB_SACKED_RETRANS) && 1110 after(end_seq, TCP_SKB_CB(skb)->ack_seq) && 1111 (!lost_retrans || after(end_seq, lost_retrans))) 1112 lost_retrans = end_seq; 1113 1114 if (!in_sack) 1115 continue; 1116 1117 if (!(sacked&TCPCB_SACKED_ACKED)) { 1118 if (sacked & TCPCB_SACKED_RETRANS) { 1119 /* If the segment is not tagged as lost, 1120 * we do not clear RETRANS, believing 1121 * that retransmission is still in flight. 1122 */ 1123 if (sacked & TCPCB_LOST) { 1124 TCP_SKB_CB(skb)->sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS); 1125 tp->lost_out -= tcp_skb_pcount(skb); 1126 tp->retrans_out -= tcp_skb_pcount(skb); 1127 1128 /* clear lost hint */ 1129 tp->retransmit_skb_hint = NULL; 1130 } 1131 } else { 1132 /* New sack for not retransmitted frame, 1133 * which was in hole. It is reordering. 1134 */ 1135 if (!(sacked & TCPCB_RETRANS) && 1136 fack_count < prior_fackets) 1137 reord = min(fack_count, reord); 1138 1139 if (sacked & TCPCB_LOST) { 1140 TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST; 1141 tp->lost_out -= tcp_skb_pcount(skb); 1142 1143 /* clear lost hint */ 1144 tp->retransmit_skb_hint = NULL; 1145 } 1146 } 1147 1148 TCP_SKB_CB(skb)->sacked |= TCPCB_SACKED_ACKED; 1149 flag |= FLAG_DATA_SACKED; 1150 tp->sacked_out += tcp_skb_pcount(skb); 1151 1152 if (fack_count > tp->fackets_out) 1153 tp->fackets_out = fack_count; 1154 } else { 1155 if (dup_sack && (sacked&TCPCB_RETRANS)) 1156 reord = min(fack_count, reord); 1157 } 1158 1159 /* D-SACK. We can detect redundant retransmission 1160 * in S|R and plain R frames and clear it. 1161 * undo_retrans is decreased above, L|R frames 1162 * are accounted above as well. 1163 */ 1164 if (dup_sack && 1165 (TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_RETRANS)) { 1166 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS; 1167 tp->retrans_out -= tcp_skb_pcount(skb); 1168 tp->retransmit_skb_hint = NULL; 1169 } 1170 } 1171 } 1172 1173 /* Check for lost retransmit. This superb idea is 1174 * borrowed from "ratehalving". Event "C". 1175 * Later note: FACK people cheated me again 8), 1176 * we have to account for reordering! Ugly, 1177 * but should help. 1178 */ 1179 if (lost_retrans && icsk->icsk_ca_state == TCP_CA_Recovery) { 1180 struct sk_buff *skb; 1181 1182 sk_stream_for_retrans_queue(skb, sk) { 1183 if (after(TCP_SKB_CB(skb)->seq, lost_retrans)) 1184 break; 1185 if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) 1186 continue; 1187 if ((TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_RETRANS) && 1188 after(lost_retrans, TCP_SKB_CB(skb)->ack_seq) && 1189 (IsFack(tp) || 1190 !before(lost_retrans, 1191 TCP_SKB_CB(skb)->ack_seq + tp->reordering * 1192 tp->mss_cache))) { 1193 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS; 1194 tp->retrans_out -= tcp_skb_pcount(skb); 1195 1196 /* clear lost hint */ 1197 tp->retransmit_skb_hint = NULL; 1198 1199 if (!(TCP_SKB_CB(skb)->sacked&(TCPCB_LOST|TCPCB_SACKED_ACKED))) { 1200 tp->lost_out += tcp_skb_pcount(skb); 1201 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1202 flag |= FLAG_DATA_SACKED; 1203 NET_INC_STATS_BH(LINUX_MIB_TCPLOSTRETRANSMIT); 1204 } 1205 } 1206 } 1207 } 1208 1209 tp->left_out = tp->sacked_out + tp->lost_out; 1210 1211 if ((reord < tp->fackets_out) && icsk->icsk_ca_state != TCP_CA_Loss) 1212 tcp_update_reordering(sk, ((tp->fackets_out + 1) - reord), 0); 1213 1214#if FASTRETRANS_DEBUG > 0 1215 BUG_TRAP((int)tp->sacked_out >= 0); 1216 BUG_TRAP((int)tp->lost_out >= 0); 1217 BUG_TRAP((int)tp->retrans_out >= 0); 1218 BUG_TRAP((int)tcp_packets_in_flight(tp) >= 0); 1219#endif 1220 return flag; 1221} 1222 1223/* RTO occurred, but do not yet enter loss state. Instead, transmit two new 1224 * segments to see from the next ACKs whether any data was really missing. 1225 * If the RTO was spurious, new ACKs should arrive. 1226 */ 1227void tcp_enter_frto(struct sock *sk) 1228{ 1229 const struct inet_connection_sock *icsk = inet_csk(sk); 1230 struct tcp_sock *tp = tcp_sk(sk); 1231 struct sk_buff *skb; 1232 1233 tp->frto_counter = 1; 1234 1235 if (icsk->icsk_ca_state <= TCP_CA_Disorder || 1236 tp->snd_una == tp->high_seq || 1237 (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) { 1238 tp->prior_ssthresh = tcp_current_ssthresh(sk); 1239 tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk); 1240 tcp_ca_event(sk, CA_EVENT_FRTO); 1241 } 1242 1243 /* Have to clear retransmission markers here to keep the bookkeeping 1244 * in shape, even though we are not yet in Loss state. 1245 * If something was really lost, it is eventually caught up 1246 * in tcp_enter_frto_loss. 1247 */ 1248 tp->retrans_out = 0; 1249 tp->undo_marker = tp->snd_una; 1250 tp->undo_retrans = 0; 1251 1252 sk_stream_for_retrans_queue(skb, sk) { 1253 TCP_SKB_CB(skb)->sacked &= ~TCPCB_RETRANS; 1254 } 1255 tcp_sync_left_out(tp); 1256 1257 tcp_set_ca_state(sk, TCP_CA_Open); 1258 tp->frto_highmark = tp->snd_nxt; 1259} 1260 1261/* Enter Loss state after F-RTO was applied. Dupack arrived after RTO, 1262 * which indicates that we should follow the traditional RTO recovery, 1263 * i.e. mark everything lost and do go-back-N retransmission. 1264 */ 1265static void tcp_enter_frto_loss(struct sock *sk) 1266{ 1267 struct tcp_sock *tp = tcp_sk(sk); 1268 struct sk_buff *skb; 1269 int cnt = 0; 1270 1271 tp->sacked_out = 0; 1272 tp->lost_out = 0; 1273 tp->fackets_out = 0; 1274 1275 sk_stream_for_retrans_queue(skb, sk) { 1276 cnt += tcp_skb_pcount(skb); 1277 TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST; 1278 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_ACKED)) { 1279 1280 /* Do not mark those segments lost that were 1281 * forward transmitted after RTO 1282 */ 1283 if (!after(TCP_SKB_CB(skb)->end_seq, 1284 tp->frto_highmark)) { 1285 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1286 tp->lost_out += tcp_skb_pcount(skb); 1287 } 1288 } else { 1289 tp->sacked_out += tcp_skb_pcount(skb); 1290 tp->fackets_out = cnt; 1291 } 1292 } 1293 tcp_sync_left_out(tp); 1294 1295 tp->snd_cwnd = tp->frto_counter + tcp_packets_in_flight(tp)+1; 1296 tp->snd_cwnd_cnt = 0; 1297 tp->snd_cwnd_stamp = tcp_time_stamp; 1298 tp->undo_marker = 0; 1299 tp->frto_counter = 0; 1300 1301 tp->reordering = min_t(unsigned int, tp->reordering, 1302 sysctl_tcp_reordering); 1303 tcp_set_ca_state(sk, TCP_CA_Loss); 1304 tp->high_seq = tp->frto_highmark; 1305 TCP_ECN_queue_cwr(tp); 1306 1307 clear_all_retrans_hints(tp); 1308} 1309 1310void tcp_clear_retrans(struct tcp_sock *tp) 1311{ 1312 tp->left_out = 0; 1313 tp->retrans_out = 0; 1314 1315 tp->fackets_out = 0; 1316 tp->sacked_out = 0; 1317 tp->lost_out = 0; 1318 1319 tp->undo_marker = 0; 1320 tp->undo_retrans = 0; 1321} 1322 1323/* Enter Loss state. If "how" is not zero, forget all SACK information 1324 * and reset tags completely, otherwise preserve SACKs. If receiver 1325 * dropped its ofo queue, we will know this due to reneging detection. 1326 */ 1327void tcp_enter_loss(struct sock *sk, int how) 1328{ 1329 const struct inet_connection_sock *icsk = inet_csk(sk); 1330 struct tcp_sock *tp = tcp_sk(sk); 1331 struct sk_buff *skb; 1332 int cnt = 0; 1333 1334 /* Reduce ssthresh if it has not yet been made inside this window. */ 1335 if (icsk->icsk_ca_state <= TCP_CA_Disorder || tp->snd_una == tp->high_seq || 1336 (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) { 1337 tp->prior_ssthresh = tcp_current_ssthresh(sk); 1338 tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk); 1339 tcp_ca_event(sk, CA_EVENT_LOSS); 1340 } 1341 tp->snd_cwnd = 1; 1342 tp->snd_cwnd_cnt = 0; 1343 tp->snd_cwnd_stamp = tcp_time_stamp; 1344 1345 tp->bytes_acked = 0; 1346 tcp_clear_retrans(tp); 1347 1348 /* Push undo marker, if it was plain RTO and nothing 1349 * was retransmitted. */ 1350 if (!how) 1351 tp->undo_marker = tp->snd_una; 1352 1353 sk_stream_for_retrans_queue(skb, sk) { 1354 cnt += tcp_skb_pcount(skb); 1355 if (TCP_SKB_CB(skb)->sacked&TCPCB_RETRANS) 1356 tp->undo_marker = 0; 1357 TCP_SKB_CB(skb)->sacked &= (~TCPCB_TAGBITS)|TCPCB_SACKED_ACKED; 1358 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_ACKED) || how) { 1359 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_ACKED; 1360 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1361 tp->lost_out += tcp_skb_pcount(skb); 1362 } else { 1363 tp->sacked_out += tcp_skb_pcount(skb); 1364 tp->fackets_out = cnt; 1365 } 1366 } 1367 tcp_sync_left_out(tp); 1368 1369 tp->reordering = min_t(unsigned int, tp->reordering, 1370 sysctl_tcp_reordering); 1371 tcp_set_ca_state(sk, TCP_CA_Loss); 1372 tp->high_seq = tp->snd_nxt; 1373 TCP_ECN_queue_cwr(tp); 1374 1375 clear_all_retrans_hints(tp); 1376} 1377 1378static int tcp_check_sack_reneging(struct sock *sk) 1379{ 1380 struct sk_buff *skb; 1381 1382 /* If ACK arrived pointing to a remembered SACK, 1383 * it means that our remembered SACKs do not reflect 1384 * real state of receiver i.e. 1385 * receiver _host_ is heavily congested (or buggy). 1386 * Do processing similar to RTO timeout. 1387 */ 1388 if ((skb = skb_peek(&sk->sk_write_queue)) != NULL && 1389 (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) { 1390 struct inet_connection_sock *icsk = inet_csk(sk); 1391 NET_INC_STATS_BH(LINUX_MIB_TCPSACKRENEGING); 1392 1393 tcp_enter_loss(sk, 1); 1394 icsk->icsk_retransmits++; 1395 tcp_retransmit_skb(sk, skb_peek(&sk->sk_write_queue)); 1396 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, 1397 icsk->icsk_rto, TCP_RTO_MAX); 1398 return 1; 1399 } 1400 return 0; 1401} 1402 1403static inline int tcp_fackets_out(struct tcp_sock *tp) 1404{ 1405 return IsReno(tp) ? tp->sacked_out+1 : tp->fackets_out; 1406} 1407 1408static inline int tcp_skb_timedout(struct sock *sk, struct sk_buff *skb) 1409{ 1410 return (tcp_time_stamp - TCP_SKB_CB(skb)->when > inet_csk(sk)->icsk_rto); 1411} 1412 1413static inline int tcp_head_timedout(struct sock *sk, struct tcp_sock *tp) 1414{ 1415 return tp->packets_out && 1416 tcp_skb_timedout(sk, skb_peek(&sk->sk_write_queue)); 1417} 1418 1419/* Linux NewReno/SACK/FACK/ECN state machine. 1420 * -------------------------------------- 1421 * 1422 * "Open" Normal state, no dubious events, fast path. 1423 * "Disorder" In all the respects it is "Open", 1424 * but requires a bit more attention. It is entered when 1425 * we see some SACKs or dupacks. It is split of "Open" 1426 * mainly to move some processing from fast path to slow one. 1427 * "CWR" CWND was reduced due to some Congestion Notification event. 1428 * It can be ECN, ICMP source quench, local device congestion. 1429 * "Recovery" CWND was reduced, we are fast-retransmitting. 1430 * "Loss" CWND was reduced due to RTO timeout or SACK reneging. 1431 * 1432 * tcp_fastretrans_alert() is entered: 1433 * - each incoming ACK, if state is not "Open" 1434 * - when arrived ACK is unusual, namely: 1435 * * SACK 1436 * * Duplicate ACK. 1437 * * ECN ECE. 1438 * 1439 * Counting packets in flight is pretty simple. 1440 * 1441 * in_flight = packets_out - left_out + retrans_out 1442 * 1443 * packets_out is SND.NXT-SND.UNA counted in packets. 1444 * 1445 * retrans_out is number of retransmitted segments. 1446 * 1447 * left_out is number of segments left network, but not ACKed yet. 1448 * 1449 * left_out = sacked_out + lost_out 1450 * 1451 * sacked_out: Packets, which arrived to receiver out of order 1452 * and hence not ACKed. With SACKs this number is simply 1453 * amount of SACKed data. Even without SACKs 1454 * it is easy to give pretty reliable estimate of this number, 1455 * counting duplicate ACKs. 1456 * 1457 * lost_out: Packets lost by network. TCP has no explicit 1458 * "loss notification" feedback from network (for now). 1459 * It means that this number can be only _guessed_. 1460 * Actually, it is the heuristics to predict lossage that 1461 * distinguishes different algorithms. 1462 * 1463 * F.e. after RTO, when all the queue is considered as lost, 1464 * lost_out = packets_out and in_flight = retrans_out. 1465 * 1466 * Essentially, we have now two algorithms counting 1467 * lost packets. 1468 * 1469 * FACK: It is the simplest heuristics. As soon as we decided 1470 * that something is lost, we decide that _all_ not SACKed 1471 * packets until the most forward SACK are lost. I.e. 1472 * lost_out = fackets_out - sacked_out and left_out = fackets_out. 1473 * It is absolutely correct estimate, if network does not reorder 1474 * packets. And it loses any connection to reality when reordering 1475 * takes place. We use FACK by default until reordering 1476 * is suspected on the path to this destination. 1477 * 1478 * NewReno: when Recovery is entered, we assume that one segment 1479 * is lost (classic Reno). While we are in Recovery and 1480 * a partial ACK arrives, we assume that one more packet 1481 * is lost (NewReno). This heuristics are the same in NewReno 1482 * and SACK. 1483 * 1484 * Imagine, that's all! Forget about all this shamanism about CWND inflation 1485 * deflation etc. CWND is real congestion window, never inflated, changes 1486 * only according to classic VJ rules. 1487 * 1488 * Really tricky (and requiring careful tuning) part of algorithm 1489 * is hidden in functions tcp_time_to_recover() and tcp_xmit_retransmit_queue(). 1490 * The first determines the moment _when_ we should reduce CWND and, 1491 * hence, slow down forward transmission. In fact, it determines the moment 1492 * when we decide that hole is caused by loss, rather than by a reorder. 1493 * 1494 * tcp_xmit_retransmit_queue() decides, _what_ we should retransmit to fill 1495 * holes, caused by lost packets. 1496 * 1497 * And the most logically complicated part of algorithm is undo 1498 * heuristics. We detect false retransmits due to both too early 1499 * fast retransmit (reordering) and underestimated RTO, analyzing 1500 * timestamps and D-SACKs. When we detect that some segments were 1501 * retransmitted by mistake and CWND reduction was wrong, we undo 1502 * window reduction and abort recovery phase. This logic is hidden 1503 * inside several functions named tcp_try_undo_<something>. 1504 */ 1505 1506/* This function decides, when we should leave Disordered state 1507 * and enter Recovery phase, reducing congestion window. 1508 * 1509 * Main question: may we further continue forward transmission 1510 * with the same cwnd? 1511 */ 1512static int tcp_time_to_recover(struct sock *sk, struct tcp_sock *tp) 1513{ 1514 __u32 packets_out; 1515 1516 /* Trick#1: The loss is proven. */ 1517 if (tp->lost_out) 1518 return 1; 1519 1520 /* Not-A-Trick#2 : Classic rule... */ 1521 if (tcp_fackets_out(tp) > tp->reordering) 1522 return 1; 1523 1524 /* Trick#3 : when we use RFC2988 timer restart, fast 1525 * retransmit can be triggered by timeout of queue head. 1526 */ 1527 if (tcp_head_timedout(sk, tp)) 1528 return 1; 1529 1530 /* Trick#4: It is still not OK... But will it be useful to delay 1531 * recovery more? 1532 */ 1533 packets_out = tp->packets_out; 1534 if (packets_out <= tp->reordering && 1535 tp->sacked_out >= max_t(__u32, packets_out/2, sysctl_tcp_reordering) && 1536 !tcp_may_send_now(sk, tp)) { 1537 /* We have nothing to send. This connection is limited 1538 * either by receiver window or by application. 1539 */ 1540 return 1; 1541 } 1542 1543 return 0; 1544} 1545 1546/* If we receive more dupacks than we expected counting segments 1547 * in assumption of absent reordering, interpret this as reordering. 1548 * The only another reason could be bug in receiver TCP. 1549 */ 1550static void tcp_check_reno_reordering(struct sock *sk, const int addend) 1551{ 1552 struct tcp_sock *tp = tcp_sk(sk); 1553 u32 holes; 1554 1555 holes = max(tp->lost_out, 1U); 1556 holes = min(holes, tp->packets_out); 1557 1558 if ((tp->sacked_out + holes) > tp->packets_out) { 1559 tp->sacked_out = tp->packets_out - holes; 1560 tcp_update_reordering(sk, tp->packets_out + addend, 0); 1561 } 1562} 1563 1564/* Emulate SACKs for SACKless connection: account for a new dupack. */ 1565 1566static void tcp_add_reno_sack(struct sock *sk) 1567{ 1568 struct tcp_sock *tp = tcp_sk(sk); 1569 tp->sacked_out++; 1570 tcp_check_reno_reordering(sk, 0); 1571 tcp_sync_left_out(tp); 1572} 1573 1574/* Account for ACK, ACKing some data in Reno Recovery phase. */ 1575 1576static void tcp_remove_reno_sacks(struct sock *sk, struct tcp_sock *tp, int acked) 1577{ 1578 if (acked > 0) { 1579 /* One ACK acked hole. The rest eat duplicate ACKs. */ 1580 if (acked-1 >= tp->sacked_out) 1581 tp->sacked_out = 0; 1582 else 1583 tp->sacked_out -= acked-1; 1584 } 1585 tcp_check_reno_reordering(sk, acked); 1586 tcp_sync_left_out(tp); 1587} 1588 1589static inline void tcp_reset_reno_sack(struct tcp_sock *tp) 1590{ 1591 tp->sacked_out = 0; 1592 tp->left_out = tp->lost_out; 1593} 1594 1595/* Mark head of queue up as lost. */ 1596static void tcp_mark_head_lost(struct sock *sk, struct tcp_sock *tp, 1597 int packets, u32 high_seq) 1598{ 1599 struct sk_buff *skb; 1600 int cnt; 1601 1602 BUG_TRAP(packets <= tp->packets_out); 1603 if (tp->lost_skb_hint) { 1604 skb = tp->lost_skb_hint; 1605 cnt = tp->lost_cnt_hint; 1606 } else { 1607 skb = sk->sk_write_queue.next; 1608 cnt = 0; 1609 } 1610 1611 sk_stream_for_retrans_queue_from(skb, sk) { 1612 /* TODO: do this better */ 1613 /* this is not the most efficient way to do this... */ 1614 tp->lost_skb_hint = skb; 1615 tp->lost_cnt_hint = cnt; 1616 cnt += tcp_skb_pcount(skb); 1617 if (cnt > packets || after(TCP_SKB_CB(skb)->end_seq, high_seq)) 1618 break; 1619 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_TAGBITS)) { 1620 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1621 tp->lost_out += tcp_skb_pcount(skb); 1622 1623 /* clear xmit_retransmit_queue hints 1624 * if this is beyond hint */ 1625 if(tp->retransmit_skb_hint != NULL && 1626 before(TCP_SKB_CB(skb)->seq, 1627 TCP_SKB_CB(tp->retransmit_skb_hint)->seq)) { 1628 1629 tp->retransmit_skb_hint = NULL; 1630 } 1631 } 1632 } 1633 tcp_sync_left_out(tp); 1634} 1635 1636/* Account newly detected lost packet(s) */ 1637 1638static void tcp_update_scoreboard(struct sock *sk, struct tcp_sock *tp) 1639{ 1640 if (IsFack(tp)) { 1641 int lost = tp->fackets_out - tp->reordering; 1642 if (lost <= 0) 1643 lost = 1; 1644 tcp_mark_head_lost(sk, tp, lost, tp->high_seq); 1645 } else { 1646 tcp_mark_head_lost(sk, tp, 1, tp->high_seq); 1647 } 1648 1649 /* New heuristics: it is possible only after we switched 1650 * to restart timer each time when something is ACKed. 1651 * Hence, we can detect timed out packets during fast 1652 * retransmit without falling to slow start. 1653 */ 1654 if (!IsReno(tp) && tcp_head_timedout(sk, tp)) { 1655 struct sk_buff *skb; 1656 1657 skb = tp->scoreboard_skb_hint ? tp->scoreboard_skb_hint 1658 : sk->sk_write_queue.next; 1659 1660 sk_stream_for_retrans_queue_from(skb, sk) { 1661 if (!tcp_skb_timedout(sk, skb)) 1662 break; 1663 1664 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_TAGBITS)) { 1665 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST; 1666 tp->lost_out += tcp_skb_pcount(skb); 1667 1668 /* clear xmit_retrans hint */ 1669 if (tp->retransmit_skb_hint && 1670 before(TCP_SKB_CB(skb)->seq, 1671 TCP_SKB_CB(tp->retransmit_skb_hint)->seq)) 1672 1673 tp->retransmit_skb_hint = NULL; 1674 } 1675 } 1676 1677 tp->scoreboard_skb_hint = skb; 1678 1679 tcp_sync_left_out(tp); 1680 } 1681} 1682 1683/* CWND moderation, preventing bursts due to too big ACKs 1684 * in dubious situations. 1685 */ 1686static inline void tcp_moderate_cwnd(struct tcp_sock *tp) 1687{ 1688 tp->snd_cwnd = min(tp->snd_cwnd, 1689 tcp_packets_in_flight(tp)+tcp_max_burst(tp)); 1690 tp->snd_cwnd_stamp = tcp_time_stamp; 1691} 1692 1693/* Lower bound on congestion window is slow start threshold 1694 * unless congestion avoidance choice decides to overide it. 1695 */ 1696static inline u32 tcp_cwnd_min(const struct sock *sk) 1697{ 1698 const struct tcp_congestion_ops *ca_ops = inet_csk(sk)->icsk_ca_ops; 1699 1700 return ca_ops->min_cwnd ? ca_ops->min_cwnd(sk) : tcp_sk(sk)->snd_ssthresh; 1701} 1702 1703/* Decrease cwnd each second ack. */ 1704static void tcp_cwnd_down(struct sock *sk) 1705{ 1706 struct tcp_sock *tp = tcp_sk(sk); 1707 int decr = tp->snd_cwnd_cnt + 1; 1708 1709 tp->snd_cwnd_cnt = decr&1; 1710 decr >>= 1; 1711 1712 if (decr && tp->snd_cwnd > tcp_cwnd_min(sk)) 1713 tp->snd_cwnd -= decr; 1714 1715 tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp)+1); 1716 tp->snd_cwnd_stamp = tcp_time_stamp; 1717} 1718 1719/* Nothing was retransmitted or returned timestamp is less 1720 * than timestamp of the first retransmission. 1721 */ 1722static inline int tcp_packet_delayed(struct tcp_sock *tp) 1723{ 1724 return !tp->retrans_stamp || 1725 (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 1726 (__s32)(tp->rx_opt.rcv_tsecr - tp->retrans_stamp) < 0); 1727} 1728 1729/* Undo procedures. */ 1730 1731#if FASTRETRANS_DEBUG > 1 1732static void DBGUNDO(struct sock *sk, struct tcp_sock *tp, const char *msg) 1733{ 1734 struct inet_sock *inet = inet_sk(sk); 1735 printk(KERN_DEBUG "Undo %s %u.%u.%u.%u/%u c%u l%u ss%u/%u p%u\n", 1736 msg, 1737 NIPQUAD(inet->daddr), ntohs(inet->dport), 1738 tp->snd_cwnd, tp->left_out, 1739 tp->snd_ssthresh, tp->prior_ssthresh, 1740 tp->packets_out); 1741} 1742#else 1743#define DBGUNDO(x...) do { } while (0) 1744#endif 1745 1746static void tcp_undo_cwr(struct sock *sk, const int undo) 1747{ 1748 struct tcp_sock *tp = tcp_sk(sk); 1749 1750 if (tp->prior_ssthresh) { 1751 const struct inet_connection_sock *icsk = inet_csk(sk); 1752 1753 if (icsk->icsk_ca_ops->undo_cwnd) 1754 tp->snd_cwnd = icsk->icsk_ca_ops->undo_cwnd(sk); 1755 else 1756 tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh<<1); 1757 1758 if (undo && tp->prior_ssthresh > tp->snd_ssthresh) { 1759 tp->snd_ssthresh = tp->prior_ssthresh; 1760 TCP_ECN_withdraw_cwr(tp); 1761 } 1762 } else { 1763 tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh); 1764 } 1765 tcp_moderate_cwnd(tp); 1766 tp->snd_cwnd_stamp = tcp_time_stamp; 1767 1768 /* There is something screwy going on with the retrans hints after 1769 an undo */ 1770 clear_all_retrans_hints(tp); 1771} 1772 1773static inline int tcp_may_undo(struct tcp_sock *tp) 1774{ 1775 return tp->undo_marker && 1776 (!tp->undo_retrans || tcp_packet_delayed(tp)); 1777} 1778 1779/* People celebrate: "We love our President!" */ 1780static int tcp_try_undo_recovery(struct sock *sk, struct tcp_sock *tp) 1781{ 1782 if (tcp_may_undo(tp)) { 1783 /* Happy end! We did not retransmit anything 1784 * or our original transmission succeeded. 1785 */ 1786 DBGUNDO(sk, tp, inet_csk(sk)->icsk_ca_state == TCP_CA_Loss ? "loss" : "retrans"); 1787 tcp_undo_cwr(sk, 1); 1788 if (inet_csk(sk)->icsk_ca_state == TCP_CA_Loss) 1789 NET_INC_STATS_BH(LINUX_MIB_TCPLOSSUNDO); 1790 else 1791 NET_INC_STATS_BH(LINUX_MIB_TCPFULLUNDO); 1792 tp->undo_marker = 0; 1793 } 1794 if (tp->snd_una == tp->high_seq && IsReno(tp)) { 1795 /* Hold old state until something *above* high_seq 1796 * is ACKed. For Reno it is MUST to prevent false 1797 * fast retransmits (RFC2582). SACK TCP is safe. */ 1798 tcp_moderate_cwnd(tp); 1799 return 1; 1800 } 1801 tcp_set_ca_state(sk, TCP_CA_Open); 1802 return 0; 1803} 1804 1805/* Try to undo cwnd reduction, because D-SACKs acked all retransmitted data */ 1806static void tcp_try_undo_dsack(struct sock *sk, struct tcp_sock *tp) 1807{ 1808 if (tp->undo_marker && !tp->undo_retrans) { 1809 DBGUNDO(sk, tp, "D-SACK"); 1810 tcp_undo_cwr(sk, 1); 1811 tp->undo_marker = 0; 1812 NET_INC_STATS_BH(LINUX_MIB_TCPDSACKUNDO); 1813 } 1814} 1815 1816/* Undo during fast recovery after partial ACK. */ 1817 1818static int tcp_try_undo_partial(struct sock *sk, struct tcp_sock *tp, 1819 int acked) 1820{ 1821 /* Partial ACK arrived. Force Hoe's retransmit. */ 1822 int failed = IsReno(tp) || tp->fackets_out>tp->reordering; 1823 1824 if (tcp_may_undo(tp)) { 1825 /* Plain luck! Hole if filled with delayed 1826 * packet, rather than with a retransmit. 1827 */ 1828 if (tp->retrans_out == 0) 1829 tp->retrans_stamp = 0; 1830 1831 tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1); 1832 1833 DBGUNDO(sk, tp, "Hoe"); 1834 tcp_undo_cwr(sk, 0); 1835 NET_INC_STATS_BH(LINUX_MIB_TCPPARTIALUNDO); 1836 1837 /* So... Do not make Hoe's retransmit yet. 1838 * If the first packet was delayed, the rest 1839 * ones are most probably delayed as well. 1840 */ 1841 failed = 0; 1842 } 1843 return failed; 1844} 1845 1846/* Undo during loss recovery after partial ACK. */ 1847static int tcp_try_undo_loss(struct sock *sk, struct tcp_sock *tp) 1848{ 1849 if (tcp_may_undo(tp)) { 1850 struct sk_buff *skb; 1851 sk_stream_for_retrans_queue(skb, sk) { 1852 TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST; 1853 } 1854 1855 clear_all_retrans_hints(tp); 1856 1857 DBGUNDO(sk, tp, "partial loss"); 1858 tp->lost_out = 0; 1859 tp->left_out = tp->sacked_out; 1860 tcp_undo_cwr(sk, 1); 1861 NET_INC_STATS_BH(LINUX_MIB_TCPLOSSUNDO); 1862 inet_csk(sk)->icsk_retransmits = 0; 1863 tp->undo_marker = 0; 1864 if (!IsReno(tp)) 1865 tcp_set_ca_state(sk, TCP_CA_Open); 1866 return 1; 1867 } 1868 return 0; 1869} 1870 1871static inline void tcp_complete_cwr(struct sock *sk) 1872{ 1873 struct tcp_sock *tp = tcp_sk(sk); 1874 tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh); 1875 tp->snd_cwnd_stamp = tcp_time_stamp; 1876 tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR); 1877} 1878 1879static void tcp_try_to_open(struct sock *sk, struct tcp_sock *tp, int flag) 1880{ 1881 tp->left_out = tp->sacked_out; 1882 1883 if (tp->retrans_out == 0) 1884 tp->retrans_stamp = 0; 1885 1886 if (flag&FLAG_ECE) 1887 tcp_enter_cwr(sk); 1888 1889 if (inet_csk(sk)->icsk_ca_state != TCP_CA_CWR) { 1890 int state = TCP_CA_Open; 1891 1892 if (tp->left_out || tp->retrans_out || tp->undo_marker) 1893 state = TCP_CA_Disorder; 1894 1895 if (inet_csk(sk)->icsk_ca_state != state) { 1896 tcp_set_ca_state(sk, state); 1897 tp->high_seq = tp->snd_nxt; 1898 } 1899 tcp_moderate_cwnd(tp); 1900 } else { 1901 tcp_cwnd_down(sk); 1902 } 1903} 1904 1905static void tcp_mtup_probe_failed(struct sock *sk) 1906{ 1907 struct inet_connection_sock *icsk = inet_csk(sk); 1908 1909 icsk->icsk_mtup.search_high = icsk->icsk_mtup.probe_size - 1; 1910 icsk->icsk_mtup.probe_size = 0; 1911} 1912 1913static void tcp_mtup_probe_success(struct sock *sk, struct sk_buff *skb) 1914{ 1915 struct tcp_sock *tp = tcp_sk(sk); 1916 struct inet_connection_sock *icsk = inet_csk(sk); 1917 1918 /* FIXME: breaks with very large cwnd */ 1919 tp->prior_ssthresh = tcp_current_ssthresh(sk); 1920 tp->snd_cwnd = tp->snd_cwnd * 1921 tcp_mss_to_mtu(sk, tp->mss_cache) / 1922 icsk->icsk_mtup.probe_size; 1923 tp->snd_cwnd_cnt = 0; 1924 tp->snd_cwnd_stamp = tcp_time_stamp; 1925 tp->rcv_ssthresh = tcp_current_ssthresh(sk); 1926 1927 icsk->icsk_mtup.search_low = icsk->icsk_mtup.probe_size; 1928 icsk->icsk_mtup.probe_size = 0; 1929 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 1930} 1931 1932 1933/* Process an event, which can update packets-in-flight not trivially. 1934 * Main goal of this function is to calculate new estimate for left_out, 1935 * taking into account both packets sitting in receiver's buffer and 1936 * packets lost by network. 1937 * 1938 * Besides that it does CWND reduction, when packet loss is detected 1939 * and changes state of machine. 1940 * 1941 * It does _not_ decide what to send, it is made in function 1942 * tcp_xmit_retransmit_queue(). 1943 */ 1944static void 1945tcp_fastretrans_alert(struct sock *sk, u32 prior_snd_una, 1946 int prior_packets, int flag) 1947{ 1948 struct inet_connection_sock *icsk = inet_csk(sk); 1949 struct tcp_sock *tp = tcp_sk(sk); 1950 int is_dupack = (tp->snd_una == prior_snd_una && !(flag&FLAG_NOT_DUP)); 1951 1952 /* Some technical things: 1953 * 1. Reno does not count dupacks (sacked_out) automatically. */ 1954 if (!tp->packets_out) 1955 tp->sacked_out = 0; 1956 /* 2. SACK counts snd_fack in packets inaccurately. */ 1957 if (tp->sacked_out == 0) 1958 tp->fackets_out = 0; 1959 1960 /* Now state machine starts. 1961 * A. ECE, hence prohibit cwnd undoing, the reduction is required. */ 1962 if (flag&FLAG_ECE) 1963 tp->prior_ssthresh = 0; 1964 1965 /* B. In all the states check for reneging SACKs. */ 1966 if (tp->sacked_out && tcp_check_sack_reneging(sk)) 1967 return; 1968 1969 /* C. Process data loss notification, provided it is valid. */ 1970 if ((flag&FLAG_DATA_LOST) && 1971 before(tp->snd_una, tp->high_seq) && 1972 icsk->icsk_ca_state != TCP_CA_Open && 1973 tp->fackets_out > tp->reordering) { 1974 tcp_mark_head_lost(sk, tp, tp->fackets_out-tp->reordering, tp->high_seq); 1975 NET_INC_STATS_BH(LINUX_MIB_TCPLOSS); 1976 } 1977 1978 /* D. Synchronize left_out to current state. */ 1979 tcp_sync_left_out(tp); 1980 1981 /* E. Check state exit conditions. State can be terminated 1982 * when high_seq is ACKed. */ 1983 if (icsk->icsk_ca_state == TCP_CA_Open) { 1984 if (!sysctl_tcp_frto) 1985 BUG_TRAP(tp->retrans_out == 0); 1986 tp->retrans_stamp = 0; 1987 } else if (!before(tp->snd_una, tp->high_seq)) { 1988 switch (icsk->icsk_ca_state) { 1989 case TCP_CA_Loss: 1990 icsk->icsk_retransmits = 0; 1991 if (tcp_try_undo_recovery(sk, tp)) 1992 return; 1993 break; 1994 1995 case TCP_CA_CWR: 1996 /* CWR is to be held something *above* high_seq 1997 * is ACKed for CWR bit to reach receiver. */ 1998 if (tp->snd_una != tp->high_seq) { 1999 tcp_complete_cwr(sk); 2000 tcp_set_ca_state(sk, TCP_CA_Open); 2001 } 2002 break; 2003 2004 case TCP_CA_Disorder: 2005 tcp_try_undo_dsack(sk, tp); 2006 if (!tp->undo_marker || 2007 /* For SACK case do not Open to allow to undo 2008 * catching for all duplicate ACKs. */ 2009 IsReno(tp) || tp->snd_una != tp->high_seq) { 2010 tp->undo_marker = 0; 2011 tcp_set_ca_state(sk, TCP_CA_Open); 2012 } 2013 break; 2014 2015 case TCP_CA_Recovery: 2016 if (IsReno(tp)) 2017 tcp_reset_reno_sack(tp); 2018 if (tcp_try_undo_recovery(sk, tp)) 2019 return; 2020 tcp_complete_cwr(sk); 2021 break; 2022 } 2023 } 2024 2025 /* F. Process state. */ 2026 switch (icsk->icsk_ca_state) { 2027 case TCP_CA_Recovery: 2028 if (prior_snd_una == tp->snd_una) { 2029 if (IsReno(tp) && is_dupack) 2030 tcp_add_reno_sack(sk); 2031 } else { 2032 int acked = prior_packets - tp->packets_out; 2033 if (IsReno(tp)) 2034 tcp_remove_reno_sacks(sk, tp, acked); 2035 is_dupack = tcp_try_undo_partial(sk, tp, acked); 2036 } 2037 break; 2038 case TCP_CA_Loss: 2039 if (flag&FLAG_DATA_ACKED) 2040 icsk->icsk_retransmits = 0; 2041 if (!tcp_try_undo_loss(sk, tp)) { 2042 tcp_moderate_cwnd(tp); 2043 tcp_xmit_retransmit_queue(sk); 2044 return; 2045 } 2046 if (icsk->icsk_ca_state != TCP_CA_Open) 2047 return; 2048 /* Loss is undone; fall through to processing in Open state. */ 2049 default: 2050 if (IsReno(tp)) { 2051 if (tp->snd_una != prior_snd_una) 2052 tcp_reset_reno_sack(tp); 2053 if (is_dupack) 2054 tcp_add_reno_sack(sk); 2055 } 2056 2057 if (icsk->icsk_ca_state == TCP_CA_Disorder) 2058 tcp_try_undo_dsack(sk, tp); 2059 2060 if (!tcp_time_to_recover(sk, tp)) { 2061 tcp_try_to_open(sk, tp, flag); 2062 return; 2063 } 2064 2065 /* MTU probe failure: don't reduce cwnd */ 2066 if (icsk->icsk_ca_state < TCP_CA_CWR && 2067 icsk->icsk_mtup.probe_size && 2068 tp->snd_una == tp->mtu_probe.probe_seq_start) { 2069 tcp_mtup_probe_failed(sk); 2070 /* Restores the reduction we did in tcp_mtup_probe() */ 2071 tp->snd_cwnd++; 2072 tcp_simple_retransmit(sk); 2073 return; 2074 } 2075 2076 /* Otherwise enter Recovery state */ 2077 2078 if (IsReno(tp)) 2079 NET_INC_STATS_BH(LINUX_MIB_TCPRENORECOVERY); 2080 else 2081 NET_INC_STATS_BH(LINUX_MIB_TCPSACKRECOVERY); 2082 2083 tp->high_seq = tp->snd_nxt; 2084 tp->prior_ssthresh = 0; 2085 tp->undo_marker = tp->snd_una; 2086 tp->undo_retrans = tp->retrans_out; 2087 2088 if (icsk->icsk_ca_state < TCP_CA_CWR) { 2089 if (!(flag&FLAG_ECE)) 2090 tp->prior_ssthresh = tcp_current_ssthresh(sk); 2091 tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk); 2092 TCP_ECN_queue_cwr(tp); 2093 } 2094 2095 tp->bytes_acked = 0; 2096 tp->snd_cwnd_cnt = 0; 2097 tcp_set_ca_state(sk, TCP_CA_Recovery); 2098 } 2099 2100 if (is_dupack || tcp_head_timedout(sk, tp)) 2101 tcp_update_scoreboard(sk, tp); 2102 tcp_cwnd_down(sk); 2103 tcp_xmit_retransmit_queue(sk); 2104} 2105 2106/* Read draft-ietf-tcplw-high-performance before mucking 2107 * with this code. (Supersedes RFC1323) 2108 */ 2109static void tcp_ack_saw_tstamp(struct sock *sk, int flag) 2110{ 2111 /* RTTM Rule: A TSecr value received in a segment is used to 2112 * update the averaged RTT measurement only if the segment 2113 * acknowledges some new data, i.e., only if it advances the 2114 * left edge of the send window. 2115 * 2116 * See draft-ietf-tcplw-high-performance-00, section 3.3. 2117 * 1998/04/10 Andrey V. Savochkin <saw@msu.ru> 2118 * 2119 * Changed: reset backoff as soon as we see the first valid sample. 2120 * If we do not, we get strongly overestimated rto. With timestamps 2121 * samples are accepted even from very old segments: f.e., when rtt=1 2122 * increases to 8, we retransmit 5 times and after 8 seconds delayed 2123 * answer arrives rto becomes 120 seconds! If at least one of segments 2124 * in window is lost... Voila. --ANK (010210) 2125 */ 2126 struct tcp_sock *tp = tcp_sk(sk); 2127 const __u32 seq_rtt = tcp_time_stamp - tp->rx_opt.rcv_tsecr; 2128 tcp_rtt_estimator(sk, seq_rtt); 2129 tcp_set_rto(sk); 2130 inet_csk(sk)->icsk_backoff = 0; 2131 tcp_bound_rto(sk); 2132} 2133 2134static void tcp_ack_no_tstamp(struct sock *sk, u32 seq_rtt, int flag) 2135{ 2136 /* We don't have a timestamp. Can only use 2137 * packets that are not retransmitted to determine 2138 * rtt estimates. Also, we must not reset the 2139 * backoff for rto until we get a non-retransmitted 2140 * packet. This allows us to deal with a situation 2141 * where the network delay has increased suddenly. 2142 * I.e. Karn's algorithm. (SIGCOMM '87, p5.) 2143 */ 2144 2145 if (flag & FLAG_RETRANS_DATA_ACKED) 2146 return; 2147 2148 tcp_rtt_estimator(sk, seq_rtt); 2149 tcp_set_rto(sk); 2150 inet_csk(sk)->icsk_backoff = 0; 2151 tcp_bound_rto(sk); 2152} 2153 2154static inline void tcp_ack_update_rtt(struct sock *sk, const int flag, 2155 const s32 seq_rtt) 2156{ 2157 const struct tcp_sock *tp = tcp_sk(sk); 2158 /* Note that peer MAY send zero echo. In this case it is ignored. (rfc1323) */ 2159 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr) 2160 tcp_ack_saw_tstamp(sk, flag); 2161 else if (seq_rtt >= 0) 2162 tcp_ack_no_tstamp(sk, seq_rtt, flag); 2163} 2164 2165static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 rtt, 2166 u32 in_flight, int good) 2167{ 2168 const struct inet_connection_sock *icsk = inet_csk(sk); 2169 icsk->icsk_ca_ops->cong_avoid(sk, ack, rtt, in_flight, good); 2170 tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp; 2171} 2172 2173/* Restart timer after forward progress on connection. 2174 * RFC2988 recommends to restart timer to now+rto. 2175 */ 2176 2177static void tcp_ack_packets_out(struct sock *sk, struct tcp_sock *tp) 2178{ 2179 if (!tp->packets_out) { 2180 inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS); 2181 } else { 2182 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, inet_csk(sk)->icsk_rto, TCP_RTO_MAX); 2183 } 2184} 2185 2186static int tcp_tso_acked(struct sock *sk, struct sk_buff *skb, 2187 __u32 now, __s32 *seq_rtt) 2188{ 2189 struct tcp_sock *tp = tcp_sk(sk); 2190 struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 2191 __u32 seq = tp->snd_una; 2192 __u32 packets_acked; 2193 int acked = 0; 2194 2195 /* If we get here, the whole TSO packet has not been 2196 * acked. 2197 */ 2198 BUG_ON(!after(scb->end_seq, seq)); 2199 2200 packets_acked = tcp_skb_pcount(skb); 2201 if (tcp_trim_head(sk, skb, seq - scb->seq)) 2202 return 0; 2203 packets_acked -= tcp_skb_pcount(skb); 2204 2205 if (packets_acked) { 2206 __u8 sacked = scb->sacked; 2207 2208 acked |= FLAG_DATA_ACKED; 2209 if (sacked) { 2210 if (sacked & TCPCB_RETRANS) { 2211 if (sacked & TCPCB_SACKED_RETRANS) 2212 tp->retrans_out -= packets_acked; 2213 acked |= FLAG_RETRANS_DATA_ACKED; 2214 *seq_rtt = -1; 2215 } else if (*seq_rtt < 0) 2216 *seq_rtt = now - scb->when; 2217 if (sacked & TCPCB_SACKED_ACKED) 2218 tp->sacked_out -= packets_acked; 2219 if (sacked & TCPCB_LOST) 2220 tp->lost_out -= packets_acked; 2221 if (sacked & TCPCB_URG) { 2222 if (tp->urg_mode && 2223 !before(seq, tp->snd_up)) 2224 tp->urg_mode = 0; 2225 } 2226 } else if (*seq_rtt < 0) 2227 *seq_rtt = now - scb->when; 2228 2229 if (tp->fackets_out) { 2230 __u32 dval = min(tp->fackets_out, packets_acked); 2231 tp->fackets_out -= dval; 2232 } 2233 tp->packets_out -= packets_acked; 2234 2235 BUG_ON(tcp_skb_pcount(skb) == 0); 2236 BUG_ON(!before(scb->seq, scb->end_seq)); 2237 } 2238 2239 return acked; 2240} 2241 2242static u32 tcp_usrtt(struct timeval *tv) 2243{ 2244 struct timeval now; 2245 2246 do_gettimeofday(&now); 2247 return (now.tv_sec - tv->tv_sec) * 1000000 + (now.tv_usec - tv->tv_usec); 2248} 2249 2250/* Remove acknowledged frames from the retransmission queue. */ 2251static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p) 2252{ 2253 struct tcp_sock *tp = tcp_sk(sk); 2254 const struct inet_connection_sock *icsk = inet_csk(sk); 2255 struct sk_buff *skb; 2256 __u32 now = tcp_time_stamp; 2257 int acked = 0; 2258 __s32 seq_rtt = -1; 2259 u32 pkts_acked = 0; 2260 void (*rtt_sample)(struct sock *sk, u32 usrtt) 2261 = icsk->icsk_ca_ops->rtt_sample; 2262 struct timeval tv = { .tv_sec = 0, .tv_usec = 0 }; 2263 2264 while ((skb = skb_peek(&sk->sk_write_queue)) && 2265 skb != sk->sk_send_head) { 2266 struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 2267 __u8 sacked = scb->sacked; 2268 2269 /* If our packet is before the ack sequence we can 2270 * discard it as it's confirmed to have arrived at 2271 * the other end. 2272 */ 2273 if (after(scb->end_seq, tp->snd_una)) { 2274 if (tcp_skb_pcount(skb) > 1 && 2275 after(tp->snd_una, scb->seq)) 2276 acked |= tcp_tso_acked(sk, skb, 2277 now, &seq_rtt); 2278 break; 2279 } 2280 2281 /* Initial outgoing SYN's get put onto the write_queue 2282 * just like anything else we transmit. It is not 2283 * true data, and if we misinform our callers that 2284 * this ACK acks real data, we will erroneously exit 2285 * connection startup slow start one packet too 2286 * quickly. This is severely frowned upon behavior. 2287 */ 2288 if (!(scb->flags & TCPCB_FLAG_SYN)) { 2289 acked |= FLAG_DATA_ACKED; 2290 ++pkts_acked; 2291 } else { 2292 acked |= FLAG_SYN_ACKED; 2293 tp->retrans_stamp = 0; 2294 } 2295 2296 /* MTU probing checks */ 2297 if (icsk->icsk_mtup.probe_size) { 2298 if (!after(tp->mtu_probe.probe_seq_end, TCP_SKB_CB(skb)->end_seq)) { 2299 tcp_mtup_probe_success(sk, skb); 2300 } 2301 } 2302 2303 if (sacked) { 2304 if (sacked & TCPCB_RETRANS) { 2305 if(sacked & TCPCB_SACKED_RETRANS) 2306 tp->retrans_out -= tcp_skb_pcount(skb); 2307 acked |= FLAG_RETRANS_DATA_ACKED; 2308 seq_rtt = -1; 2309 } else if (seq_rtt < 0) { 2310 seq_rtt = now - scb->when; 2311 skb_get_timestamp(skb, &tv); 2312 } 2313 if (sacked & TCPCB_SACKED_ACKED) 2314 tp->sacked_out -= tcp_skb_pcount(skb); 2315 if (sacked & TCPCB_LOST) 2316 tp->lost_out -= tcp_skb_pcount(skb); 2317 if (sacked & TCPCB_URG) { 2318 if (tp->urg_mode && 2319 !before(scb->end_seq, tp->snd_up)) 2320 tp->urg_mode = 0; 2321 } 2322 } else if (seq_rtt < 0) { 2323 seq_rtt = now - scb->when; 2324 skb_get_timestamp(skb, &tv); 2325 } 2326 tcp_dec_pcount_approx(&tp->fackets_out, skb); 2327 tcp_packets_out_dec(tp, skb); 2328 __skb_unlink(skb, &sk->sk_write_queue); 2329 sk_stream_free_skb(sk, skb); 2330 clear_all_retrans_hints(tp); 2331 } 2332 2333 if (acked&FLAG_ACKED) { 2334 tcp_ack_update_rtt(sk, acked, seq_rtt); 2335 tcp_ack_packets_out(sk, tp); 2336 if (rtt_sample && !(acked & FLAG_RETRANS_DATA_ACKED)) 2337 (*rtt_sample)(sk, tcp_usrtt(&tv)); 2338 2339 if (icsk->icsk_ca_ops->pkts_acked) 2340 icsk->icsk_ca_ops->pkts_acked(sk, pkts_acked); 2341 } 2342 2343#if FASTRETRANS_DEBUG > 0 2344 BUG_TRAP((int)tp->sacked_out >= 0); 2345 BUG_TRAP((int)tp->lost_out >= 0); 2346 BUG_TRAP((int)tp->retrans_out >= 0); 2347 if (!tp->packets_out && tp->rx_opt.sack_ok) { 2348 const struct inet_connection_sock *icsk = inet_csk(sk); 2349 if (tp->lost_out) { 2350 printk(KERN_DEBUG "Leak l=%u %d\n", 2351 tp->lost_out, icsk->icsk_ca_state); 2352 tp->lost_out = 0; 2353 } 2354 if (tp->sacked_out) { 2355 printk(KERN_DEBUG "Leak s=%u %d\n", 2356 tp->sacked_out, icsk->icsk_ca_state); 2357 tp->sacked_out = 0; 2358 } 2359 if (tp->retrans_out) { 2360 printk(KERN_DEBUG "Leak r=%u %d\n", 2361 tp->retrans_out, icsk->icsk_ca_state); 2362 tp->retrans_out = 0; 2363 } 2364 } 2365#endif 2366 *seq_rtt_p = seq_rtt; 2367 return acked; 2368} 2369 2370static void tcp_ack_probe(struct sock *sk) 2371{ 2372 const struct tcp_sock *tp = tcp_sk(sk); 2373 struct inet_connection_sock *icsk = inet_csk(sk); 2374 2375 /* Was it a usable window open? */ 2376 2377 if (!after(TCP_SKB_CB(sk->sk_send_head)->end_seq, 2378 tp->snd_una + tp->snd_wnd)) { 2379 icsk->icsk_backoff = 0; 2380 inet_csk_clear_xmit_timer(sk, ICSK_TIME_PROBE0); 2381 /* Socket must be waked up by subsequent tcp_data_snd_check(). 2382 * This function is not for random using! 2383 */ 2384 } else { 2385 inet_csk_reset_xmit_timer(sk, ICSK_TIME_PROBE0, 2386 min(icsk->icsk_rto << icsk->icsk_backoff, TCP_RTO_MAX), 2387 TCP_RTO_MAX); 2388 } 2389} 2390 2391static inline int tcp_ack_is_dubious(const struct sock *sk, const int flag) 2392{ 2393 return (!(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) || 2394 inet_csk(sk)->icsk_ca_state != TCP_CA_Open); 2395} 2396 2397static inline int tcp_may_raise_cwnd(const struct sock *sk, const int flag) 2398{ 2399 const struct tcp_sock *tp = tcp_sk(sk); 2400 return (!(flag & FLAG_ECE) || tp->snd_cwnd < tp->snd_ssthresh) && 2401 !((1 << inet_csk(sk)->icsk_ca_state) & (TCPF_CA_Recovery | TCPF_CA_CWR)); 2402} 2403 2404/* Check that window update is acceptable. 2405 * The function assumes that snd_una<=ack<=snd_next. 2406 */ 2407static inline int tcp_may_update_window(const struct tcp_sock *tp, const u32 ack, 2408 const u32 ack_seq, const u32 nwin) 2409{ 2410 return (after(ack, tp->snd_una) || 2411 after(ack_seq, tp->snd_wl1) || 2412 (ack_seq == tp->snd_wl1 && nwin > tp->snd_wnd)); 2413} 2414 2415/* Update our send window. 2416 * 2417 * Window update algorithm, described in RFC793/RFC1122 (used in linux-2.2 2418 * and in FreeBSD. NetBSD's one is even worse.) is wrong. 2419 */ 2420static int tcp_ack_update_window(struct sock *sk, struct tcp_sock *tp, 2421 struct sk_buff *skb, u32 ack, u32 ack_seq) 2422{ 2423 int flag = 0; 2424 u32 nwin = ntohs(skb->h.th->window); 2425 2426 if (likely(!skb->h.th->syn)) 2427 nwin <<= tp->rx_opt.snd_wscale; 2428 2429 if (tcp_may_update_window(tp, ack, ack_seq, nwin)) { 2430 flag |= FLAG_WIN_UPDATE; 2431 tcp_update_wl(tp, ack, ack_seq); 2432 2433 if (tp->snd_wnd != nwin) { 2434 tp->snd_wnd = nwin; 2435 2436 /* Note, it is the only place, where 2437 * fast path is recovered for sending TCP. 2438 */ 2439 tp->pred_flags = 0; 2440 tcp_fast_path_check(sk, tp); 2441 2442 if (nwin > tp->max_window) { 2443 tp->max_window = nwin; 2444 tcp_sync_mss(sk, inet_csk(sk)->icsk_pmtu_cookie); 2445 } 2446 } 2447 } 2448 2449 tp->snd_una = ack; 2450 2451 return flag; 2452} 2453 2454static void tcp_process_frto(struct sock *sk, u32 prior_snd_una) 2455{ 2456 struct tcp_sock *tp = tcp_sk(sk); 2457 2458 tcp_sync_left_out(tp); 2459 2460 if (tp->snd_una == prior_snd_una || 2461 !before(tp->snd_una, tp->frto_highmark)) { 2462 /* RTO was caused by loss, start retransmitting in 2463 * go-back-N slow start 2464 */ 2465 tcp_enter_frto_loss(sk); 2466 return; 2467 } 2468 2469 if (tp->frto_counter == 1) { 2470 /* First ACK after RTO advances the window: allow two new 2471 * segments out. 2472 */ 2473 tp->snd_cwnd = tcp_packets_in_flight(tp) + 2; 2474 } else { 2475 /* Also the second ACK after RTO advances the window. 2476 * The RTO was likely spurious. Reduce cwnd and continue 2477 * in congestion avoidance 2478 */ 2479 tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh); 2480 tcp_moderate_cwnd(tp); 2481 } 2482 2483 /* F-RTO affects on two new ACKs following RTO. 2484 * At latest on third ACK the TCP behavior is back to normal. 2485 */ 2486 tp->frto_counter = (tp->frto_counter + 1) % 3; 2487} 2488 2489/* This routine deals with incoming acks, but not outgoing ones. */ 2490static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag) 2491{ 2492 struct inet_connection_sock *icsk = inet_csk(sk); 2493 struct tcp_sock *tp = tcp_sk(sk); 2494 u32 prior_snd_una = tp->snd_una; 2495 u32 ack_seq = TCP_SKB_CB(skb)->seq; 2496 u32 ack = TCP_SKB_CB(skb)->ack_seq; 2497 u32 prior_in_flight; 2498 s32 seq_rtt; 2499 int prior_packets; 2500 2501 /* If the ack is newer than sent or older than previous acks 2502 * then we can probably ignore it. 2503 */ 2504 if (after(ack, tp->snd_nxt)) 2505 goto uninteresting_ack; 2506 2507 if (before(ack, prior_snd_una)) 2508 goto old_ack; 2509 2510 if (sysctl_tcp_abc) { 2511 if (icsk->icsk_ca_state < TCP_CA_CWR) 2512 tp->bytes_acked += ack - prior_snd_una; 2513 else if (icsk->icsk_ca_state == TCP_CA_Loss) 2514 /* we assume just one segment left network */ 2515 tp->bytes_acked += min(ack - prior_snd_una, tp->mss_cache); 2516 } 2517 2518 if (!(flag&FLAG_SLOWPATH) && after(ack, prior_snd_una)) { 2519 /* Window is constant, pure forward advance. 2520 * No more checks are required. 2521 * Note, we use the fact that SND.UNA>=SND.WL2. 2522 */ 2523 tcp_update_wl(tp, ack, ack_seq); 2524 tp->snd_una = ack; 2525 flag |= FLAG_WIN_UPDATE; 2526 2527 tcp_ca_event(sk, CA_EVENT_FAST_ACK); 2528 2529 NET_INC_STATS_BH(LINUX_MIB_TCPHPACKS); 2530 } else { 2531 if (ack_seq != TCP_SKB_CB(skb)->end_seq) 2532 flag |= FLAG_DATA; 2533 else 2534 NET_INC_STATS_BH(LINUX_MIB_TCPPUREACKS); 2535 2536 flag |= tcp_ack_update_window(sk, tp, skb, ack, ack_seq); 2537 2538 if (TCP_SKB_CB(skb)->sacked) 2539 flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una); 2540 2541 if (TCP_ECN_rcv_ecn_echo(tp, skb->h.th)) 2542 flag |= FLAG_ECE; 2543 2544 tcp_ca_event(sk, CA_EVENT_SLOW_ACK); 2545 } 2546 2547 /* We passed data and got it acked, remove any soft error 2548 * log. Something worked... 2549 */ 2550 sk->sk_err_soft = 0; 2551 tp->rcv_tstamp = tcp_time_stamp; 2552 prior_packets = tp->packets_out; 2553 if (!prior_packets) 2554 goto no_queue; 2555 2556 prior_in_flight = tcp_packets_in_flight(tp); 2557 2558 /* See if we can take anything off of the retransmit queue. */ 2559 flag |= tcp_clean_rtx_queue(sk, &seq_rtt); 2560 2561 if (tp->frto_counter) 2562 tcp_process_frto(sk, prior_snd_una); 2563 2564 if (tcp_ack_is_dubious(sk, flag)) { 2565 /* Advance CWND, if state allows this. */ 2566 if ((flag & FLAG_DATA_ACKED) && tcp_may_raise_cwnd(sk, flag)) 2567 tcp_cong_avoid(sk, ack, seq_rtt, prior_in_flight, 0); 2568 tcp_fastretrans_alert(sk, prior_snd_una, prior_packets, flag); 2569 } else { 2570 if ((flag & FLAG_DATA_ACKED)) 2571 tcp_cong_avoid(sk, ack, seq_rtt, prior_in_flight, 1); 2572 } 2573 2574 if ((flag & FLAG_FORWARD_PROGRESS) || !(flag&FLAG_NOT_DUP)) 2575 dst_confirm(sk->sk_dst_cache); 2576 2577 return 1; 2578 2579no_queue: 2580 icsk->icsk_probes_out = 0; 2581 2582 /* If this ack opens up a zero window, clear backoff. It was 2583 * being used to time the probes, and is probably far higher than 2584 * it needs to be for normal retransmission. 2585 */ 2586 if (sk->sk_send_head) 2587 tcp_ack_probe(sk); 2588 return 1; 2589 2590old_ack: 2591 if (TCP_SKB_CB(skb)->sacked) 2592 tcp_sacktag_write_queue(sk, skb, prior_snd_una); 2593 2594uninteresting_ack: 2595 SOCK_DEBUG(sk, "Ack %u out of %u:%u\n", ack, tp->snd_una, tp->snd_nxt); 2596 return 0; 2597} 2598 2599 2600/* Look for tcp options. Normally only called on SYN and SYNACK packets. 2601 * But, this can also be called on packets in the established flow when 2602 * the fast version below fails. 2603 */ 2604void tcp_parse_options(struct sk_buff *skb, struct tcp_options_received *opt_rx, int estab) 2605{ 2606 unsigned char *ptr; 2607 struct tcphdr *th = skb->h.th; 2608 int length=(th->doff*4)-sizeof(struct tcphdr); 2609 2610 ptr = (unsigned char *)(th + 1); 2611 opt_rx->saw_tstamp = 0; 2612 2613 while(length>0) { 2614 int opcode=*ptr++; 2615 int opsize; 2616 2617 switch (opcode) { 2618 case TCPOPT_EOL: 2619 return; 2620 case TCPOPT_NOP: /* Ref: RFC 793 section 3.1 */ 2621 length--; 2622 continue; 2623 default: 2624 opsize=*ptr++; 2625 if (opsize < 2) /* "silly options" */ 2626 return; 2627 if (opsize > length) 2628 return; /* don't parse partial options */ 2629 switch(opcode) { 2630 case TCPOPT_MSS: 2631 if(opsize==TCPOLEN_MSS && th->syn && !estab) { 2632 u16 in_mss = ntohs(get_unaligned((__be16 *)ptr)); 2633 if (in_mss) { 2634 if (opt_rx->user_mss && opt_rx->user_mss < in_mss) 2635 in_mss = opt_rx->user_mss; 2636 opt_rx->mss_clamp = in_mss; 2637 } 2638 } 2639 break; 2640 case TCPOPT_WINDOW: 2641 if(opsize==TCPOLEN_WINDOW && th->syn && !estab) 2642 if (sysctl_tcp_window_scaling) { 2643 __u8 snd_wscale = *(__u8 *) ptr; 2644 opt_rx->wscale_ok = 1; 2645 if (snd_wscale > 14) { 2646 if(net_ratelimit()) 2647 printk(KERN_INFO "tcp_parse_options: Illegal window " 2648 "scaling value %d >14 received.\n", 2649 snd_wscale); 2650 snd_wscale = 14; 2651 } 2652 opt_rx->snd_wscale = snd_wscale; 2653 } 2654 break; 2655 case TCPOPT_TIMESTAMP: 2656 if(opsize==TCPOLEN_TIMESTAMP) { 2657 if ((estab && opt_rx->tstamp_ok) || 2658 (!estab && sysctl_tcp_timestamps)) { 2659 opt_rx->saw_tstamp = 1; 2660 opt_rx->rcv_tsval = ntohl(get_unaligned((__be32 *)ptr)); 2661 opt_rx->rcv_tsecr = ntohl(get_unaligned((__be32 *)(ptr+4))); 2662 } 2663 } 2664 break; 2665 case TCPOPT_SACK_PERM: 2666 if(opsize==TCPOLEN_SACK_PERM && th->syn && !estab) { 2667 if (sysctl_tcp_sack) { 2668 opt_rx->sack_ok = 1; 2669 tcp_sack_reset(opt_rx); 2670 } 2671 } 2672 break; 2673 2674 case TCPOPT_SACK: 2675 if((opsize >= (TCPOLEN_SACK_BASE + TCPOLEN_SACK_PERBLOCK)) && 2676 !((opsize - TCPOLEN_SACK_BASE) % TCPOLEN_SACK_PERBLOCK) && 2677 opt_rx->sack_ok) { 2678 TCP_SKB_CB(skb)->sacked = (ptr - 2) - (unsigned char *)th; 2679 } 2680 }; 2681 ptr+=opsize-2; 2682 length-=opsize; 2683 }; 2684 } 2685} 2686 2687/* Fast parse options. This hopes to only see timestamps. 2688 * If it is wrong it falls back on tcp_parse_options(). 2689 */ 2690static int tcp_fast_parse_options(struct sk_buff *skb, struct tcphdr *th, 2691 struct tcp_sock *tp) 2692{ 2693 if (th->doff == sizeof(struct tcphdr)>>2) { 2694 tp->rx_opt.saw_tstamp = 0; 2695 return 0; 2696 } else if (tp->rx_opt.tstamp_ok && 2697 th->doff == (sizeof(struct tcphdr)>>2)+(TCPOLEN_TSTAMP_ALIGNED>>2)) { 2698 __be32 *ptr = (__be32 *)(th + 1); 2699 if (*ptr == htonl((TCPOPT_NOP << 24) | (TCPOPT_NOP << 16) 2700 | (TCPOPT_TIMESTAMP << 8) | TCPOLEN_TIMESTAMP)) { 2701 tp->rx_opt.saw_tstamp = 1; 2702 ++ptr; 2703 tp->rx_opt.rcv_tsval = ntohl(*ptr); 2704 ++ptr; 2705 tp->rx_opt.rcv_tsecr = ntohl(*ptr); 2706 return 1; 2707 } 2708 } 2709 tcp_parse_options(skb, &tp->rx_opt, 1); 2710 return 1; 2711} 2712 2713static inline void tcp_store_ts_recent(struct tcp_sock *tp) 2714{ 2715 tp->rx_opt.ts_recent = tp->rx_opt.rcv_tsval; 2716 tp->rx_opt.ts_recent_stamp = xtime.tv_sec; 2717} 2718 2719static inline void tcp_replace_ts_recent(struct tcp_sock *tp, u32 seq) 2720{ 2721 if (tp->rx_opt.saw_tstamp && !after(seq, tp->rcv_wup)) { 2722 /* PAWS bug workaround wrt. ACK frames, the PAWS discard 2723 * extra check below makes sure this can only happen 2724 * for pure ACK frames. -DaveM 2725 * 2726 * Not only, also it occurs for expired timestamps. 2727 */ 2728 2729 if((s32)(tp->rx_opt.rcv_tsval - tp->rx_opt.ts_recent) >= 0 || 2730 xtime.tv_sec >= tp->rx_opt.ts_recent_stamp + TCP_PAWS_24DAYS) 2731 tcp_store_ts_recent(tp); 2732 } 2733} 2734 2735/* Sorry, PAWS as specified is broken wrt. pure-ACKs -DaveM 2736 * 2737 * It is not fatal. If this ACK does _not_ change critical state (seqs, window) 2738 * it can pass through stack. So, the following predicate verifies that 2739 * this segment is not used for anything but congestion avoidance or 2740 * fast retransmit. Moreover, we even are able to eliminate most of such 2741 * second order effects, if we apply some small "replay" window (~RTO) 2742 * to timestamp space. 2743 * 2744 * All these measures still do not guarantee that we reject wrapped ACKs 2745 * on networks with high bandwidth, when sequence space is recycled fastly, 2746 * but it guarantees that such events will be very rare and do not affect 2747 * connection seriously. This doesn't look nice, but alas, PAWS is really 2748 * buggy extension. 2749 * 2750 * [ Later note. Even worse! It is buggy for segments _with_ data. RFC 2751 * states that events when retransmit arrives after original data are rare. 2752 * It is a blatant lie. VJ forgot about fast retransmit! 8)8) It is 2753 * the biggest problem on large power networks even with minor reordering. 2754 * OK, let's give it small replay window. If peer clock is even 1hz, it is safe 2755 * up to bandwidth of 18Gigabit/sec. 8) ] 2756 */ 2757 2758static int tcp_disordered_ack(const struct sock *sk, const struct sk_buff *skb) 2759{ 2760 struct tcp_sock *tp = tcp_sk(sk); 2761 struct tcphdr *th = skb->h.th; 2762 u32 seq = TCP_SKB_CB(skb)->seq; 2763 u32 ack = TCP_SKB_CB(skb)->ack_seq; 2764 2765 return (/* 1. Pure ACK with correct sequence number. */ 2766 (th->ack && seq == TCP_SKB_CB(skb)->end_seq && seq == tp->rcv_nxt) && 2767 2768 /* 2. ... and duplicate ACK. */ 2769 ack == tp->snd_una && 2770 2771 /* 3. ... and does not update window. */ 2772 !tcp_may_update_window(tp, ack, seq, ntohs(th->window) << tp->rx_opt.snd_wscale) && 2773 2774 /* 4. ... and sits in replay window. */ 2775 (s32)(tp->rx_opt.ts_recent - tp->rx_opt.rcv_tsval) <= (inet_csk(sk)->icsk_rto * 1024) / HZ); 2776} 2777 2778static inline int tcp_paws_discard(const struct sock *sk, const struct sk_buff *skb) 2779{ 2780 const struct tcp_sock *tp = tcp_sk(sk); 2781 return ((s32)(tp->rx_opt.ts_recent - tp->rx_opt.rcv_tsval) > TCP_PAWS_WINDOW && 2782 xtime.tv_sec < tp->rx_opt.ts_recent_stamp + TCP_PAWS_24DAYS && 2783 !tcp_disordered_ack(sk, skb)); 2784} 2785 2786/* Check segment sequence number for validity. 2787 * 2788 * Segment controls are considered valid, if the segment 2789 * fits to the window after truncation to the window. Acceptability 2790 * of data (and SYN, FIN, of course) is checked separately. 2791 * See tcp_data_queue(), for example. 2792 * 2793 * Also, controls (RST is main one) are accepted using RCV.WUP instead 2794 * of RCV.NXT. Peer still did not advance his SND.UNA when we 2795 * delayed ACK, so that hisSND.UNA<=ourRCV.WUP. 2796 * (borrowed from freebsd) 2797 */ 2798 2799static inline int tcp_sequence(struct tcp_sock *tp, u32 seq, u32 end_seq) 2800{ 2801 return !before(end_seq, tp->rcv_wup) && 2802 !after(seq, tp->rcv_nxt + tcp_receive_window(tp)); 2803} 2804 2805/* When we get a reset we do this. */ 2806static void tcp_reset(struct sock *sk) 2807{ 2808 /* We want the right error as BSD sees it (and indeed as we do). */ 2809 switch (sk->sk_state) { 2810 case TCP_SYN_SENT: 2811 sk->sk_err = ECONNREFUSED; 2812 break; 2813 case TCP_CLOSE_WAIT: 2814 sk->sk_err = EPIPE; 2815 break; 2816 case TCP_CLOSE: 2817 return; 2818 default: 2819 sk->sk_err = ECONNRESET; 2820 } 2821 2822 if (!sock_flag(sk, SOCK_DEAD)) 2823 sk->sk_error_report(sk); 2824 2825 tcp_done(sk); 2826} 2827 2828/* 2829 * Process the FIN bit. This now behaves as it is supposed to work 2830 * and the FIN takes effect when it is validly part of sequence 2831 * space. Not before when we get holes. 2832 * 2833 * If we are ESTABLISHED, a received fin moves us to CLOSE-WAIT 2834 * (and thence onto LAST-ACK and finally, CLOSE, we never enter 2835 * TIME-WAIT) 2836 * 2837 * If we are in FINWAIT-1, a received FIN indicates simultaneous 2838 * close and we go into CLOSING (and later onto TIME-WAIT) 2839 * 2840 * If we are in FINWAIT-2, a received FIN moves us to TIME-WAIT. 2841 */ 2842static void tcp_fin(struct sk_buff *skb, struct sock *sk, struct tcphdr *th) 2843{ 2844 struct tcp_sock *tp = tcp_sk(sk); 2845 2846 inet_csk_schedule_ack(sk); 2847 2848 sk->sk_shutdown |= RCV_SHUTDOWN; 2849 sock_set_flag(sk, SOCK_DONE); 2850 2851 switch (sk->sk_state) { 2852 case TCP_SYN_RECV: 2853 case TCP_ESTABLISHED: 2854 /* Move to CLOSE_WAIT */ 2855 tcp_set_state(sk, TCP_CLOSE_WAIT); 2856 inet_csk(sk)->icsk_ack.pingpong = 1; 2857 break; 2858 2859 case TCP_CLOSE_WAIT: 2860 case TCP_CLOSING: 2861 /* Received a retransmission of the FIN, do 2862 * nothing. 2863 */ 2864 break; 2865 case TCP_LAST_ACK: 2866 /* RFC793: Remain in the LAST-ACK state. */ 2867 break; 2868 2869 case TCP_FIN_WAIT1: 2870 /* This case occurs when a simultaneous close 2871 * happens, we must ack the received FIN and 2872 * enter the CLOSING state. 2873 */ 2874 tcp_send_ack(sk); 2875 tcp_set_state(sk, TCP_CLOSING); 2876 break; 2877 case TCP_FIN_WAIT2: 2878 /* Received a FIN -- send ACK and enter TIME_WAIT. */ 2879 tcp_send_ack(sk); 2880 tcp_time_wait(sk, TCP_TIME_WAIT, 0); 2881 break; 2882 default: 2883 /* Only TCP_LISTEN and TCP_CLOSE are left, in these 2884 * cases we should never reach this piece of code. 2885 */ 2886 printk(KERN_ERR "%s: Impossible, sk->sk_state=%d\n", 2887 __FUNCTION__, sk->sk_state); 2888 break; 2889 }; 2890 2891 /* It _is_ possible, that we have something out-of-order _after_ FIN. 2892 * Probably, we should reset in this case. For now drop them. 2893 */ 2894 __skb_queue_purge(&tp->out_of_order_queue); 2895 if (tp->rx_opt.sack_ok) 2896 tcp_sack_reset(&tp->rx_opt); 2897 sk_stream_mem_reclaim(sk); 2898 2899 if (!sock_flag(sk, SOCK_DEAD)) { 2900 sk->sk_state_change(sk); 2901 2902 /* Do not send POLL_HUP for half duplex close. */ 2903 if (sk->sk_shutdown == SHUTDOWN_MASK || 2904 sk->sk_state == TCP_CLOSE) 2905 sk_wake_async(sk, 1, POLL_HUP); 2906 else 2907 sk_wake_async(sk, 1, POLL_IN); 2908 } 2909} 2910 2911static inline int tcp_sack_extend(struct tcp_sack_block *sp, u32 seq, u32 end_seq) 2912{ 2913 if (!after(seq, sp->end_seq) && !after(sp->start_seq, end_seq)) { 2914 if (before(seq, sp->start_seq)) 2915 sp->start_seq = seq; 2916 if (after(end_seq, sp->end_seq)) 2917 sp->end_seq = end_seq; 2918 return 1; 2919 } 2920 return 0; 2921} 2922 2923static void tcp_dsack_set(struct tcp_sock *tp, u32 seq, u32 end_seq) 2924{ 2925 if (tp->rx_opt.sack_ok && sysctl_tcp_dsack) { 2926 if (before(seq, tp->rcv_nxt)) 2927 NET_INC_STATS_BH(LINUX_MIB_TCPDSACKOLDSENT); 2928 else 2929 NET_INC_STATS_BH(LINUX_MIB_TCPDSACKOFOSENT); 2930 2931 tp->rx_opt.dsack = 1; 2932 tp->duplicate_sack[0].start_seq = seq; 2933 tp->duplicate_sack[0].end_seq = end_seq; 2934 tp->rx_opt.eff_sacks = min(tp->rx_opt.num_sacks + 1, 4 - tp->rx_opt.tstamp_ok); 2935 } 2936} 2937 2938static void tcp_dsack_extend(struct tcp_sock *tp, u32 seq, u32 end_seq) 2939{ 2940 if (!tp->rx_opt.dsack) 2941 tcp_dsack_set(tp, seq, end_seq); 2942 else 2943 tcp_sack_extend(tp->duplicate_sack, seq, end_seq); 2944} 2945 2946static void tcp_send_dupack(struct sock *sk, struct sk_buff *skb) 2947{ 2948 struct tcp_sock *tp = tcp_sk(sk); 2949 2950 if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 2951 before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 2952 NET_INC_STATS_BH(LINUX_MIB_DELAYEDACKLOST); 2953 tcp_enter_quickack_mode(sk); 2954 2955 if (tp->rx_opt.sack_ok && sysctl_tcp_dsack) { 2956 u32 end_seq = TCP_SKB_CB(skb)->end_seq; 2957 2958 if (after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) 2959 end_seq = tp->rcv_nxt; 2960 tcp_dsack_set(tp, TCP_SKB_CB(skb)->seq, end_seq); 2961 } 2962 } 2963 2964 tcp_send_ack(sk); 2965} 2966 2967/* These routines update the SACK block as out-of-order packets arrive or 2968 * in-order packets close up the sequence space. 2969 */ 2970static void tcp_sack_maybe_coalesce(struct tcp_sock *tp) 2971{ 2972 int this_sack; 2973 struct tcp_sack_block *sp = &tp->selective_acks[0]; 2974 struct tcp_sack_block *swalk = sp+1; 2975 2976 /* See if the recent change to the first SACK eats into 2977 * or hits the sequence space of other SACK blocks, if so coalesce. 2978 */ 2979 for (this_sack = 1; this_sack < tp->rx_opt.num_sacks; ) { 2980 if (tcp_sack_extend(sp, swalk->start_seq, swalk->end_seq)) { 2981 int i; 2982 2983 /* Zap SWALK, by moving every further SACK up by one slot. 2984 * Decrease num_sacks. 2985 */ 2986 tp->rx_opt.num_sacks--; 2987 tp->rx_opt.eff_sacks = min(tp->rx_opt.num_sacks + tp->rx_opt.dsack, 4 - tp->rx_opt.tstamp_ok); 2988 for(i=this_sack; i < tp->rx_opt.num_sacks; i++) 2989 sp[i] = sp[i+1]; 2990 continue; 2991 } 2992 this_sack++, swalk++; 2993 } 2994} 2995 2996static inline void tcp_sack_swap(struct tcp_sack_block *sack1, struct tcp_sack_block *sack2) 2997{ 2998 __u32 tmp; 2999 3000 tmp = sack1->start_seq; 3001 sack1->start_seq = sack2->start_seq; 3002 sack2->start_seq = tmp; 3003 3004 tmp = sack1->end_seq; 3005 sack1->end_seq = sack2->end_seq; 3006 sack2->end_seq = tmp; 3007} 3008 3009static void tcp_sack_new_ofo_skb(struct sock *sk, u32 seq, u32 end_seq) 3010{ 3011 struct tcp_sock *tp = tcp_sk(sk); 3012 struct tcp_sack_block *sp = &tp->selective_acks[0]; 3013 int cur_sacks = tp->rx_opt.num_sacks; 3014 int this_sack; 3015 3016 if (!cur_sacks) 3017 goto new_sack; 3018 3019 for (this_sack=0; this_sack<cur_sacks; this_sack++, sp++) { 3020 if (tcp_sack_extend(sp, seq, end_seq)) { 3021 /* Rotate this_sack to the first one. */ 3022 for (; this_sack>0; this_sack--, sp--) 3023 tcp_sack_swap(sp, sp-1); 3024 if (cur_sacks > 1) 3025 tcp_sack_maybe_coalesce(tp); 3026 return; 3027 } 3028 } 3029 3030 /* Could not find an adjacent existing SACK, build a new one, 3031 * put it at the front, and shift everyone else down. We 3032 * always know there is at least one SACK present already here. 3033 * 3034 * If the sack array is full, forget about the last one. 3035 */ 3036 if (this_sack >= 4) { 3037 this_sack--; 3038 tp->rx_opt.num_sacks--; 3039 sp--; 3040 } 3041 for(; this_sack > 0; this_sack--, sp--) 3042 *sp = *(sp-1); 3043 3044new_sack: 3045 /* Build the new head SACK, and we're done. */ 3046 sp->start_seq = seq; 3047 sp->end_seq = end_seq; 3048 tp->rx_opt.num_sacks++; 3049 tp->rx_opt.eff_sacks = min(tp->rx_opt.num_sacks + tp->rx_opt.dsack, 4 - tp->rx_opt.tstamp_ok); 3050} 3051 3052/* RCV.NXT advances, some SACKs should be eaten. */ 3053 3054static void tcp_sack_remove(struct tcp_sock *tp) 3055{ 3056 struct tcp_sack_block *sp = &tp->selective_acks[0]; 3057 int num_sacks = tp->rx_opt.num_sacks; 3058 int this_sack; 3059 3060 /* Empty ofo queue, hence, all the SACKs are eaten. Clear. */ 3061 if (skb_queue_empty(&tp->out_of_order_queue)) { 3062 tp->rx_opt.num_sacks = 0; 3063 tp->rx_opt.eff_sacks = tp->rx_opt.dsack; 3064 return; 3065 } 3066 3067 for(this_sack = 0; this_sack < num_sacks; ) { 3068 /* Check if the start of the sack is covered by RCV.NXT. */ 3069 if (!before(tp->rcv_nxt, sp->start_seq)) { 3070 int i; 3071 3072 /* RCV.NXT must cover all the block! */ 3073 BUG_TRAP(!before(tp->rcv_nxt, sp->end_seq)); 3074 3075 /* Zap this SACK, by moving forward any other SACKS. */ 3076 for (i=this_sack+1; i < num_sacks; i++) 3077 tp->selective_acks[i-1] = tp->selective_acks[i]; 3078 num_sacks--; 3079 continue; 3080 } 3081 this_sack++; 3082 sp++; 3083 } 3084 if (num_sacks != tp->rx_opt.num_sacks) { 3085 tp->rx_opt.num_sacks = num_sacks; 3086 tp->rx_opt.eff_sacks = min(tp->rx_opt.num_sacks + tp->rx_opt.dsack, 4 - tp->rx_opt.tstamp_ok); 3087 } 3088} 3089 3090/* This one checks to see if we can put data from the 3091 * out_of_order queue into the receive_queue. 3092 */ 3093static void tcp_ofo_queue(struct sock *sk) 3094{ 3095 struct tcp_sock *tp = tcp_sk(sk); 3096 __u32 dsack_high = tp->rcv_nxt; 3097 struct sk_buff *skb; 3098 3099 while ((skb = skb_peek(&tp->out_of_order_queue)) != NULL) { 3100 if (after(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) 3101 break; 3102 3103 if (before(TCP_SKB_CB(skb)->seq, dsack_high)) { 3104 __u32 dsack = dsack_high; 3105 if (before(TCP_SKB_CB(skb)->end_seq, dsack_high)) 3106 dsack_high = TCP_SKB_CB(skb)->end_seq; 3107 tcp_dsack_extend(tp, TCP_SKB_CB(skb)->seq, dsack); 3108 } 3109 3110 if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) { 3111 SOCK_DEBUG(sk, "ofo packet was already received \n"); 3112 __skb_unlink(skb, &tp->out_of_order_queue); 3113 __kfree_skb(skb); 3114 continue; 3115 } 3116 SOCK_DEBUG(sk, "ofo requeuing : rcv_next %X seq %X - %X\n", 3117 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, 3118 TCP_SKB_CB(skb)->end_seq); 3119 3120 __skb_unlink(skb, &tp->out_of_order_queue); 3121 __skb_queue_tail(&sk->sk_receive_queue, skb); 3122 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 3123 if(skb->h.th->fin) 3124 tcp_fin(skb, sk, skb->h.th); 3125 } 3126} 3127 3128static int tcp_prune_queue(struct sock *sk); 3129 3130static void tcp_data_queue(struct sock *sk, struct sk_buff *skb) 3131{ 3132 struct tcphdr *th = skb->h.th; 3133 struct tcp_sock *tp = tcp_sk(sk); 3134 int eaten = -1; 3135 3136 if (TCP_SKB_CB(skb)->seq == TCP_SKB_CB(skb)->end_seq) 3137 goto drop; 3138 3139 __skb_pull(skb, th->doff*4); 3140 3141 TCP_ECN_accept_cwr(tp, skb); 3142 3143 if (tp->rx_opt.dsack) { 3144 tp->rx_opt.dsack = 0; 3145 tp->rx_opt.eff_sacks = min_t(unsigned int, tp->rx_opt.num_sacks, 3146 4 - tp->rx_opt.tstamp_ok); 3147 } 3148 3149 /* Queue data for delivery to the user. 3150 * Packets in sequence go to the receive queue. 3151 * Out of sequence packets to the out_of_order_queue. 3152 */ 3153 if (TCP_SKB_CB(skb)->seq == tp->rcv_nxt) { 3154 if (tcp_receive_window(tp) == 0) 3155 goto out_of_window; 3156 3157 /* Ok. In sequence. In window. */ 3158 if (tp->ucopy.task == current && 3159 tp->copied_seq == tp->rcv_nxt && tp->ucopy.len && 3160 sock_owned_by_user(sk) && !tp->urg_data) { 3161 int chunk = min_t(unsigned int, skb->len, 3162 tp->ucopy.len); 3163 3164 __set_current_state(TASK_RUNNING); 3165 3166 local_bh_enable(); 3167 if (!skb_copy_datagram_iovec(skb, 0, tp->ucopy.iov, chunk)) { 3168 tp->ucopy.len -= chunk; 3169 tp->copied_seq += chunk; 3170 eaten = (chunk == skb->len && !th->fin); 3171 tcp_rcv_space_adjust(sk); 3172 } 3173 local_bh_disable(); 3174 } 3175 3176 if (eaten <= 0) { 3177queue_and_out: 3178 if (eaten < 0 && 3179 (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf || 3180 !sk_stream_rmem_schedule(sk, skb))) { 3181 if (tcp_prune_queue(sk) < 0 || 3182 !sk_stream_rmem_schedule(sk, skb)) 3183 goto drop; 3184 } 3185 sk_stream_set_owner_r(skb, sk); 3186 __skb_queue_tail(&sk->sk_receive_queue, skb); 3187 } 3188 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 3189 if(skb->len) 3190 tcp_event_data_recv(sk, tp, skb); 3191 if(th->fin) 3192 tcp_fin(skb, sk, th); 3193 3194 if (!skb_queue_empty(&tp->out_of_order_queue)) { 3195 tcp_ofo_queue(sk); 3196 3197 /* RFC2581. 4.2. SHOULD send immediate ACK, when 3198 * gap in queue is filled. 3199 */ 3200 if (skb_queue_empty(&tp->out_of_order_queue)) 3201 inet_csk(sk)->icsk_ack.pingpong = 0; 3202 } 3203 3204 if (tp->rx_opt.num_sacks) 3205 tcp_sack_remove(tp); 3206 3207 tcp_fast_path_check(sk, tp); 3208 3209 if (eaten > 0) 3210 __kfree_skb(skb); 3211 else if (!sock_flag(sk, SOCK_DEAD)) 3212 sk->sk_data_ready(sk, 0); 3213 return; 3214 } 3215 3216 if (!after(TCP_SKB_CB(skb)->end_seq, tp->rcv_nxt)) { 3217 /* A retransmit, 2nd most common case. Force an immediate ack. */ 3218 NET_INC_STATS_BH(LINUX_MIB_DELAYEDACKLOST); 3219 tcp_dsack_set(tp, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq); 3220 3221out_of_window: 3222 tcp_enter_quickack_mode(sk); 3223 inet_csk_schedule_ack(sk); 3224drop: 3225 __kfree_skb(skb); 3226 return; 3227 } 3228 3229 /* Out of window. F.e. zero window probe. */ 3230 if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt + tcp_receive_window(tp))) 3231 goto out_of_window; 3232 3233 tcp_enter_quickack_mode(sk); 3234 3235 if (before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 3236 /* Partial packet, seq < rcv_next < end_seq */ 3237 SOCK_DEBUG(sk, "partial packet: rcv_next %X seq %X - %X\n", 3238 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, 3239 TCP_SKB_CB(skb)->end_seq); 3240 3241 tcp_dsack_set(tp, TCP_SKB_CB(skb)->seq, tp->rcv_nxt); 3242 3243 /* If window is closed, drop tail of packet. But after 3244 * remembering D-SACK for its head made in previous line. 3245 */ 3246 if (!tcp_receive_window(tp)) 3247 goto out_of_window; 3248 goto queue_and_out; 3249 } 3250 3251 TCP_ECN_check_ce(tp, skb); 3252 3253 if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf || 3254 !sk_stream_rmem_schedule(sk, skb)) { 3255 if (tcp_prune_queue(sk) < 0 || 3256 !sk_stream_rmem_schedule(sk, skb)) 3257 goto drop; 3258 } 3259 3260 /* Disable header prediction. */ 3261 tp->pred_flags = 0; 3262 inet_csk_schedule_ack(sk); 3263 3264 SOCK_DEBUG(sk, "out of order segment: rcv_next %X seq %X - %X\n", 3265 tp->rcv_nxt, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq); 3266 3267 sk_stream_set_owner_r(skb, sk); 3268 3269 if (!skb_peek(&tp->out_of_order_queue)) { 3270 /* Initial out of order segment, build 1 SACK. */ 3271 if (tp->rx_opt.sack_ok) { 3272 tp->rx_opt.num_sacks = 1; 3273 tp->rx_opt.dsack = 0; 3274 tp->rx_opt.eff_sacks = 1; 3275 tp->selective_acks[0].start_seq = TCP_SKB_CB(skb)->seq; 3276 tp->selective_acks[0].end_seq = 3277 TCP_SKB_CB(skb)->end_seq; 3278 } 3279 __skb_queue_head(&tp->out_of_order_queue,skb); 3280 } else { 3281 struct sk_buff *skb1 = tp->out_of_order_queue.prev; 3282 u32 seq = TCP_SKB_CB(skb)->seq; 3283 u32 end_seq = TCP_SKB_CB(skb)->end_seq; 3284 3285 if (seq == TCP_SKB_CB(skb1)->end_seq) { 3286 __skb_append(skb1, skb, &tp->out_of_order_queue); 3287 3288 if (!tp->rx_opt.num_sacks || 3289 tp->selective_acks[0].end_seq != seq) 3290 goto add_sack; 3291 3292 /* Common case: data arrive in order after hole. */ 3293 tp->selective_acks[0].end_seq = end_seq; 3294 return; 3295 } 3296 3297 /* Find place to insert this segment. */ 3298 do { 3299 if (!after(TCP_SKB_CB(skb1)->seq, seq)) 3300 break; 3301 } while ((skb1 = skb1->prev) != 3302 (struct sk_buff*)&tp->out_of_order_queue); 3303 3304 /* Do skb overlap to previous one? */ 3305 if (skb1 != (struct sk_buff*)&tp->out_of_order_queue && 3306 before(seq, TCP_SKB_CB(skb1)->end_seq)) { 3307 if (!after(end_seq, TCP_SKB_CB(skb1)->end_seq)) { 3308 /* All the bits are present. Drop. */ 3309 __kfree_skb(skb); 3310 tcp_dsack_set(tp, seq, end_seq); 3311 goto add_sack; 3312 } 3313 if (after(seq, TCP_SKB_CB(skb1)->seq)) { 3314 /* Partial overlap. */ 3315 tcp_dsack_set(tp, seq, TCP_SKB_CB(skb1)->end_seq); 3316 } else { 3317 skb1 = skb1->prev; 3318 } 3319 } 3320 __skb_insert(skb, skb1, skb1->next, &tp->out_of_order_queue); 3321 3322 /* And clean segments covered by new one as whole. */ 3323 while ((skb1 = skb->next) != 3324 (struct sk_buff*)&tp->out_of_order_queue && 3325 after(end_seq, TCP_SKB_CB(skb1)->seq)) { 3326 if (before(end_seq, TCP_SKB_CB(skb1)->end_seq)) { 3327 tcp_dsack_extend(tp, TCP_SKB_CB(skb1)->seq, end_seq); 3328 break; 3329 } 3330 __skb_unlink(skb1, &tp->out_of_order_queue); 3331 tcp_dsack_extend(tp, TCP_SKB_CB(skb1)->seq, TCP_SKB_CB(skb1)->end_seq); 3332 __kfree_skb(skb1); 3333 } 3334 3335add_sack: 3336 if (tp->rx_opt.sack_ok) 3337 tcp_sack_new_ofo_skb(sk, seq, end_seq); 3338 } 3339} 3340 3341/* Collapse contiguous sequence of skbs head..tail with 3342 * sequence numbers start..end. 3343 * Segments with FIN/SYN are not collapsed (only because this 3344 * simplifies code) 3345 */ 3346static void 3347tcp_collapse(struct sock *sk, struct sk_buff_head *list, 3348 struct sk_buff *head, struct sk_buff *tail, 3349 u32 start, u32 end) 3350{ 3351 struct sk_buff *skb; 3352 3353 /* First, check that queue is collapsible and find 3354 * the point where collapsing can be useful. */ 3355 for (skb = head; skb != tail; ) { 3356 /* No new bits? It is possible on ofo queue. */ 3357 if (!before(start, TCP_SKB_CB(skb)->end_seq)) { 3358 struct sk_buff *next = skb->next; 3359 __skb_unlink(skb, list); 3360 __kfree_skb(skb); 3361 NET_INC_STATS_BH(LINUX_MIB_TCPRCVCOLLAPSED); 3362 skb = next; 3363 continue; 3364 } 3365 3366 /* The first skb to collapse is: 3367 * - not SYN/FIN and 3368 * - bloated or contains data before "start" or 3369 * overlaps to the next one. 3370 */ 3371 if (!skb->h.th->syn && !skb->h.th->fin && 3372 (tcp_win_from_space(skb->truesize) > skb->len || 3373 before(TCP_SKB_CB(skb)->seq, start) || 3374 (skb->next != tail && 3375 TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb->next)->seq))) 3376 break; 3377 3378 /* Decided to skip this, advance start seq. */ 3379 start = TCP_SKB_CB(skb)->end_seq; 3380 skb = skb->next; 3381 } 3382 if (skb == tail || skb->h.th->syn || skb->h.th->fin) 3383 return; 3384 3385 while (before(start, end)) { 3386 struct sk_buff *nskb; 3387 int header = skb_headroom(skb); 3388 int copy = SKB_MAX_ORDER(header, 0); 3389 3390 /* Too big header? This can happen with IPv6. */ 3391 if (copy < 0) 3392 return; 3393 if (end-start < copy) 3394 copy = end-start; 3395 nskb = alloc_skb(copy+header, GFP_ATOMIC); 3396 if (!nskb) 3397 return; 3398 skb_reserve(nskb, header); 3399 memcpy(nskb->head, skb->head, header); 3400 nskb->nh.raw = nskb->head + (skb->nh.raw-skb->head); 3401 nskb->h.raw = nskb->head + (skb->h.raw-skb->head); 3402 nskb->mac.raw = nskb->head + (skb->mac.raw-skb->head); 3403 memcpy(nskb->cb, skb->cb, sizeof(skb->cb)); 3404 TCP_SKB_CB(nskb)->seq = TCP_SKB_CB(nskb)->end_seq = start; 3405 __skb_insert(nskb, skb->prev, skb, list); 3406 sk_stream_set_owner_r(nskb, sk); 3407 3408 /* Copy data, releasing collapsed skbs. */ 3409 while (copy > 0) { 3410 int offset = start - TCP_SKB_CB(skb)->seq; 3411 int size = TCP_SKB_CB(skb)->end_seq - start; 3412 3413 BUG_ON(offset < 0); 3414 if (size > 0) { 3415 size = min(copy, size); 3416 if (skb_copy_bits(skb, offset, skb_put(nskb, size), size)) 3417 BUG(); 3418 TCP_SKB_CB(nskb)->end_seq += size; 3419 copy -= size; 3420 start += size; 3421 } 3422 if (!before(start, TCP_SKB_CB(skb)->end_seq)) { 3423 struct sk_buff *next = skb->next; 3424 __skb_unlink(skb, list); 3425 __kfree_skb(skb); 3426 NET_INC_STATS_BH(LINUX_MIB_TCPRCVCOLLAPSED); 3427 skb = next; 3428 if (skb == tail || skb->h.th->syn || skb->h.th->fin) 3429 return; 3430 } 3431 } 3432 } 3433} 3434 3435/* Collapse ofo queue. Algorithm: select contiguous sequence of skbs 3436 * and tcp_collapse() them until all the queue is collapsed. 3437 */ 3438static void tcp_collapse_ofo_queue(struct sock *sk) 3439{ 3440 struct tcp_sock *tp = tcp_sk(sk); 3441 struct sk_buff *skb = skb_peek(&tp->out_of_order_queue); 3442 struct sk_buff *head; 3443 u32 start, end; 3444 3445 if (skb == NULL) 3446 return; 3447 3448 start = TCP_SKB_CB(skb)->seq; 3449 end = TCP_SKB_CB(skb)->end_seq; 3450 head = skb; 3451 3452 for (;;) { 3453 skb = skb->next; 3454 3455 /* Segment is terminated when we see gap or when 3456 * we are at the end of all the queue. */ 3457 if (skb == (struct sk_buff *)&tp->out_of_order_queue || 3458 after(TCP_SKB_CB(skb)->seq, end) || 3459 before(TCP_SKB_CB(skb)->end_seq, start)) { 3460 tcp_collapse(sk, &tp->out_of_order_queue, 3461 head, skb, start, end); 3462 head = skb; 3463 if (skb == (struct sk_buff *)&tp->out_of_order_queue) 3464 break; 3465 /* Start new segment */ 3466 start = TCP_SKB_CB(skb)->seq; 3467 end = TCP_SKB_CB(skb)->end_seq; 3468 } else { 3469 if (before(TCP_SKB_CB(skb)->seq, start)) 3470 start = TCP_SKB_CB(skb)->seq; 3471 if (after(TCP_SKB_CB(skb)->end_seq, end)) 3472 end = TCP_SKB_CB(skb)->end_seq; 3473 } 3474 } 3475} 3476 3477/* Reduce allocated memory if we can, trying to get 3478 * the socket within its memory limits again. 3479 * 3480 * Return less than zero if we should start dropping frames 3481 * until the socket owning process reads some of the data 3482 * to stabilize the situation. 3483 */ 3484static int tcp_prune_queue(struct sock *sk) 3485{ 3486 struct tcp_sock *tp = tcp_sk(sk); 3487 3488 SOCK_DEBUG(sk, "prune_queue: c=%x\n", tp->copied_seq); 3489 3490 NET_INC_STATS_BH(LINUX_MIB_PRUNECALLED); 3491 3492 if (atomic_read(&sk->sk_rmem_alloc) >= sk->sk_rcvbuf) 3493 tcp_clamp_window(sk, tp); 3494 else if (tcp_memory_pressure) 3495 tp->rcv_ssthresh = min(tp->rcv_ssthresh, 4U * tp->advmss); 3496 3497 tcp_collapse_ofo_queue(sk); 3498 tcp_collapse(sk, &sk->sk_receive_queue, 3499 sk->sk_receive_queue.next, 3500 (struct sk_buff*)&sk->sk_receive_queue, 3501 tp->copied_seq, tp->rcv_nxt); 3502 sk_stream_mem_reclaim(sk); 3503 3504 if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf) 3505 return 0; 3506 3507 /* Collapsing did not help, destructive actions follow. 3508 * This must not ever occur. */ 3509 3510 /* First, purge the out_of_order queue. */ 3511 if (!skb_queue_empty(&tp->out_of_order_queue)) { 3512 NET_INC_STATS_BH(LINUX_MIB_OFOPRUNED); 3513 __skb_queue_purge(&tp->out_of_order_queue); 3514 3515 /* Reset SACK state. A conforming SACK implementation will 3516 * do the same at a timeout based retransmit. When a connection 3517 * is in a sad state like this, we care only about integrity 3518 * of the connection not performance. 3519 */ 3520 if (tp->rx_opt.sack_ok) 3521 tcp_sack_reset(&tp->rx_opt); 3522 sk_stream_mem_reclaim(sk); 3523 } 3524 3525 if (atomic_read(&sk->sk_rmem_alloc) <= sk->sk_rcvbuf) 3526 return 0; 3527 3528 /* If we are really being abused, tell the caller to silently 3529 * drop receive data on the floor. It will get retransmitted 3530 * and hopefully then we'll have sufficient space. 3531 */ 3532 NET_INC_STATS_BH(LINUX_MIB_RCVPRUNED); 3533 3534 /* Massive buffer overcommit. */ 3535 tp->pred_flags = 0; 3536 return -1; 3537} 3538 3539 3540/* RFC2861, slow part. Adjust cwnd, after it was not full during one rto. 3541 * As additional protections, we do not touch cwnd in retransmission phases, 3542 * and if application hit its sndbuf limit recently. 3543 */ 3544void tcp_cwnd_application_limited(struct sock *sk) 3545{ 3546 struct tcp_sock *tp = tcp_sk(sk); 3547 3548 if (inet_csk(sk)->icsk_ca_state == TCP_CA_Open && 3549 sk->sk_socket && !test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) { 3550 /* Limited by application or receiver window. */ 3551 u32 init_win = tcp_init_cwnd(tp, __sk_dst_get(sk)); 3552 u32 win_used = max(tp->snd_cwnd_used, init_win); 3553 if (win_used < tp->snd_cwnd) { 3554 tp->snd_ssthresh = tcp_current_ssthresh(sk); 3555 tp->snd_cwnd = (tp->snd_cwnd + win_used) >> 1; 3556 } 3557 tp->snd_cwnd_used = 0; 3558 } 3559 tp->snd_cwnd_stamp = tcp_time_stamp; 3560} 3561 3562static int tcp_should_expand_sndbuf(struct sock *sk, struct tcp_sock *tp) 3563{ 3564 /* If the user specified a specific send buffer setting, do 3565 * not modify it. 3566 */ 3567 if (sk->sk_userlocks & SOCK_SNDBUF_LOCK) 3568 return 0; 3569 3570 /* If we are under global TCP memory pressure, do not expand. */ 3571 if (tcp_memory_pressure) 3572 return 0; 3573 3574 /* If we are under soft global TCP memory pressure, do not expand. */ 3575 if (atomic_read(&tcp_memory_allocated) >= sysctl_tcp_mem[0]) 3576 return 0; 3577 3578 /* If we filled the congestion window, do not expand. */ 3579 if (tp->packets_out >= tp->snd_cwnd) 3580 return 0; 3581 3582 return 1; 3583} 3584 3585/* When incoming ACK allowed to free some skb from write_queue, 3586 * we remember this event in flag SOCK_QUEUE_SHRUNK and wake up socket 3587 * on the exit from tcp input handler. 3588 * 3589 * PROBLEM: sndbuf expansion does not work well with largesend. 3590 */ 3591static void tcp_new_space(struct sock *sk) 3592{ 3593 struct tcp_sock *tp = tcp_sk(sk); 3594 3595 if (tcp_should_expand_sndbuf(sk, tp)) { 3596 int sndmem = max_t(u32, tp->rx_opt.mss_clamp, tp->mss_cache) + 3597 MAX_TCP_HEADER + 16 + sizeof(struct sk_buff), 3598 demanded = max_t(unsigned int, tp->snd_cwnd, 3599 tp->reordering + 1); 3600 sndmem *= 2*demanded; 3601 if (sndmem > sk->sk_sndbuf) 3602 sk->sk_sndbuf = min(sndmem, sysctl_tcp_wmem[2]); 3603 tp->snd_cwnd_stamp = tcp_time_stamp; 3604 } 3605 3606 sk->sk_write_space(sk); 3607} 3608 3609static void tcp_check_space(struct sock *sk) 3610{ 3611 if (sock_flag(sk, SOCK_QUEUE_SHRUNK)) { 3612 sock_reset_flag(sk, SOCK_QUEUE_SHRUNK); 3613 if (sk->sk_socket && 3614 test_bit(SOCK_NOSPACE, &sk->sk_socket->flags)) 3615 tcp_new_space(sk); 3616 } 3617} 3618 3619static inline void tcp_data_snd_check(struct sock *sk, struct tcp_sock *tp) 3620{ 3621 tcp_push_pending_frames(sk, tp); 3622 tcp_check_space(sk); 3623} 3624 3625/* 3626 * Check if sending an ack is needed. 3627 */ 3628static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible) 3629{ 3630 struct tcp_sock *tp = tcp_sk(sk); 3631 3632 /* More than one full frame received... */ 3633 if (((tp->rcv_nxt - tp->rcv_wup) > inet_csk(sk)->icsk_ack.rcv_mss 3634 /* ... and right edge of window advances far enough. 3635 * (tcp_recvmsg() will send ACK otherwise). Or... 3636 */ 3637 && __tcp_select_window(sk) >= tp->rcv_wnd) || 3638 /* We ACK each frame or... */ 3639 tcp_in_quickack_mode(sk) || 3640 /* We have out of order data. */ 3641 (ofo_possible && 3642 skb_peek(&tp->out_of_order_queue))) { 3643 /* Then ack it now */ 3644 tcp_send_ack(sk); 3645 } else { 3646 /* Else, send delayed ack. */ 3647 tcp_send_delayed_ack(sk); 3648 } 3649} 3650 3651static inline void tcp_ack_snd_check(struct sock *sk) 3652{ 3653 if (!inet_csk_ack_scheduled(sk)) { 3654 /* We sent a data segment already. */ 3655 return; 3656 } 3657 __tcp_ack_snd_check(sk, 1); 3658} 3659 3660/* 3661 * This routine is only called when we have urgent data 3662 * signaled. Its the 'slow' part of tcp_urg. It could be 3663 * moved inline now as tcp_urg is only called from one 3664 * place. We handle URGent data wrong. We have to - as 3665 * BSD still doesn't use the correction from RFC961. 3666 * For 1003.1g we should support a new option TCP_STDURG to permit 3667 * either form (or just set the sysctl tcp_stdurg). 3668 */ 3669 3670static void tcp_check_urg(struct sock * sk, struct tcphdr * th) 3671{ 3672 struct tcp_sock *tp = tcp_sk(sk); 3673 u32 ptr = ntohs(th->urg_ptr); 3674 3675 if (ptr && !sysctl_tcp_stdurg) 3676 ptr--; 3677 ptr += ntohl(th->seq); 3678 3679 /* Ignore urgent data that we've already seen and read. */ 3680 if (after(tp->copied_seq, ptr)) 3681 return; 3682 3683 /* Do not replay urg ptr. 3684 * 3685 * NOTE: interesting situation not covered by specs. 3686 * Misbehaving sender may send urg ptr, pointing to segment, 3687 * which we already have in ofo queue. We are not able to fetch 3688 * such data and will stay in TCP_URG_NOTYET until will be eaten 3689 * by recvmsg(). Seems, we are not obliged to handle such wicked 3690 * situations. But it is worth to think about possibility of some 3691 * DoSes using some hypothetical application level deadlock. 3692 */ 3693 if (before(ptr, tp->rcv_nxt)) 3694 return; 3695 3696 /* Do we already have a newer (or duplicate) urgent pointer? */ 3697 if (tp->urg_data && !after(ptr, tp->urg_seq)) 3698 return; 3699 3700 /* Tell the world about our new urgent pointer. */ 3701 sk_send_sigurg(sk); 3702 3703 /* We may be adding urgent data when the last byte read was 3704 * urgent. To do this requires some care. We cannot just ignore 3705 * tp->copied_seq since we would read the last urgent byte again 3706 * as data, nor can we alter copied_seq until this data arrives 3707 * or we break the semantics of SIOCATMARK (and thus sockatmark()) 3708 * 3709 * NOTE. Double Dutch. Rendering to plain English: author of comment 3710 * above did something sort of send("A", MSG_OOB); send("B", MSG_OOB); 3711 * and expect that both A and B disappear from stream. This is _wrong_. 3712 * Though this happens in BSD with high probability, this is occasional. 3713 * Any application relying on this is buggy. Note also, that fix "works" 3714 * only in this artificial test. Insert some normal data between A and B and we will 3715 * decline of BSD again. Verdict: it is better to remove to trap 3716 * buggy users. 3717 */ 3718 if (tp->urg_seq == tp->copied_seq && tp->urg_data && 3719 !sock_flag(sk, SOCK_URGINLINE) && 3720 tp->copied_seq != tp->rcv_nxt) { 3721 struct sk_buff *skb = skb_peek(&sk->sk_receive_queue); 3722 tp->copied_seq++; 3723 if (skb && !before(tp->copied_seq, TCP_SKB_CB(skb)->end_seq)) { 3724 __skb_unlink(skb, &sk->sk_receive_queue); 3725 __kfree_skb(skb); 3726 } 3727 } 3728 3729 tp->urg_data = TCP_URG_NOTYET; 3730 tp->urg_seq = ptr; 3731 3732 /* Disable header prediction. */ 3733 tp->pred_flags = 0; 3734} 3735 3736/* This is the 'fast' part of urgent handling. */ 3737static void tcp_urg(struct sock *sk, struct sk_buff *skb, struct tcphdr *th) 3738{ 3739 struct tcp_sock *tp = tcp_sk(sk); 3740 3741 /* Check if we get a new urgent pointer - normally not. */ 3742 if (th->urg) 3743 tcp_check_urg(sk,th); 3744 3745 /* Do we wait for any urgent data? - normally not... */ 3746 if (tp->urg_data == TCP_URG_NOTYET) { 3747 u32 ptr = tp->urg_seq - ntohl(th->seq) + (th->doff * 4) - 3748 th->syn; 3749 3750 /* Is the urgent pointer pointing into this packet? */ 3751 if (ptr < skb->len) { 3752 u8 tmp; 3753 if (skb_copy_bits(skb, ptr, &tmp, 1)) 3754 BUG(); 3755 tp->urg_data = TCP_URG_VALID | tmp; 3756 if (!sock_flag(sk, SOCK_DEAD)) 3757 sk->sk_data_ready(sk, 0); 3758 } 3759 } 3760} 3761 3762static int tcp_copy_to_iovec(struct sock *sk, struct sk_buff *skb, int hlen) 3763{ 3764 struct tcp_sock *tp = tcp_sk(sk); 3765 int chunk = skb->len - hlen; 3766 int err; 3767 3768 local_bh_enable(); 3769 if (skb->ip_summed==CHECKSUM_UNNECESSARY) 3770 err = skb_copy_datagram_iovec(skb, hlen, tp->ucopy.iov, chunk); 3771 else 3772 err = skb_copy_and_csum_datagram_iovec(skb, hlen, 3773 tp->ucopy.iov); 3774 3775 if (!err) { 3776 tp->ucopy.len -= chunk; 3777 tp->copied_seq += chunk; 3778 tcp_rcv_space_adjust(sk); 3779 } 3780 3781 local_bh_disable(); 3782 return err; 3783} 3784 3785static int __tcp_checksum_complete_user(struct sock *sk, struct sk_buff *skb) 3786{ 3787 int result; 3788 3789 if (sock_owned_by_user(sk)) { 3790 local_bh_enable(); 3791 result = __tcp_checksum_complete(skb); 3792 local_bh_disable(); 3793 } else { 3794 result = __tcp_checksum_complete(skb); 3795 } 3796 return result; 3797} 3798 3799static inline int tcp_checksum_complete_user(struct sock *sk, struct sk_buff *skb) 3800{ 3801 return skb->ip_summed != CHECKSUM_UNNECESSARY && 3802 __tcp_checksum_complete_user(sk, skb); 3803} 3804 3805#ifdef CONFIG_NET_DMA 3806static int tcp_dma_try_early_copy(struct sock *sk, struct sk_buff *skb, int hlen) 3807{ 3808 struct tcp_sock *tp = tcp_sk(sk); 3809 int chunk = skb->len - hlen; 3810 int dma_cookie; 3811 int copied_early = 0; 3812 3813 if (tp->ucopy.wakeup) 3814 return 0; 3815 3816 if (!tp->ucopy.dma_chan && tp->ucopy.pinned_list) 3817 tp->ucopy.dma_chan = get_softnet_dma(); 3818 3819 if (tp->ucopy.dma_chan && skb->ip_summed == CHECKSUM_UNNECESSARY) { 3820 3821 dma_cookie = dma_skb_copy_datagram_iovec(tp->ucopy.dma_chan, 3822 skb, hlen, tp->ucopy.iov, chunk, tp->ucopy.pinned_list); 3823 3824 if (dma_cookie < 0) 3825 goto out; 3826 3827 tp->ucopy.dma_cookie = dma_cookie; 3828 copied_early = 1; 3829 3830 tp->ucopy.len -= chunk; 3831 tp->copied_seq += chunk; 3832 tcp_rcv_space_adjust(sk); 3833 3834 if ((tp->ucopy.len == 0) || 3835 (tcp_flag_word(skb->h.th) & TCP_FLAG_PSH) || 3836 (atomic_read(&sk->sk_rmem_alloc) > (sk->sk_rcvbuf >> 1))) { 3837 tp->ucopy.wakeup = 1; 3838 sk->sk_data_ready(sk, 0); 3839 } 3840 } else if (chunk > 0) { 3841 tp->ucopy.wakeup = 1; 3842 sk->sk_data_ready(sk, 0); 3843 } 3844out: 3845 return copied_early; 3846} 3847#endif /* CONFIG_NET_DMA */ 3848 3849/* 3850 * TCP receive function for the ESTABLISHED state. 3851 * 3852 * It is split into a fast path and a slow path. The fast path is 3853 * disabled when: 3854 * - A zero window was announced from us - zero window probing 3855 * is only handled properly in the slow path. 3856 * - Out of order segments arrived. 3857 * - Urgent data is expected. 3858 * - There is no buffer space left 3859 * - Unexpected TCP flags/window values/header lengths are received 3860 * (detected by checking the TCP header against pred_flags) 3861 * - Data is sent in both directions. Fast path only supports pure senders 3862 * or pure receivers (this means either the sequence number or the ack 3863 * value must stay constant) 3864 * - Unexpected TCP option. 3865 * 3866 * When these conditions are not satisfied it drops into a standard 3867 * receive procedure patterned after RFC793 to handle all cases. 3868 * The first three cases are guaranteed by proper pred_flags setting, 3869 * the rest is checked inline. Fast processing is turned on in 3870 * tcp_data_queue when everything is OK. 3871 */ 3872int tcp_rcv_established(struct sock *sk, struct sk_buff *skb, 3873 struct tcphdr *th, unsigned len) 3874{ 3875 struct tcp_sock *tp = tcp_sk(sk); 3876 3877 /* 3878 * Header prediction. 3879 * The code loosely follows the one in the famous 3880 * "30 instruction TCP receive" Van Jacobson mail. 3881 * 3882 * Van's trick is to deposit buffers into socket queue 3883 * on a device interrupt, to call tcp_recv function 3884 * on the receive process context and checksum and copy 3885 * the buffer to user space. smart... 3886 * 3887 * Our current scheme is not silly either but we take the 3888 * extra cost of the net_bh soft interrupt processing... 3889 * We do checksum and copy also but from device to kernel. 3890 */ 3891 3892 tp->rx_opt.saw_tstamp = 0; 3893 3894 /* pred_flags is 0xS?10 << 16 + snd_wnd 3895 * if header_prediction is to be made 3896 * 'S' will always be tp->tcp_header_len >> 2 3897 * '?' will be 0 for the fast path, otherwise pred_flags is 0 to 3898 * turn it off (when there are holes in the receive 3899 * space for instance) 3900 * PSH flag is ignored. 3901 */ 3902 3903 if ((tcp_flag_word(th) & TCP_HP_BITS) == tp->pred_flags && 3904 TCP_SKB_CB(skb)->seq == tp->rcv_nxt) { 3905 int tcp_header_len = tp->tcp_header_len; 3906 3907 /* Timestamp header prediction: tcp_header_len 3908 * is automatically equal to th->doff*4 due to pred_flags 3909 * match. 3910 */ 3911 3912 /* Check timestamp */ 3913 if (tcp_header_len == sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) { 3914 __be32 *ptr = (__be32 *)(th + 1); 3915 3916 /* No? Slow path! */ 3917 if (*ptr != htonl((TCPOPT_NOP << 24) | (TCPOPT_NOP << 16) 3918 | (TCPOPT_TIMESTAMP << 8) | TCPOLEN_TIMESTAMP)) 3919 goto slow_path; 3920 3921 tp->rx_opt.saw_tstamp = 1; 3922 ++ptr; 3923 tp->rx_opt.rcv_tsval = ntohl(*ptr); 3924 ++ptr; 3925 tp->rx_opt.rcv_tsecr = ntohl(*ptr); 3926 3927 /* If PAWS failed, check it more carefully in slow path */ 3928 if ((s32)(tp->rx_opt.rcv_tsval - tp->rx_opt.ts_recent) < 0) 3929 goto slow_path; 3930 3931 /* DO NOT update ts_recent here, if checksum fails 3932 * and timestamp was corrupted part, it will result 3933 * in a hung connection since we will drop all 3934 * future packets due to the PAWS test. 3935 */ 3936 } 3937 3938 if (len <= tcp_header_len) { 3939 /* Bulk data transfer: sender */ 3940 if (len == tcp_header_len) { 3941 /* Predicted packet is in window by definition. 3942 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 3943 * Hence, check seq<=rcv_wup reduces to: 3944 */ 3945 if (tcp_header_len == 3946 (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) && 3947 tp->rcv_nxt == tp->rcv_wup) 3948 tcp_store_ts_recent(tp); 3949 3950 /* We know that such packets are checksummed 3951 * on entry. 3952 */ 3953 tcp_ack(sk, skb, 0); 3954 __kfree_skb(skb); 3955 tcp_data_snd_check(sk, tp); 3956 return 0; 3957 } else { /* Header too small */ 3958 TCP_INC_STATS_BH(TCP_MIB_INERRS); 3959 goto discard; 3960 } 3961 } else { 3962 int eaten = 0; 3963 int copied_early = 0; 3964 3965 if (tp->copied_seq == tp->rcv_nxt && 3966 len - tcp_header_len <= tp->ucopy.len) { 3967#ifdef CONFIG_NET_DMA 3968 if (tcp_dma_try_early_copy(sk, skb, tcp_header_len)) { 3969 copied_early = 1; 3970 eaten = 1; 3971 } 3972#endif 3973 if (tp->ucopy.task == current && sock_owned_by_user(sk) && !copied_early) { 3974 __set_current_state(TASK_RUNNING); 3975 3976 if (!tcp_copy_to_iovec(sk, skb, tcp_header_len)) 3977 eaten = 1; 3978 } 3979 if (eaten) { 3980 /* Predicted packet is in window by definition. 3981 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 3982 * Hence, check seq<=rcv_wup reduces to: 3983 */ 3984 if (tcp_header_len == 3985 (sizeof(struct tcphdr) + 3986 TCPOLEN_TSTAMP_ALIGNED) && 3987 tp->rcv_nxt == tp->rcv_wup) 3988 tcp_store_ts_recent(tp); 3989 3990 tcp_rcv_rtt_measure_ts(sk, skb); 3991 3992 __skb_pull(skb, tcp_header_len); 3993 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 3994 NET_INC_STATS_BH(LINUX_MIB_TCPHPHITSTOUSER); 3995 } 3996 if (copied_early) 3997 tcp_cleanup_rbuf(sk, skb->len); 3998 } 3999 if (!eaten) { 4000 if (tcp_checksum_complete_user(sk, skb)) 4001 goto csum_error; 4002 4003 /* Predicted packet is in window by definition. 4004 * seq == rcv_nxt and rcv_wup <= rcv_nxt. 4005 * Hence, check seq<=rcv_wup reduces to: 4006 */ 4007 if (tcp_header_len == 4008 (sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED) && 4009 tp->rcv_nxt == tp->rcv_wup) 4010 tcp_store_ts_recent(tp); 4011 4012 tcp_rcv_rtt_measure_ts(sk, skb); 4013 4014 if ((int)skb->truesize > sk->sk_forward_alloc) 4015 goto step5; 4016 4017 NET_INC_STATS_BH(LINUX_MIB_TCPHPHITS); 4018 4019 /* Bulk data transfer: receiver */ 4020 __skb_pull(skb,tcp_header_len); 4021 __skb_queue_tail(&sk->sk_receive_queue, skb); 4022 sk_stream_set_owner_r(skb, sk); 4023 tp->rcv_nxt = TCP_SKB_CB(skb)->end_seq; 4024 } 4025 4026 tcp_event_data_recv(sk, tp, skb); 4027 4028 if (TCP_SKB_CB(skb)->ack_seq != tp->snd_una) { 4029 /* Well, only one small jumplet in fast path... */ 4030 tcp_ack(sk, skb, FLAG_DATA); 4031 tcp_data_snd_check(sk, tp); 4032 if (!inet_csk_ack_scheduled(sk)) 4033 goto no_ack; 4034 } 4035 4036 __tcp_ack_snd_check(sk, 0); 4037no_ack: 4038#ifdef CONFIG_NET_DMA 4039 if (copied_early) 4040 __skb_queue_tail(&sk->sk_async_wait_queue, skb); 4041 else 4042#endif 4043 if (eaten) 4044 __kfree_skb(skb); 4045 else 4046 sk->sk_data_ready(sk, 0); 4047 return 0; 4048 } 4049 } 4050 4051slow_path: 4052 if (len < (th->doff<<2) || tcp_checksum_complete_user(sk, skb)) 4053 goto csum_error; 4054 4055 /* 4056 * RFC1323: H1. Apply PAWS check first. 4057 */ 4058 if (tcp_fast_parse_options(skb, th, tp) && tp->rx_opt.saw_tstamp && 4059 tcp_paws_discard(sk, skb)) { 4060 if (!th->rst) { 4061 NET_INC_STATS_BH(LINUX_MIB_PAWSESTABREJECTED); 4062 tcp_send_dupack(sk, skb); 4063 goto discard; 4064 } 4065 /* Resets are accepted even if PAWS failed. 4066 4067 ts_recent update must be made after we are sure 4068 that the packet is in window. 4069 */ 4070 } 4071 4072 /* 4073 * Standard slow path. 4074 */ 4075 4076 if (!tcp_sequence(tp, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq)) { 4077 /* RFC793, page 37: "In all states except SYN-SENT, all reset 4078 * (RST) segments are validated by checking their SEQ-fields." 4079 * And page 69: "If an incoming segment is not acceptable, 4080 * an acknowledgment should be sent in reply (unless the RST bit 4081 * is set, if so drop the segment and return)". 4082 */ 4083 if (!th->rst) 4084 tcp_send_dupack(sk, skb); 4085 goto discard; 4086 } 4087 4088 if(th->rst) { 4089 tcp_reset(sk); 4090 goto discard; 4091 } 4092 4093 tcp_replace_ts_recent(tp, TCP_SKB_CB(skb)->seq); 4094 4095 if (th->syn && !before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 4096 TCP_INC_STATS_BH(TCP_MIB_INERRS); 4097 NET_INC_STATS_BH(LINUX_MIB_TCPABORTONSYN); 4098 tcp_reset(sk); 4099 return 1; 4100 } 4101 4102step5: 4103 if(th->ack) 4104 tcp_ack(sk, skb, FLAG_SLOWPATH); 4105 4106 tcp_rcv_rtt_measure_ts(sk, skb); 4107 4108 /* Process urgent data. */ 4109 tcp_urg(sk, skb, th); 4110 4111 /* step 7: process the segment text */ 4112 tcp_data_queue(sk, skb); 4113 4114 tcp_data_snd_check(sk, tp); 4115 tcp_ack_snd_check(sk); 4116 return 0; 4117 4118csum_error: 4119 TCP_INC_STATS_BH(TCP_MIB_INERRS); 4120 4121discard: 4122 __kfree_skb(skb); 4123 return 0; 4124} 4125 4126static int tcp_rcv_synsent_state_process(struct sock *sk, struct sk_buff *skb, 4127 struct tcphdr *th, unsigned len) 4128{ 4129 struct tcp_sock *tp = tcp_sk(sk); 4130 struct inet_connection_sock *icsk = inet_csk(sk); 4131 int saved_clamp = tp->rx_opt.mss_clamp; 4132 4133 tcp_parse_options(skb, &tp->rx_opt, 0); 4134 4135 if (th->ack) { 4136 /* rfc793: 4137 * "If the state is SYN-SENT then 4138 * first check the ACK bit 4139 * If the ACK bit is set 4140 * If SEG.ACK =< ISS, or SEG.ACK > SND.NXT, send 4141 * a reset (unless the RST bit is set, if so drop 4142 * the segment and return)" 4143 * 4144 * We do not send data with SYN, so that RFC-correct 4145 * test reduces to: 4146 */ 4147 if (TCP_SKB_CB(skb)->ack_seq != tp->snd_nxt) 4148 goto reset_and_undo; 4149 4150 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 4151 !between(tp->rx_opt.rcv_tsecr, tp->retrans_stamp, 4152 tcp_time_stamp)) { 4153 NET_INC_STATS_BH(LINUX_MIB_PAWSACTIVEREJECTED); 4154 goto reset_and_undo; 4155 } 4156 4157 /* Now ACK is acceptable. 4158 * 4159 * "If the RST bit is set 4160 * If the ACK was acceptable then signal the user "error: 4161 * connection reset", drop the segment, enter CLOSED state, 4162 * delete TCB, and return." 4163 */ 4164 4165 if (th->rst) { 4166 tcp_reset(sk); 4167 goto discard; 4168 } 4169 4170 /* rfc793: 4171 * "fifth, if neither of the SYN or RST bits is set then 4172 * drop the segment and return." 4173 * 4174 * See note below! 4175 * --ANK(990513) 4176 */ 4177 if (!th->syn) 4178 goto discard_and_undo; 4179 4180 /* rfc793: 4181 * "If the SYN bit is on ... 4182 * are acceptable then ... 4183 * (our SYN has been ACKed), change the connection 4184 * state to ESTABLISHED..." 4185 */ 4186 4187 TCP_ECN_rcv_synack(tp, th); 4188 4189 tp->snd_wl1 = TCP_SKB_CB(skb)->seq; 4190 tcp_ack(sk, skb, FLAG_SLOWPATH); 4191 4192 /* Ok.. it's good. Set up sequence numbers and 4193 * move to established. 4194 */ 4195 tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1; 4196 tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1; 4197 4198 /* RFC1323: The window in SYN & SYN/ACK segments is 4199 * never scaled. 4200 */ 4201 tp->snd_wnd = ntohs(th->window); 4202 tcp_init_wl(tp, TCP_SKB_CB(skb)->ack_seq, TCP_SKB_CB(skb)->seq); 4203 4204 if (!tp->rx_opt.wscale_ok) { 4205 tp->rx_opt.snd_wscale = tp->rx_opt.rcv_wscale = 0; 4206 tp->window_clamp = min(tp->window_clamp, 65535U); 4207 } 4208 4209 if (tp->rx_opt.saw_tstamp) { 4210 tp->rx_opt.tstamp_ok = 1; 4211 tp->tcp_header_len = 4212 sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED; 4213 tp->advmss -= TCPOLEN_TSTAMP_ALIGNED; 4214 tcp_store_ts_recent(tp); 4215 } else { 4216 tp->tcp_header_len = sizeof(struct tcphdr); 4217 } 4218 4219 if (tp->rx_opt.sack_ok && sysctl_tcp_fack) 4220 tp->rx_opt.sack_ok |= 2; 4221 4222 tcp_mtup_init(sk); 4223 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 4224 tcp_initialize_rcv_mss(sk); 4225 4226 /* Remember, tcp_poll() does not lock socket! 4227 * Change state from SYN-SENT only after copied_seq 4228 * is initialized. */ 4229 tp->copied_seq = tp->rcv_nxt; 4230 mb(); 4231 tcp_set_state(sk, TCP_ESTABLISHED); 4232 4233 /* Make sure socket is routed, for correct metrics. */ 4234 icsk->icsk_af_ops->rebuild_header(sk); 4235 4236 tcp_init_metrics(sk); 4237 4238 tcp_init_congestion_control(sk); 4239 4240 /* Prevent spurious tcp_cwnd_restart() on first data 4241 * packet. 4242 */ 4243 tp->lsndtime = tcp_time_stamp; 4244 4245 tcp_init_buffer_space(sk); 4246 4247 if (sock_flag(sk, SOCK_KEEPOPEN)) 4248 inet_csk_reset_keepalive_timer(sk, keepalive_time_when(tp)); 4249 4250 if (!tp->rx_opt.snd_wscale) 4251 __tcp_fast_path_on(tp, tp->snd_wnd); 4252 else 4253 tp->pred_flags = 0; 4254 4255 if (!sock_flag(sk, SOCK_DEAD)) { 4256 sk->sk_state_change(sk); 4257 sk_wake_async(sk, 0, POLL_OUT); 4258 } 4259 4260 if (sk->sk_write_pending || 4261 icsk->icsk_accept_queue.rskq_defer_accept || 4262 icsk->icsk_ack.pingpong) { 4263 /* Save one ACK. Data will be ready after 4264 * several ticks, if write_pending is set. 4265 * 4266 * It may be deleted, but with this feature tcpdumps 4267 * look so _wonderfully_ clever, that I was not able 4268 * to stand against the temptation 8) --ANK 4269 */ 4270 inet_csk_schedule_ack(sk); 4271 icsk->icsk_ack.lrcvtime = tcp_time_stamp; 4272 icsk->icsk_ack.ato = TCP_ATO_MIN; 4273 tcp_incr_quickack(sk); 4274 tcp_enter_quickack_mode(sk); 4275 inet_csk_reset_xmit_timer(sk, ICSK_TIME_DACK, 4276 TCP_DELACK_MAX, TCP_RTO_MAX); 4277 4278discard: 4279 __kfree_skb(skb); 4280 return 0; 4281 } else { 4282 tcp_send_ack(sk); 4283 } 4284 return -1; 4285 } 4286 4287 /* No ACK in the segment */ 4288 4289 if (th->rst) { 4290 /* rfc793: 4291 * "If the RST bit is set 4292 * 4293 * Otherwise (no ACK) drop the segment and return." 4294 */ 4295 4296 goto discard_and_undo; 4297 } 4298 4299 /* PAWS check. */ 4300 if (tp->rx_opt.ts_recent_stamp && tp->rx_opt.saw_tstamp && tcp_paws_check(&tp->rx_opt, 0)) 4301 goto discard_and_undo; 4302 4303 if (th->syn) { 4304 /* We see SYN without ACK. It is attempt of 4305 * simultaneous connect with crossed SYNs. 4306 * Particularly, it can be connect to self. 4307 */ 4308 tcp_set_state(sk, TCP_SYN_RECV); 4309 4310 if (tp->rx_opt.saw_tstamp) { 4311 tp->rx_opt.tstamp_ok = 1; 4312 tcp_store_ts_recent(tp); 4313 tp->tcp_header_len = 4314 sizeof(struct tcphdr) + TCPOLEN_TSTAMP_ALIGNED; 4315 } else { 4316 tp->tcp_header_len = sizeof(struct tcphdr); 4317 } 4318 4319 tp->rcv_nxt = TCP_SKB_CB(skb)->seq + 1; 4320 tp->rcv_wup = TCP_SKB_CB(skb)->seq + 1; 4321 4322 /* RFC1323: The window in SYN & SYN/ACK segments is 4323 * never scaled. 4324 */ 4325 tp->snd_wnd = ntohs(th->window); 4326 tp->snd_wl1 = TCP_SKB_CB(skb)->seq; 4327 tp->max_window = tp->snd_wnd; 4328 4329 TCP_ECN_rcv_syn(tp, th); 4330 4331 tcp_mtup_init(sk); 4332 tcp_sync_mss(sk, icsk->icsk_pmtu_cookie); 4333 tcp_initialize_rcv_mss(sk); 4334 4335 4336 tcp_send_synack(sk); 4337#if 0 4338 /* Note, we could accept data and URG from this segment. 4339 * There are no obstacles to make this. 4340 * 4341 * However, if we ignore data in ACKless segments sometimes, 4342 * we have no reasons to accept it sometimes. 4343 * Also, seems the code doing it in step6 of tcp_rcv_state_process 4344 * is not flawless. So, discard packet for sanity. 4345 * Uncomment this return to process the data. 4346 */ 4347 return -1; 4348#else 4349 goto discard; 4350#endif 4351 } 4352 /* "fifth, if neither of the SYN or RST bits is set then 4353 * drop the segment and return." 4354 */ 4355 4356discard_and_undo: 4357 tcp_clear_options(&tp->rx_opt); 4358 tp->rx_opt.mss_clamp = saved_clamp; 4359 goto discard; 4360 4361reset_and_undo: 4362 tcp_clear_options(&tp->rx_opt); 4363 tp->rx_opt.mss_clamp = saved_clamp; 4364 return 1; 4365} 4366 4367 4368/* 4369 * This function implements the receiving procedure of RFC 793 for 4370 * all states except ESTABLISHED and TIME_WAIT. 4371 * It's called from both tcp_v4_rcv and tcp_v6_rcv and should be 4372 * address independent. 4373 */ 4374 4375int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb, 4376 struct tcphdr *th, unsigned len) 4377{ 4378 struct tcp_sock *tp = tcp_sk(sk); 4379 struct inet_connection_sock *icsk = inet_csk(sk); 4380 int queued = 0; 4381 4382 tp->rx_opt.saw_tstamp = 0; 4383 4384 switch (sk->sk_state) { 4385 case TCP_CLOSE: 4386 goto discard; 4387 4388 case TCP_LISTEN: 4389 if(th->ack) 4390 return 1; 4391 4392 if(th->rst) 4393 goto discard; 4394 4395 if(th->syn) { 4396 if (icsk->icsk_af_ops->conn_request(sk, skb) < 0) 4397 return 1; 4398 4399 /* Now we have several options: In theory there is 4400 * nothing else in the frame. KA9Q has an option to 4401 * send data with the syn, BSD accepts data with the 4402 * syn up to the [to be] advertised window and 4403 * Solaris 2.1 gives you a protocol error. For now 4404 * we just ignore it, that fits the spec precisely 4405 * and avoids incompatibilities. It would be nice in 4406 * future to drop through and process the data. 4407 * 4408 * Now that TTCP is starting to be used we ought to 4409 * queue this data. 4410 * But, this leaves one open to an easy denial of 4411 * service attack, and SYN cookies can't defend 4412 * against this problem. So, we drop the data 4413 * in the interest of security over speed. 4414 */ 4415 goto discard; 4416 } 4417 goto discard; 4418 4419 case TCP_SYN_SENT: 4420 queued = tcp_rcv_synsent_state_process(sk, skb, th, len); 4421 if (queued >= 0) 4422 return queued; 4423 4424 /* Do step6 onward by hand. */ 4425 tcp_urg(sk, skb, th); 4426 __kfree_skb(skb); 4427 tcp_data_snd_check(sk, tp); 4428 return 0; 4429 } 4430 4431 if (tcp_fast_parse_options(skb, th, tp) && tp->rx_opt.saw_tstamp && 4432 tcp_paws_discard(sk, skb)) { 4433 if (!th->rst) { 4434 NET_INC_STATS_BH(LINUX_MIB_PAWSESTABREJECTED); 4435 tcp_send_dupack(sk, skb); 4436 goto discard; 4437 } 4438 /* Reset is accepted even if it did not pass PAWS. */ 4439 } 4440 4441 /* step 1: check sequence number */ 4442 if (!tcp_sequence(tp, TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq)) { 4443 if (!th->rst) 4444 tcp_send_dupack(sk, skb); 4445 goto discard; 4446 } 4447 4448 /* step 2: check RST bit */ 4449 if(th->rst) { 4450 tcp_reset(sk); 4451 goto discard; 4452 } 4453 4454 tcp_replace_ts_recent(tp, TCP_SKB_CB(skb)->seq); 4455 4456 /* step 3: check security and precedence [ignored] */ 4457 4458 /* step 4: 4459 * 4460 * Check for a SYN in window. 4461 */ 4462 if (th->syn && !before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) { 4463 NET_INC_STATS_BH(LINUX_MIB_TCPABORTONSYN); 4464 tcp_reset(sk); 4465 return 1; 4466 } 4467 4468 /* step 5: check the ACK field */ 4469 if (th->ack) { 4470 int acceptable = tcp_ack(sk, skb, FLAG_SLOWPATH); 4471 4472 switch(sk->sk_state) { 4473 case TCP_SYN_RECV: 4474 if (acceptable) { 4475 tp->copied_seq = tp->rcv_nxt; 4476 mb(); 4477 tcp_set_state(sk, TCP_ESTABLISHED); 4478 sk->sk_state_change(sk); 4479 4480 /* Note, that this wakeup is only for marginal 4481 * crossed SYN case. Passively open sockets 4482 * are not waked up, because sk->sk_sleep == 4483 * NULL and sk->sk_socket == NULL. 4484 */ 4485 if (sk->sk_socket) { 4486 sk_wake_async(sk,0,POLL_OUT); 4487 } 4488 4489 tp->snd_una = TCP_SKB_CB(skb)->ack_seq; 4490 tp->snd_wnd = ntohs(th->window) << 4491 tp->rx_opt.snd_wscale; 4492 tcp_init_wl(tp, TCP_SKB_CB(skb)->ack_seq, 4493 TCP_SKB_CB(skb)->seq); 4494 4495 /* tcp_ack considers this ACK as duplicate 4496 * and does not calculate rtt. 4497 * Fix it at least with timestamps. 4498 */ 4499 if (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr && 4500 !tp->srtt) 4501 tcp_ack_saw_tstamp(sk, 0); 4502 4503 if (tp->rx_opt.tstamp_ok) 4504 tp->advmss -= TCPOLEN_TSTAMP_ALIGNED; 4505 4506 /* Make sure socket is routed, for 4507 * correct metrics. 4508 */ 4509 icsk->icsk_af_ops->rebuild_header(sk); 4510 4511 tcp_init_metrics(sk); 4512 4513 tcp_init_congestion_control(sk); 4514 4515 /* Prevent spurious tcp_cwnd_restart() on 4516 * first data packet. 4517 */ 4518 tp->lsndtime = tcp_time_stamp; 4519 4520 tcp_mtup_init(sk); 4521 tcp_initialize_rcv_mss(sk); 4522 tcp_init_buffer_space(sk); 4523 tcp_fast_path_on(tp); 4524 } else { 4525 return 1; 4526 } 4527 break; 4528 4529 case TCP_FIN_WAIT1: 4530 if (tp->snd_una == tp->write_seq) { 4531 tcp_set_state(sk, TCP_FIN_WAIT2); 4532 sk->sk_shutdown |= SEND_SHUTDOWN; 4533 dst_confirm(sk->sk_dst_cache); 4534 4535 if (!sock_flag(sk, SOCK_DEAD)) 4536 /* Wake up lingering close() */ 4537 sk->sk_state_change(sk); 4538 else { 4539 int tmo; 4540 4541 if (tp->linger2 < 0 || 4542 (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 4543 after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt))) { 4544 tcp_done(sk); 4545 NET_INC_STATS_BH(LINUX_MIB_TCPABORTONDATA); 4546 return 1; 4547 } 4548 4549 tmo = tcp_fin_time(sk); 4550 if (tmo > TCP_TIMEWAIT_LEN) { 4551 inet_csk_reset_keepalive_timer(sk, tmo - TCP_TIMEWAIT_LEN); 4552 } else if (th->fin || sock_owned_by_user(sk)) { 4553 /* Bad case. We could lose such FIN otherwise. 4554 * It is not a big problem, but it looks confusing 4555 * and not so rare event. We still can lose it now, 4556 * if it spins in bh_lock_sock(), but it is really 4557 * marginal case. 4558 */ 4559 inet_csk_reset_keepalive_timer(sk, tmo); 4560 } else { 4561 tcp_time_wait(sk, TCP_FIN_WAIT2, tmo); 4562 goto discard; 4563 } 4564 } 4565 } 4566 break; 4567 4568 case TCP_CLOSING: 4569 if (tp->snd_una == tp->write_seq) { 4570 tcp_time_wait(sk, TCP_TIME_WAIT, 0); 4571 goto discard; 4572 } 4573 break; 4574 4575 case TCP_LAST_ACK: 4576 if (tp->snd_una == tp->write_seq) { 4577 tcp_update_metrics(sk); 4578 tcp_done(sk); 4579 goto discard; 4580 } 4581 break; 4582 } 4583 } else 4584 goto discard; 4585 4586 /* step 6: check the URG bit */ 4587 tcp_urg(sk, skb, th); 4588 4589 /* step 7: process the segment text */ 4590 switch (sk->sk_state) { 4591 case TCP_CLOSE_WAIT: 4592 case TCP_CLOSING: 4593 case TCP_LAST_ACK: 4594 if (!before(TCP_SKB_CB(skb)->seq, tp->rcv_nxt)) 4595 break; 4596 case TCP_FIN_WAIT1: 4597 case TCP_FIN_WAIT2: 4598 /* RFC 793 says to queue data in these states, 4599 * RFC 1122 says we MUST send a reset. 4600 * BSD 4.4 also does reset. 4601 */ 4602 if (sk->sk_shutdown & RCV_SHUTDOWN) { 4603 if (TCP_SKB_CB(skb)->end_seq != TCP_SKB_CB(skb)->seq && 4604 after(TCP_SKB_CB(skb)->end_seq - th->fin, tp->rcv_nxt)) { 4605 NET_INC_STATS_BH(LINUX_MIB_TCPABORTONDATA); 4606 tcp_reset(sk); 4607 return 1; 4608 } 4609 } 4610 /* Fall through */ 4611 case TCP_ESTABLISHED: 4612 tcp_data_queue(sk, skb); 4613 queued = 1; 4614 break; 4615 } 4616 4617 /* tcp_data could move socket to TIME-WAIT */ 4618 if (sk->sk_state != TCP_CLOSE) { 4619 tcp_data_snd_check(sk, tp); 4620 tcp_ack_snd_check(sk); 4621 } 4622 4623 if (!queued) { 4624discard: 4625 __kfree_skb(skb); 4626 } 4627 return 0; 4628} 4629 4630EXPORT_SYMBOL(sysctl_tcp_ecn); 4631EXPORT_SYMBOL(sysctl_tcp_reordering); 4632EXPORT_SYMBOL(tcp_parse_options); 4633EXPORT_SYMBOL(tcp_rcv_established); 4634EXPORT_SYMBOL(tcp_rcv_state_process); 4635EXPORT_SYMBOL(tcp_initialize_rcv_mss); 4636