00a41499d52c89c0961f6229d79f58022c25ba46
[pandora-kernel.git] / net / ipv4 / tcp_input.c
1 /*
2  * INET         An implementation of the TCP/IP protocol suite for the LINUX
3  *              operating system.  INET is implemented using the  BSD Socket
4  *              interface as the means of communication with the user level.
5  *
6  *              Implementation of the Transmission Control Protocol(TCP).
7  *
8  * Authors:     Ross Biro
9  *              Fred N. van Kempen, <waltje@uWalt.NL.Mugnet.ORG>
10  *              Mark Evans, <evansmp@uhura.aston.ac.uk>
11  *              Corey Minyard <wf-rch!minyard@relay.EU.net>
12  *              Florian La Roche, <flla@stud.uni-sb.de>
13  *              Charles Hedrick, <hedrick@klinzhai.rutgers.edu>
14  *              Linus Torvalds, <torvalds@cs.helsinki.fi>
15  *              Alan Cox, <gw4pts@gw4pts.ampr.org>
16  *              Matthew Dillon, <dillon@apollo.west.oic.com>
17  *              Arnt Gulbrandsen, <agulbra@nvg.unit.no>
18  *              Jorge Cwik, <jorge@laser.satlink.net>
19  */
20
21 /*
22  * Changes:
23  *              Pedro Roque     :       Fast Retransmit/Recovery.
24  *                                      Two receive queues.
25  *                                      Retransmit queue handled by TCP.
26  *                                      Better retransmit timer handling.
27  *                                      New congestion avoidance.
28  *                                      Header prediction.
29  *                                      Variable renaming.
30  *
31  *              Eric            :       Fast Retransmit.
32  *              Randy Scott     :       MSS option defines.
33  *              Eric Schenk     :       Fixes to slow start algorithm.
34  *              Eric Schenk     :       Yet another double ACK bug.
35  *              Eric Schenk     :       Delayed ACK bug fixes.
36  *              Eric Schenk     :       Floyd style fast retrans war avoidance.
37  *              David S. Miller :       Don't allow zero congestion window.
38  *              Eric Schenk     :       Fix retransmitter so that it sends
39  *                                      next packet on ack of previous packet.
40  *              Andi Kleen      :       Moved open_request checking here
41  *                                      and process RSTs for open_requests.
42  *              Andi Kleen      :       Better prune_queue, and other fixes.
43  *              Andrey Savochkin:       Fix RTT measurements in the presence of
44  *                                      timestamps.
45  *              Andrey Savochkin:       Check sequence numbers correctly when
46  *                                      removing SACKs due to in sequence incoming
47  *                                      data segments.
48  *              Andi Kleen:             Make sure we never ack data there is not
49  *                                      enough room for. Also make this condition
50  *                                      a fatal error if it might still happen.
51  *              Andi Kleen:             Add tcp_measure_rcv_mss to make
52  *                                      connections with MSS<min(MTU,ann. MSS)
53  *                                      work without delayed acks.
54  *              Andi Kleen:             Process packets with PSH set in the
55  *                                      fast path.
56  *              J Hadi Salim:           ECN support
57  *              Andrei Gurtov,
58  *              Pasi Sarolahti,
59  *              Panu Kuhlberg:          Experimental audit of TCP (re)transmission
60  *                                      engine. Lots of bugs are found.
61  *              Pasi Sarolahti:         F-RTO for dealing with spurious RTOs
62  */
63
64 #define pr_fmt(fmt) "TCP: " fmt
65
66 #include <linux/mm.h>
67 #include <linux/slab.h>
68 #include <linux/module.h>
69 #include <linux/sysctl.h>
70 #include <linux/kernel.h>
71 #include <net/dst.h>
72 #include <net/tcp.h>
73 #include <net/inet_common.h>
74 #include <linux/ipsec.h>
75 #include <asm/unaligned.h>
76 #include <linux/errqueue.h>
77
78 int sysctl_tcp_timestamps __read_mostly = 1;
79 int sysctl_tcp_window_scaling __read_mostly = 1;
80 int sysctl_tcp_sack __read_mostly = 1;
81 int sysctl_tcp_fack __read_mostly = 1;
82 int sysctl_tcp_reordering __read_mostly = TCP_FASTRETRANS_THRESH;
83 EXPORT_SYMBOL(sysctl_tcp_reordering);
84 int sysctl_tcp_dsack __read_mostly = 1;
85 int sysctl_tcp_app_win __read_mostly = 31;
86 int sysctl_tcp_adv_win_scale __read_mostly = 1;
87 EXPORT_SYMBOL(sysctl_tcp_adv_win_scale);
88
89 /* rfc5961 challenge ack rate limiting */
90 int sysctl_tcp_challenge_ack_limit = 100;
91
92 int sysctl_tcp_stdurg __read_mostly;
93 int sysctl_tcp_rfc1337 __read_mostly;
94 int sysctl_tcp_max_orphans __read_mostly = NR_FILE;
95 int sysctl_tcp_frto __read_mostly = 2;
96
97 int sysctl_tcp_thin_dupack __read_mostly;
98
99 int sysctl_tcp_moderate_rcvbuf __read_mostly = 1;
100 int sysctl_tcp_early_retrans __read_mostly = 3;
101
102 #define FLAG_DATA               0x01 /* Incoming frame contained data.          */
103 #define FLAG_WIN_UPDATE         0x02 /* Incoming ACK was a window update.       */
104 #define FLAG_DATA_ACKED         0x04 /* This ACK acknowledged new data.         */
105 #define FLAG_RETRANS_DATA_ACKED 0x08 /* "" "" some of which was retransmitted.  */
106 #define FLAG_SYN_ACKED          0x10 /* This ACK acknowledged SYN.              */
107 #define FLAG_DATA_SACKED        0x20 /* New SACK.                               */
108 #define FLAG_ECE                0x40 /* ECE in this ACK                         */
109 #define FLAG_SLOWPATH           0x100 /* Do not skip RFC checks for window update.*/
110 #define FLAG_ORIG_SACK_ACKED    0x200 /* Never retransmitted data are (s)acked  */
111 #define FLAG_SND_UNA_ADVANCED   0x400 /* Snd_una was changed (!= FLAG_DATA_ACKED) */
112 #define FLAG_DSACKING_ACK       0x800 /* SACK blocks contained D-SACK info */
113 #define FLAG_SACK_RENEGING      0x2000 /* snd_una advanced to a sacked seq */
114 #define FLAG_UPDATE_TS_RECENT   0x4000 /* tcp_replace_ts_recent() */
115
116 #define FLAG_ACKED              (FLAG_DATA_ACKED|FLAG_SYN_ACKED)
117 #define FLAG_NOT_DUP            (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)
118 #define FLAG_CA_ALERT           (FLAG_DATA_SACKED|FLAG_ECE)
119 #define FLAG_FORWARD_PROGRESS   (FLAG_ACKED|FLAG_DATA_SACKED)
120
121 #define TCP_REMNANT (TCP_FLAG_FIN|TCP_FLAG_URG|TCP_FLAG_SYN|TCP_FLAG_PSH)
122 #define TCP_HP_BITS (~(TCP_RESERVED_BITS|TCP_FLAG_PSH))
123
124 /* Adapt the MSS value used to make delayed ack decision to the
125  * real world.
126  */
127 static void tcp_measure_rcv_mss(struct sock *sk, const struct sk_buff *skb)
128 {
129         struct inet_connection_sock *icsk = inet_csk(sk);
130         const unsigned int lss = icsk->icsk_ack.last_seg_size;
131         unsigned int len;
132
133         icsk->icsk_ack.last_seg_size = 0;
134
135         /* skb->len may jitter because of SACKs, even if peer
136          * sends good full-sized frames.
137          */
138         len = skb_shinfo(skb)->gso_size ? : skb->len;
139         if (len >= icsk->icsk_ack.rcv_mss) {
140                 icsk->icsk_ack.rcv_mss = len;
141         } else {
142                 /* Otherwise, we make more careful check taking into account,
143                  * that SACKs block is variable.
144                  *
145                  * "len" is invariant segment length, including TCP header.
146                  */
147                 len += skb->data - skb_transport_header(skb);
148                 if (len >= TCP_MSS_DEFAULT + sizeof(struct tcphdr) ||
149                     /* If PSH is not set, packet should be
150                      * full sized, provided peer TCP is not badly broken.
151                      * This observation (if it is correct 8)) allows
152                      * to handle super-low mtu links fairly.
153                      */
154                     (len >= TCP_MIN_MSS + sizeof(struct tcphdr) &&
155                      !(tcp_flag_word(tcp_hdr(skb)) & TCP_REMNANT))) {
156                         /* Subtract also invariant (if peer is RFC compliant),
157                          * tcp header plus fixed timestamp option length.
158                          * Resulting "len" is MSS free of SACK jitter.
159                          */
160                         len -= tcp_sk(sk)->tcp_header_len;
161                         icsk->icsk_ack.last_seg_size = len;
162                         if (len == lss) {
163                                 icsk->icsk_ack.rcv_mss = len;
164                                 return;
165                         }
166                 }
167                 if (icsk->icsk_ack.pending & ICSK_ACK_PUSHED)
168                         icsk->icsk_ack.pending |= ICSK_ACK_PUSHED2;
169                 icsk->icsk_ack.pending |= ICSK_ACK_PUSHED;
170         }
171 }
172
173 static void tcp_incr_quickack(struct sock *sk)
174 {
175         struct inet_connection_sock *icsk = inet_csk(sk);
176         unsigned int quickacks = tcp_sk(sk)->rcv_wnd / (2 * icsk->icsk_ack.rcv_mss);
177
178         if (quickacks == 0)
179                 quickacks = 2;
180         if (quickacks > icsk->icsk_ack.quick)
181                 icsk->icsk_ack.quick = min(quickacks, TCP_MAX_QUICKACKS);
182 }
183
184 static void tcp_enter_quickack_mode(struct sock *sk)
185 {
186         struct inet_connection_sock *icsk = inet_csk(sk);
187         tcp_incr_quickack(sk);
188         icsk->icsk_ack.pingpong = 0;
189         icsk->icsk_ack.ato = TCP_ATO_MIN;
190 }
191
192 /* Send ACKs quickly, if "quick" count is not exhausted
193  * and the session is not interactive.
194  */
195
196 static inline bool tcp_in_quickack_mode(const struct sock *sk)
197 {
198         const struct inet_connection_sock *icsk = inet_csk(sk);
199
200         return icsk->icsk_ack.quick && !icsk->icsk_ack.pingpong;
201 }
202
203 static void tcp_ecn_queue_cwr(struct tcp_sock *tp)
204 {
205         if (tp->ecn_flags & TCP_ECN_OK)
206                 tp->ecn_flags |= TCP_ECN_QUEUE_CWR;
207 }
208
209 static void tcp_ecn_accept_cwr(struct tcp_sock *tp, const struct sk_buff *skb)
210 {
211         if (tcp_hdr(skb)->cwr)
212                 tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
213 }
214
215 static void tcp_ecn_withdraw_cwr(struct tcp_sock *tp)
216 {
217         tp->ecn_flags &= ~TCP_ECN_DEMAND_CWR;
218 }
219
220 static void __tcp_ecn_check_ce(struct tcp_sock *tp, const struct sk_buff *skb)
221 {
222         switch (TCP_SKB_CB(skb)->ip_dsfield & INET_ECN_MASK) {
223         case INET_ECN_NOT_ECT:
224                 /* Funny extension: if ECT is not set on a segment,
225                  * and we already seen ECT on a previous segment,
226                  * it is probably a retransmit.
227                  */
228                 if (tp->ecn_flags & TCP_ECN_SEEN)
229                         tcp_enter_quickack_mode((struct sock *)tp);
230                 break;
231         case INET_ECN_CE:
232                 if (tcp_ca_needs_ecn((struct sock *)tp))
233                         tcp_ca_event((struct sock *)tp, CA_EVENT_ECN_IS_CE);
234
235                 if (!(tp->ecn_flags & TCP_ECN_DEMAND_CWR)) {
236                         /* Better not delay acks, sender can have a very low cwnd */
237                         tcp_enter_quickack_mode((struct sock *)tp);
238                         tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
239                 }
240                 tp->ecn_flags |= TCP_ECN_SEEN;
241                 break;
242         default:
243                 if (tcp_ca_needs_ecn((struct sock *)tp))
244                         tcp_ca_event((struct sock *)tp, CA_EVENT_ECN_NO_CE);
245                 tp->ecn_flags |= TCP_ECN_SEEN;
246                 break;
247         }
248 }
249
250 static void tcp_ecn_check_ce(struct tcp_sock *tp, const struct sk_buff *skb)
251 {
252         if (tp->ecn_flags & TCP_ECN_OK)
253                 __tcp_ecn_check_ce(tp, skb);
254 }
255
256 static void tcp_ecn_rcv_synack(struct tcp_sock *tp, const struct tcphdr *th)
257 {
258         if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || th->cwr))
259                 tp->ecn_flags &= ~TCP_ECN_OK;
260 }
261
262 static void tcp_ecn_rcv_syn(struct tcp_sock *tp, const struct tcphdr *th)
263 {
264         if ((tp->ecn_flags & TCP_ECN_OK) && (!th->ece || !th->cwr))
265                 tp->ecn_flags &= ~TCP_ECN_OK;
266 }
267
268 static bool tcp_ecn_rcv_ecn_echo(const struct tcp_sock *tp, const struct tcphdr *th)
269 {
270         if (th->ece && !th->syn && (tp->ecn_flags & TCP_ECN_OK))
271                 return true;
272         return false;
273 }
274
275 /* Buffer size and advertised window tuning.
276  *
277  * 1. Tuning sk->sk_sndbuf, when connection enters established state.
278  */
279
280 static void tcp_sndbuf_expand(struct sock *sk)
281 {
282         const struct tcp_sock *tp = tcp_sk(sk);
283         int sndmem, per_mss;
284         u32 nr_segs;
285
286         /* Worst case is non GSO/TSO : each frame consumes one skb
287          * and skb->head is kmalloced using power of two area of memory
288          */
289         per_mss = max_t(u32, tp->rx_opt.mss_clamp, tp->mss_cache) +
290                   MAX_TCP_HEADER +
291                   SKB_DATA_ALIGN(sizeof(struct skb_shared_info));
292
293         per_mss = roundup_pow_of_two(per_mss) +
294                   SKB_DATA_ALIGN(sizeof(struct sk_buff));
295
296         nr_segs = max_t(u32, TCP_INIT_CWND, tp->snd_cwnd);
297         nr_segs = max_t(u32, nr_segs, tp->reordering + 1);
298
299         /* Fast Recovery (RFC 5681 3.2) :
300          * Cubic needs 1.7 factor, rounded to 2 to include
301          * extra cushion (application might react slowly to POLLOUT)
302          */
303         sndmem = 2 * nr_segs * per_mss;
304
305         if (sk->sk_sndbuf < sndmem)
306                 sk->sk_sndbuf = min(sndmem, sysctl_tcp_wmem[2]);
307 }
308
309 /* 2. Tuning advertised window (window_clamp, rcv_ssthresh)
310  *
311  * All tcp_full_space() is split to two parts: "network" buffer, allocated
312  * forward and advertised in receiver window (tp->rcv_wnd) and
313  * "application buffer", required to isolate scheduling/application
314  * latencies from network.
315  * window_clamp is maximal advertised window. It can be less than
316  * tcp_full_space(), in this case tcp_full_space() - window_clamp
317  * is reserved for "application" buffer. The less window_clamp is
318  * the smoother our behaviour from viewpoint of network, but the lower
319  * throughput and the higher sensitivity of the connection to losses. 8)
320  *
321  * rcv_ssthresh is more strict window_clamp used at "slow start"
322  * phase to predict further behaviour of this connection.
323  * It is used for two goals:
324  * - to enforce header prediction at sender, even when application
325  *   requires some significant "application buffer". It is check #1.
326  * - to prevent pruning of receive queue because of misprediction
327  *   of receiver window. Check #2.
328  *
329  * The scheme does not work when sender sends good segments opening
330  * window and then starts to feed us spaghetti. But it should work
331  * in common situations. Otherwise, we have to rely on queue collapsing.
332  */
333
334 /* Slow part of check#2. */
335 static int __tcp_grow_window(const struct sock *sk, const struct sk_buff *skb)
336 {
337         struct tcp_sock *tp = tcp_sk(sk);
338         /* Optimize this! */
339         int truesize = tcp_win_from_space(skb->truesize) >> 1;
340         int window = tcp_win_from_space(sysctl_tcp_rmem[2]) >> 1;
341
342         while (tp->rcv_ssthresh <= window) {
343                 if (truesize <= skb->len)
344                         return 2 * inet_csk(sk)->icsk_ack.rcv_mss;
345
346                 truesize >>= 1;
347                 window >>= 1;
348         }
349         return 0;
350 }
351
352 static void tcp_grow_window(struct sock *sk, const struct sk_buff *skb)
353 {
354         struct tcp_sock *tp = tcp_sk(sk);
355
356         /* Check #1 */
357         if (tp->rcv_ssthresh < tp->window_clamp &&
358             (int)tp->rcv_ssthresh < tcp_space(sk) &&
359             !sk_under_memory_pressure(sk)) {
360                 int incr;
361
362                 /* Check #2. Increase window, if skb with such overhead
363                  * will fit to rcvbuf in future.
364                  */
365                 if (tcp_win_from_space(skb->truesize) <= skb->len)
366                         incr = 2 * tp->advmss;
367                 else
368                         incr = __tcp_grow_window(sk, skb);
369
370                 if (incr) {
371                         incr = max_t(int, incr, 2 * skb->len);
372                         tp->rcv_ssthresh = min(tp->rcv_ssthresh + incr,
373                                                tp->window_clamp);
374                         inet_csk(sk)->icsk_ack.quick |= 1;
375                 }
376         }
377 }
378
379 /* 3. Tuning rcvbuf, when connection enters established state. */
380 static void tcp_fixup_rcvbuf(struct sock *sk)
381 {
382         u32 mss = tcp_sk(sk)->advmss;
383         int rcvmem;
384
385         rcvmem = 2 * SKB_TRUESIZE(mss + MAX_TCP_HEADER) *
386                  tcp_default_init_rwnd(mss);
387
388         /* Dynamic Right Sizing (DRS) has 2 to 3 RTT latency
389          * Allow enough cushion so that sender is not limited by our window
390          */
391         if (sysctl_tcp_moderate_rcvbuf)
392                 rcvmem <<= 2;
393
394         if (sk->sk_rcvbuf < rcvmem)
395                 sk->sk_rcvbuf = min(rcvmem, sysctl_tcp_rmem[2]);
396 }
397
398 /* 4. Try to fixup all. It is made immediately after connection enters
399  *    established state.
400  */
401 void tcp_init_buffer_space(struct sock *sk)
402 {
403         struct tcp_sock *tp = tcp_sk(sk);
404         int maxwin;
405
406         if (!(sk->sk_userlocks & SOCK_RCVBUF_LOCK))
407                 tcp_fixup_rcvbuf(sk);
408         if (!(sk->sk_userlocks & SOCK_SNDBUF_LOCK))
409                 tcp_sndbuf_expand(sk);
410
411         tp->rcvq_space.space = tp->rcv_wnd;
412         tp->rcvq_space.time = tcp_time_stamp;
413         tp->rcvq_space.seq = tp->copied_seq;
414
415         maxwin = tcp_full_space(sk);
416
417         if (tp->window_clamp >= maxwin) {
418                 tp->window_clamp = maxwin;
419
420                 if (sysctl_tcp_app_win && maxwin > 4 * tp->advmss)
421                         tp->window_clamp = max(maxwin -
422                                                (maxwin >> sysctl_tcp_app_win),
423                                                4 * tp->advmss);
424         }
425
426         /* Force reservation of one segment. */
427         if (sysctl_tcp_app_win &&
428             tp->window_clamp > 2 * tp->advmss &&
429             tp->window_clamp + tp->advmss > maxwin)
430                 tp->window_clamp = max(2 * tp->advmss, maxwin - tp->advmss);
431
432         tp->rcv_ssthresh = min(tp->rcv_ssthresh, tp->window_clamp);
433         tp->snd_cwnd_stamp = tcp_time_stamp;
434 }
435
436 /* 5. Recalculate window clamp after socket hit its memory bounds. */
437 static void tcp_clamp_window(struct sock *sk)
438 {
439         struct tcp_sock *tp = tcp_sk(sk);
440         struct inet_connection_sock *icsk = inet_csk(sk);
441
442         icsk->icsk_ack.quick = 0;
443
444         if (sk->sk_rcvbuf < sysctl_tcp_rmem[2] &&
445             !(sk->sk_userlocks & SOCK_RCVBUF_LOCK) &&
446             !sk_under_memory_pressure(sk) &&
447             sk_memory_allocated(sk) < sk_prot_mem_limits(sk, 0)) {
448                 sk->sk_rcvbuf = min(atomic_read(&sk->sk_rmem_alloc),
449                                     sysctl_tcp_rmem[2]);
450         }
451         if (atomic_read(&sk->sk_rmem_alloc) > sk->sk_rcvbuf)
452                 tp->rcv_ssthresh = min(tp->window_clamp, 2U * tp->advmss);
453 }
454
455 /* Initialize RCV_MSS value.
456  * RCV_MSS is an our guess about MSS used by the peer.
457  * We haven't any direct information about the MSS.
458  * It's better to underestimate the RCV_MSS rather than overestimate.
459  * Overestimations make us ACKing less frequently than needed.
460  * Underestimations are more easy to detect and fix by tcp_measure_rcv_mss().
461  */
462 void tcp_initialize_rcv_mss(struct sock *sk)
463 {
464         const struct tcp_sock *tp = tcp_sk(sk);
465         unsigned int hint = min_t(unsigned int, tp->advmss, tp->mss_cache);
466
467         hint = min(hint, tp->rcv_wnd / 2);
468         hint = min(hint, TCP_MSS_DEFAULT);
469         hint = max(hint, TCP_MIN_MSS);
470
471         inet_csk(sk)->icsk_ack.rcv_mss = hint;
472 }
473 EXPORT_SYMBOL(tcp_initialize_rcv_mss);
474
475 /* Receiver "autotuning" code.
476  *
477  * The algorithm for RTT estimation w/o timestamps is based on
478  * Dynamic Right-Sizing (DRS) by Wu Feng and Mike Fisk of LANL.
479  * <http://public.lanl.gov/radiant/pubs.html#DRS>
480  *
481  * More detail on this code can be found at
482  * <http://staff.psc.edu/jheffner/>,
483  * though this reference is out of date.  A new paper
484  * is pending.
485  */
486 static void tcp_rcv_rtt_update(struct tcp_sock *tp, u32 sample, int win_dep)
487 {
488         u32 new_sample = tp->rcv_rtt_est.rtt;
489         long m = sample;
490
491         if (m == 0)
492                 m = 1;
493
494         if (new_sample != 0) {
495                 /* If we sample in larger samples in the non-timestamp
496                  * case, we could grossly overestimate the RTT especially
497                  * with chatty applications or bulk transfer apps which
498                  * are stalled on filesystem I/O.
499                  *
500                  * Also, since we are only going for a minimum in the
501                  * non-timestamp case, we do not smooth things out
502                  * else with timestamps disabled convergence takes too
503                  * long.
504                  */
505                 if (!win_dep) {
506                         m -= (new_sample >> 3);
507                         new_sample += m;
508                 } else {
509                         m <<= 3;
510                         if (m < new_sample)
511                                 new_sample = m;
512                 }
513         } else {
514                 /* No previous measure. */
515                 new_sample = m << 3;
516         }
517
518         if (tp->rcv_rtt_est.rtt != new_sample)
519                 tp->rcv_rtt_est.rtt = new_sample;
520 }
521
522 static inline void tcp_rcv_rtt_measure(struct tcp_sock *tp)
523 {
524         if (tp->rcv_rtt_est.time == 0)
525                 goto new_measure;
526         if (before(tp->rcv_nxt, tp->rcv_rtt_est.seq))
527                 return;
528         tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rcv_rtt_est.time, 1);
529
530 new_measure:
531         tp->rcv_rtt_est.seq = tp->rcv_nxt + tp->rcv_wnd;
532         tp->rcv_rtt_est.time = tcp_time_stamp;
533 }
534
535 static inline void tcp_rcv_rtt_measure_ts(struct sock *sk,
536                                           const struct sk_buff *skb)
537 {
538         struct tcp_sock *tp = tcp_sk(sk);
539         if (tp->rx_opt.rcv_tsecr &&
540             (TCP_SKB_CB(skb)->end_seq -
541              TCP_SKB_CB(skb)->seq >= inet_csk(sk)->icsk_ack.rcv_mss))
542                 tcp_rcv_rtt_update(tp, tcp_time_stamp - tp->rx_opt.rcv_tsecr, 0);
543 }
544
545 /*
546  * This function should be called every time data is copied to user space.
547  * It calculates the appropriate TCP receive buffer space.
548  */
549 void tcp_rcv_space_adjust(struct sock *sk)
550 {
551         struct tcp_sock *tp = tcp_sk(sk);
552         int time;
553         int copied;
554
555         time = tcp_time_stamp - tp->rcvq_space.time;
556         if (time < (tp->rcv_rtt_est.rtt >> 3) || tp->rcv_rtt_est.rtt == 0)
557                 return;
558
559         /* Number of bytes copied to user in last RTT */
560         copied = tp->copied_seq - tp->rcvq_space.seq;
561         if (copied <= tp->rcvq_space.space)
562                 goto new_measure;
563
564         /* A bit of theory :
565          * copied = bytes received in previous RTT, our base window
566          * To cope with packet losses, we need a 2x factor
567          * To cope with slow start, and sender growing its cwin by 100 %
568          * every RTT, we need a 4x factor, because the ACK we are sending
569          * now is for the next RTT, not the current one :
570          * <prev RTT . ><current RTT .. ><next RTT .... >
571          */
572
573         if (sysctl_tcp_moderate_rcvbuf &&
574             !(sk->sk_userlocks & SOCK_RCVBUF_LOCK)) {
575                 int rcvwin, rcvmem, rcvbuf;
576
577                 /* minimal window to cope with packet losses, assuming
578                  * steady state. Add some cushion because of small variations.
579                  */
580                 rcvwin = (copied << 1) + 16 * tp->advmss;
581
582                 /* If rate increased by 25%,
583                  *      assume slow start, rcvwin = 3 * copied
584                  * If rate increased by 50%,
585                  *      assume sender can use 2x growth, rcvwin = 4 * copied
586                  */
587                 if (copied >=
588                     tp->rcvq_space.space + (tp->rcvq_space.space >> 2)) {
589                         if (copied >=
590                             tp->rcvq_space.space + (tp->rcvq_space.space >> 1))
591                                 rcvwin <<= 1;
592                         else
593                                 rcvwin += (rcvwin >> 1);
594                 }
595
596                 rcvmem = SKB_TRUESIZE(tp->advmss + MAX_TCP_HEADER);
597                 while (tcp_win_from_space(rcvmem) < tp->advmss)
598                         rcvmem += 128;
599
600                 rcvbuf = min(rcvwin / tp->advmss * rcvmem, sysctl_tcp_rmem[2]);
601                 if (rcvbuf > sk->sk_rcvbuf) {
602                         sk->sk_rcvbuf = rcvbuf;
603
604                         /* Make the window clamp follow along.  */
605                         tp->window_clamp = rcvwin;
606                 }
607         }
608         tp->rcvq_space.space = copied;
609
610 new_measure:
611         tp->rcvq_space.seq = tp->copied_seq;
612         tp->rcvq_space.time = tcp_time_stamp;
613 }
614
615 /* There is something which you must keep in mind when you analyze the
616  * behavior of the tp->ato delayed ack timeout interval.  When a
617  * connection starts up, we want to ack as quickly as possible.  The
618  * problem is that "good" TCP's do slow start at the beginning of data
619  * transmission.  The means that until we send the first few ACK's the
620  * sender will sit on his end and only queue most of his data, because
621  * he can only send snd_cwnd unacked packets at any given time.  For
622  * each ACK we send, he increments snd_cwnd and transmits more of his
623  * queue.  -DaveM
624  */
625 static void tcp_event_data_recv(struct sock *sk, struct sk_buff *skb)
626 {
627         struct tcp_sock *tp = tcp_sk(sk);
628         struct inet_connection_sock *icsk = inet_csk(sk);
629         u32 now;
630
631         inet_csk_schedule_ack(sk);
632
633         tcp_measure_rcv_mss(sk, skb);
634
635         tcp_rcv_rtt_measure(tp);
636
637         now = tcp_time_stamp;
638
639         if (!icsk->icsk_ack.ato) {
640                 /* The _first_ data packet received, initialize
641                  * delayed ACK engine.
642                  */
643                 tcp_incr_quickack(sk);
644                 icsk->icsk_ack.ato = TCP_ATO_MIN;
645         } else {
646                 int m = now - icsk->icsk_ack.lrcvtime;
647
648                 if (m <= TCP_ATO_MIN / 2) {
649                         /* The fastest case is the first. */
650                         icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + TCP_ATO_MIN / 2;
651                 } else if (m < icsk->icsk_ack.ato) {
652                         icsk->icsk_ack.ato = (icsk->icsk_ack.ato >> 1) + m;
653                         if (icsk->icsk_ack.ato > icsk->icsk_rto)
654                                 icsk->icsk_ack.ato = icsk->icsk_rto;
655                 } else if (m > icsk->icsk_rto) {
656                         /* Too long gap. Apparently sender failed to
657                          * restart window, so that we send ACKs quickly.
658                          */
659                         tcp_incr_quickack(sk);
660                         sk_mem_reclaim(sk);
661                 }
662         }
663         icsk->icsk_ack.lrcvtime = now;
664
665         tcp_ecn_check_ce(tp, skb);
666
667         if (skb->len >= 128)
668                 tcp_grow_window(sk, skb);
669 }
670
671 /* Called to compute a smoothed rtt estimate. The data fed to this
672  * routine either comes from timestamps, or from segments that were
673  * known _not_ to have been retransmitted [see Karn/Partridge
674  * Proceedings SIGCOMM 87]. The algorithm is from the SIGCOMM 88
675  * piece by Van Jacobson.
676  * NOTE: the next three routines used to be one big routine.
677  * To save cycles in the RFC 1323 implementation it was better to break
678  * it up into three procedures. -- erics
679  */
680 static void tcp_rtt_estimator(struct sock *sk, long mrtt_us)
681 {
682         struct tcp_sock *tp = tcp_sk(sk);
683         long m = mrtt_us; /* RTT */
684         u32 srtt = tp->srtt_us;
685
686         /*      The following amusing code comes from Jacobson's
687          *      article in SIGCOMM '88.  Note that rtt and mdev
688          *      are scaled versions of rtt and mean deviation.
689          *      This is designed to be as fast as possible
690          *      m stands for "measurement".
691          *
692          *      On a 1990 paper the rto value is changed to:
693          *      RTO = rtt + 4 * mdev
694          *
695          * Funny. This algorithm seems to be very broken.
696          * These formulae increase RTO, when it should be decreased, increase
697          * too slowly, when it should be increased quickly, decrease too quickly
698          * etc. I guess in BSD RTO takes ONE value, so that it is absolutely
699          * does not matter how to _calculate_ it. Seems, it was trap
700          * that VJ failed to avoid. 8)
701          */
702         if (srtt != 0) {
703                 m -= (srtt >> 3);       /* m is now error in rtt est */
704                 srtt += m;              /* rtt = 7/8 rtt + 1/8 new */
705                 if (m < 0) {
706                         m = -m;         /* m is now abs(error) */
707                         m -= (tp->mdev_us >> 2);   /* similar update on mdev */
708                         /* This is similar to one of Eifel findings.
709                          * Eifel blocks mdev updates when rtt decreases.
710                          * This solution is a bit different: we use finer gain
711                          * for mdev in this case (alpha*beta).
712                          * Like Eifel it also prevents growth of rto,
713                          * but also it limits too fast rto decreases,
714                          * happening in pure Eifel.
715                          */
716                         if (m > 0)
717                                 m >>= 3;
718                 } else {
719                         m -= (tp->mdev_us >> 2);   /* similar update on mdev */
720                 }
721                 tp->mdev_us += m;               /* mdev = 3/4 mdev + 1/4 new */
722                 if (tp->mdev_us > tp->mdev_max_us) {
723                         tp->mdev_max_us = tp->mdev_us;
724                         if (tp->mdev_max_us > tp->rttvar_us)
725                                 tp->rttvar_us = tp->mdev_max_us;
726                 }
727                 if (after(tp->snd_una, tp->rtt_seq)) {
728                         if (tp->mdev_max_us < tp->rttvar_us)
729                                 tp->rttvar_us -= (tp->rttvar_us - tp->mdev_max_us) >> 2;
730                         tp->rtt_seq = tp->snd_nxt;
731                         tp->mdev_max_us = tcp_rto_min_us(sk);
732                 }
733         } else {
734                 /* no previous measure. */
735                 srtt = m << 3;          /* take the measured time to be rtt */
736                 tp->mdev_us = m << 1;   /* make sure rto = 3*rtt */
737                 tp->rttvar_us = max(tp->mdev_us, tcp_rto_min_us(sk));
738                 tp->mdev_max_us = tp->rttvar_us;
739                 tp->rtt_seq = tp->snd_nxt;
740         }
741         tp->srtt_us = max(1U, srtt);
742 }
743
744 /* Set the sk_pacing_rate to allow proper sizing of TSO packets.
745  * Note: TCP stack does not yet implement pacing.
746  * FQ packet scheduler can be used to implement cheap but effective
747  * TCP pacing, to smooth the burst on large writes when packets
748  * in flight is significantly lower than cwnd (or rwin)
749  */
750 static void tcp_update_pacing_rate(struct sock *sk)
751 {
752         const struct tcp_sock *tp = tcp_sk(sk);
753         u64 rate;
754
755         /* set sk_pacing_rate to 200 % of current rate (mss * cwnd / srtt) */
756         rate = (u64)tp->mss_cache * 2 * (USEC_PER_SEC << 3);
757
758         rate *= max(tp->snd_cwnd, tp->packets_out);
759
760         if (likely(tp->srtt_us))
761                 do_div(rate, tp->srtt_us);
762
763         /* ACCESS_ONCE() is needed because sch_fq fetches sk_pacing_rate
764          * without any lock. We want to make sure compiler wont store
765          * intermediate values in this location.
766          */
767         ACCESS_ONCE(sk->sk_pacing_rate) = min_t(u64, rate,
768                                                 sk->sk_max_pacing_rate);
769 }
770
771 /* Calculate rto without backoff.  This is the second half of Van Jacobson's
772  * routine referred to above.
773  */
774 static void tcp_set_rto(struct sock *sk)
775 {
776         const struct tcp_sock *tp = tcp_sk(sk);
777         /* Old crap is replaced with new one. 8)
778          *
779          * More seriously:
780          * 1. If rtt variance happened to be less 50msec, it is hallucination.
781          *    It cannot be less due to utterly erratic ACK generation made
782          *    at least by solaris and freebsd. "Erratic ACKs" has _nothing_
783          *    to do with delayed acks, because at cwnd>2 true delack timeout
784          *    is invisible. Actually, Linux-2.4 also generates erratic
785          *    ACKs in some circumstances.
786          */
787         inet_csk(sk)->icsk_rto = __tcp_set_rto(tp);
788
789         /* 2. Fixups made earlier cannot be right.
790          *    If we do not estimate RTO correctly without them,
791          *    all the algo is pure shit and should be replaced
792          *    with correct one. It is exactly, which we pretend to do.
793          */
794
795         /* NOTE: clamping at TCP_RTO_MIN is not required, current algo
796          * guarantees that rto is higher.
797          */
798         tcp_bound_rto(sk);
799 }
800
801 __u32 tcp_init_cwnd(const struct tcp_sock *tp, const struct dst_entry *dst)
802 {
803         __u32 cwnd = (dst ? dst_metric(dst, RTAX_INITCWND) : 0);
804
805         if (!cwnd)
806                 cwnd = TCP_INIT_CWND;
807         return min_t(__u32, cwnd, tp->snd_cwnd_clamp);
808 }
809
810 /*
811  * Packet counting of FACK is based on in-order assumptions, therefore TCP
812  * disables it when reordering is detected
813  */
814 void tcp_disable_fack(struct tcp_sock *tp)
815 {
816         /* RFC3517 uses different metric in lost marker => reset on change */
817         if (tcp_is_fack(tp))
818                 tp->lost_skb_hint = NULL;
819         tp->rx_opt.sack_ok &= ~TCP_FACK_ENABLED;
820 }
821
822 /* Take a notice that peer is sending D-SACKs */
823 static void tcp_dsack_seen(struct tcp_sock *tp)
824 {
825         tp->rx_opt.sack_ok |= TCP_DSACK_SEEN;
826 }
827
828 static void tcp_update_reordering(struct sock *sk, const int metric,
829                                   const int ts)
830 {
831         struct tcp_sock *tp = tcp_sk(sk);
832         if (metric > tp->reordering) {
833                 int mib_idx;
834
835                 tp->reordering = min(TCP_MAX_REORDERING, metric);
836
837                 /* This exciting event is worth to be remembered. 8) */
838                 if (ts)
839                         mib_idx = LINUX_MIB_TCPTSREORDER;
840                 else if (tcp_is_reno(tp))
841                         mib_idx = LINUX_MIB_TCPRENOREORDER;
842                 else if (tcp_is_fack(tp))
843                         mib_idx = LINUX_MIB_TCPFACKREORDER;
844                 else
845                         mib_idx = LINUX_MIB_TCPSACKREORDER;
846
847                 NET_INC_STATS_BH(sock_net(sk), mib_idx);
848 #if FASTRETRANS_DEBUG > 1
849                 pr_debug("Disorder%d %d %u f%u s%u rr%d\n",
850                          tp->rx_opt.sack_ok, inet_csk(sk)->icsk_ca_state,
851                          tp->reordering,
852                          tp->fackets_out,
853                          tp->sacked_out,
854                          tp->undo_marker ? tp->undo_retrans : 0);
855 #endif
856                 tcp_disable_fack(tp);
857         }
858
859         if (metric > 0)
860                 tcp_disable_early_retrans(tp);
861 }
862
863 /* This must be called before lost_out is incremented */
864 static void tcp_verify_retransmit_hint(struct tcp_sock *tp, struct sk_buff *skb)
865 {
866         if ((tp->retransmit_skb_hint == NULL) ||
867             before(TCP_SKB_CB(skb)->seq,
868                    TCP_SKB_CB(tp->retransmit_skb_hint)->seq))
869                 tp->retransmit_skb_hint = skb;
870
871         if (!tp->lost_out ||
872             after(TCP_SKB_CB(skb)->end_seq, tp->retransmit_high))
873                 tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;
874 }
875
876 static void tcp_skb_mark_lost(struct tcp_sock *tp, struct sk_buff *skb)
877 {
878         if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
879                 tcp_verify_retransmit_hint(tp, skb);
880
881                 tp->lost_out += tcp_skb_pcount(skb);
882                 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
883         }
884 }
885
886 static void tcp_skb_mark_lost_uncond_verify(struct tcp_sock *tp,
887                                             struct sk_buff *skb)
888 {
889         tcp_verify_retransmit_hint(tp, skb);
890
891         if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
892                 tp->lost_out += tcp_skb_pcount(skb);
893                 TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
894         }
895 }
896
897 /* This procedure tags the retransmission queue when SACKs arrive.
898  *
899  * We have three tag bits: SACKED(S), RETRANS(R) and LOST(L).
900  * Packets in queue with these bits set are counted in variables
901  * sacked_out, retrans_out and lost_out, correspondingly.
902  *
903  * Valid combinations are:
904  * Tag  InFlight        Description
905  * 0    1               - orig segment is in flight.
906  * S    0               - nothing flies, orig reached receiver.
907  * L    0               - nothing flies, orig lost by net.
908  * R    2               - both orig and retransmit are in flight.
909  * L|R  1               - orig is lost, retransmit is in flight.
910  * S|R  1               - orig reached receiver, retrans is still in flight.
911  * (L|S|R is logically valid, it could occur when L|R is sacked,
912  *  but it is equivalent to plain S and code short-curcuits it to S.
913  *  L|S is logically invalid, it would mean -1 packet in flight 8))
914  *
915  * These 6 states form finite state machine, controlled by the following events:
916  * 1. New ACK (+SACK) arrives. (tcp_sacktag_write_queue())
917  * 2. Retransmission. (tcp_retransmit_skb(), tcp_xmit_retransmit_queue())
918  * 3. Loss detection event of two flavors:
919  *      A. Scoreboard estimator decided the packet is lost.
920  *         A'. Reno "three dupacks" marks head of queue lost.
921  *         A''. Its FACK modification, head until snd.fack is lost.
922  *      B. SACK arrives sacking SND.NXT at the moment, when the
923  *         segment was retransmitted.
924  * 4. D-SACK added new rule: D-SACK changes any tag to S.
925  *
926  * It is pleasant to note, that state diagram turns out to be commutative,
927  * so that we are allowed not to be bothered by order of our actions,
928  * when multiple events arrive simultaneously. (see the function below).
929  *
930  * Reordering detection.
931  * --------------------
932  * Reordering metric is maximal distance, which a packet can be displaced
933  * in packet stream. With SACKs we can estimate it:
934  *
935  * 1. SACK fills old hole and the corresponding segment was not
936  *    ever retransmitted -> reordering. Alas, we cannot use it
937  *    when segment was retransmitted.
938  * 2. The last flaw is solved with D-SACK. D-SACK arrives
939  *    for retransmitted and already SACKed segment -> reordering..
940  * Both of these heuristics are not used in Loss state, when we cannot
941  * account for retransmits accurately.
942  *
943  * SACK block validation.
944  * ----------------------
945  *
946  * SACK block range validation checks that the received SACK block fits to
947  * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT.
948  * Note that SND.UNA is not included to the range though being valid because
949  * it means that the receiver is rather inconsistent with itself reporting
950  * SACK reneging when it should advance SND.UNA. Such SACK block this is
951  * perfectly valid, however, in light of RFC2018 which explicitly states
952  * that "SACK block MUST reflect the newest segment.  Even if the newest
953  * segment is going to be discarded ...", not that it looks very clever
954  * in case of head skb. Due to potentional receiver driven attacks, we
955  * choose to avoid immediate execution of a walk in write queue due to
956  * reneging and defer head skb's loss recovery to standard loss recovery
957  * procedure that will eventually trigger (nothing forbids us doing this).
958  *
959  * Implements also blockage to start_seq wrap-around. Problem lies in the
960  * fact that though start_seq (s) is before end_seq (i.e., not reversed),
961  * there's no guarantee that it will be before snd_nxt (n). The problem
962  * happens when start_seq resides between end_seq wrap (e_w) and snd_nxt
963  * wrap (s_w):
964  *
965  *         <- outs wnd ->                          <- wrapzone ->
966  *         u     e      n                         u_w   e_w  s n_w
967  *         |     |      |                          |     |   |  |
968  * |<------------+------+----- TCP seqno space --------------+---------->|
969  * ...-- <2^31 ->|                                           |<--------...
970  * ...---- >2^31 ------>|                                    |<--------...
971  *
972  * Current code wouldn't be vulnerable but it's better still to discard such
973  * crazy SACK blocks. Doing this check for start_seq alone closes somewhat
974  * similar case (end_seq after snd_nxt wrap) as earlier reversed check in
975  * snd_nxt wrap -> snd_una region will then become "well defined", i.e.,
976  * equal to the ideal case (infinite seqno space without wrap caused issues).
977  *
978  * With D-SACK the lower bound is extended to cover sequence space below
979  * SND.UNA down to undo_marker, which is the last point of interest. Yet
980  * again, D-SACK block must not to go across snd_una (for the same reason as
981  * for the normal SACK blocks, explained above). But there all simplicity
982  * ends, TCP might receive valid D-SACKs below that. As long as they reside
983  * fully below undo_marker they do not affect behavior in anyway and can
984  * therefore be safely ignored. In rare cases (which are more or less
985  * theoretical ones), the D-SACK will nicely cross that boundary due to skb
986  * fragmentation and packet reordering past skb's retransmission. To consider
987  * them correctly, the acceptable range must be extended even more though
988  * the exact amount is rather hard to quantify. However, tp->max_window can
989  * be used as an exaggerated estimate.
990  */
991 static bool tcp_is_sackblock_valid(struct tcp_sock *tp, bool is_dsack,
992                                    u32 start_seq, u32 end_seq)
993 {
994         /* Too far in future, or reversed (interpretation is ambiguous) */
995         if (after(end_seq, tp->snd_nxt) || !before(start_seq, end_seq))
996                 return false;
997
998         /* Nasty start_seq wrap-around check (see comments above) */
999         if (!before(start_seq, tp->snd_nxt))
1000                 return false;
1001
1002         /* In outstanding window? ...This is valid exit for D-SACKs too.
1003          * start_seq == snd_una is non-sensical (see comments above)
1004          */
1005         if (after(start_seq, tp->snd_una))
1006                 return true;
1007
1008         if (!is_dsack || !tp->undo_marker)
1009                 return false;
1010
1011         /* ...Then it's D-SACK, and must reside below snd_una completely */
1012         if (after(end_seq, tp->snd_una))
1013                 return false;
1014
1015         if (!before(start_seq, tp->undo_marker))
1016                 return true;
1017
1018         /* Too old */
1019         if (!after(end_seq, tp->undo_marker))
1020                 return false;
1021
1022         /* Undo_marker boundary crossing (overestimates a lot). Known already:
1023          *   start_seq < undo_marker and end_seq >= undo_marker.
1024          */
1025         return !before(start_seq, end_seq - tp->max_window);
1026 }
1027
1028 /* Check for lost retransmit. This superb idea is borrowed from "ratehalving".
1029  * Event "B". Later note: FACK people cheated me again 8), we have to account
1030  * for reordering! Ugly, but should help.
1031  *
1032  * Search retransmitted skbs from write_queue that were sent when snd_nxt was
1033  * less than what is now known to be received by the other end (derived from
1034  * highest SACK block). Also calculate the lowest snd_nxt among the remaining
1035  * retransmitted skbs to avoid some costly processing per ACKs.
1036  */
1037 static void tcp_mark_lost_retrans(struct sock *sk)
1038 {
1039         const struct inet_connection_sock *icsk = inet_csk(sk);
1040         struct tcp_sock *tp = tcp_sk(sk);
1041         struct sk_buff *skb;
1042         int cnt = 0;
1043         u32 new_low_seq = tp->snd_nxt;
1044         u32 received_upto = tcp_highest_sack_seq(tp);
1045
1046         if (!tcp_is_fack(tp) || !tp->retrans_out ||
1047             !after(received_upto, tp->lost_retrans_low) ||
1048             icsk->icsk_ca_state != TCP_CA_Recovery)
1049                 return;
1050
1051         tcp_for_write_queue(skb, sk) {
1052                 u32 ack_seq = TCP_SKB_CB(skb)->ack_seq;
1053
1054                 if (skb == tcp_send_head(sk))
1055                         break;
1056                 if (cnt == tp->retrans_out)
1057                         break;
1058                 if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
1059                         continue;
1060
1061                 if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS))
1062                         continue;
1063
1064                 /* TODO: We would like to get rid of tcp_is_fack(tp) only
1065                  * constraint here (see above) but figuring out that at
1066                  * least tp->reordering SACK blocks reside between ack_seq
1067                  * and received_upto is not easy task to do cheaply with
1068                  * the available datastructures.
1069                  *
1070                  * Whether FACK should check here for tp->reordering segs
1071                  * in-between one could argue for either way (it would be
1072                  * rather simple to implement as we could count fack_count
1073                  * during the walk and do tp->fackets_out - fack_count).
1074                  */
1075                 if (after(received_upto, ack_seq)) {
1076                         TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
1077                         tp->retrans_out -= tcp_skb_pcount(skb);
1078
1079                         tcp_skb_mark_lost_uncond_verify(tp, skb);
1080                         NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSTRETRANSMIT);
1081                 } else {
1082                         if (before(ack_seq, new_low_seq))
1083                                 new_low_seq = ack_seq;
1084                         cnt += tcp_skb_pcount(skb);
1085                 }
1086         }
1087
1088         if (tp->retrans_out)
1089                 tp->lost_retrans_low = new_low_seq;
1090 }
1091
1092 static bool tcp_check_dsack(struct sock *sk, const struct sk_buff *ack_skb,
1093                             struct tcp_sack_block_wire *sp, int num_sacks,
1094                             u32 prior_snd_una)
1095 {
1096         struct tcp_sock *tp = tcp_sk(sk);
1097         u32 start_seq_0 = get_unaligned_be32(&sp[0].start_seq);
1098         u32 end_seq_0 = get_unaligned_be32(&sp[0].end_seq);
1099         bool dup_sack = false;
1100
1101         if (before(start_seq_0, TCP_SKB_CB(ack_skb)->ack_seq)) {
1102                 dup_sack = true;
1103                 tcp_dsack_seen(tp);
1104                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKRECV);
1105         } else if (num_sacks > 1) {
1106                 u32 end_seq_1 = get_unaligned_be32(&sp[1].end_seq);
1107                 u32 start_seq_1 = get_unaligned_be32(&sp[1].start_seq);
1108
1109                 if (!after(end_seq_0, end_seq_1) &&
1110                     !before(start_seq_0, start_seq_1)) {
1111                         dup_sack = true;
1112                         tcp_dsack_seen(tp);
1113                         NET_INC_STATS_BH(sock_net(sk),
1114                                         LINUX_MIB_TCPDSACKOFORECV);
1115                 }
1116         }
1117
1118         /* D-SACK for already forgotten data... Do dumb counting. */
1119         if (dup_sack && tp->undo_marker && tp->undo_retrans > 0 &&
1120             !after(end_seq_0, prior_snd_una) &&
1121             after(end_seq_0, tp->undo_marker))
1122                 tp->undo_retrans--;
1123
1124         return dup_sack;
1125 }
1126
1127 struct tcp_sacktag_state {
1128         int     reord;
1129         int     fack_count;
1130         long    rtt_us; /* RTT measured by SACKing never-retransmitted data */
1131         int     flag;
1132 };
1133
1134 /* Check if skb is fully within the SACK block. In presence of GSO skbs,
1135  * the incoming SACK may not exactly match but we can find smaller MSS
1136  * aligned portion of it that matches. Therefore we might need to fragment
1137  * which may fail and creates some hassle (caller must handle error case
1138  * returns).
1139  *
1140  * FIXME: this could be merged to shift decision code
1141  */
1142 static int tcp_match_skb_to_sack(struct sock *sk, struct sk_buff *skb,
1143                                   u32 start_seq, u32 end_seq)
1144 {
1145         int err;
1146         bool in_sack;
1147         unsigned int pkt_len;
1148         unsigned int mss;
1149
1150         in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
1151                   !before(end_seq, TCP_SKB_CB(skb)->end_seq);
1152
1153         if (tcp_skb_pcount(skb) > 1 && !in_sack &&
1154             after(TCP_SKB_CB(skb)->end_seq, start_seq)) {
1155                 mss = tcp_skb_mss(skb);
1156                 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
1157
1158                 if (!in_sack) {
1159                         pkt_len = start_seq - TCP_SKB_CB(skb)->seq;
1160                         if (pkt_len < mss)
1161                                 pkt_len = mss;
1162                 } else {
1163                         pkt_len = end_seq - TCP_SKB_CB(skb)->seq;
1164                         if (pkt_len < mss)
1165                                 return -EINVAL;
1166                 }
1167
1168                 /* Round if necessary so that SACKs cover only full MSSes
1169                  * and/or the remaining small portion (if present)
1170                  */
1171                 if (pkt_len > mss) {
1172                         unsigned int new_len = (pkt_len / mss) * mss;
1173                         if (!in_sack && new_len < pkt_len) {
1174                                 new_len += mss;
1175                                 if (new_len >= skb->len)
1176                                         return 0;
1177                         }
1178                         pkt_len = new_len;
1179                 }
1180                 err = tcp_fragment(sk, skb, pkt_len, mss, GFP_ATOMIC);
1181                 if (err < 0)
1182                         return err;
1183         }
1184
1185         return in_sack;
1186 }
1187
1188 /* Mark the given newly-SACKed range as such, adjusting counters and hints. */
1189 static u8 tcp_sacktag_one(struct sock *sk,
1190                           struct tcp_sacktag_state *state, u8 sacked,
1191                           u32 start_seq, u32 end_seq,
1192                           int dup_sack, int pcount,
1193                           const struct skb_mstamp *xmit_time)
1194 {
1195         struct tcp_sock *tp = tcp_sk(sk);
1196         int fack_count = state->fack_count;
1197
1198         /* Account D-SACK for retransmitted packet. */
1199         if (dup_sack && (sacked & TCPCB_RETRANS)) {
1200                 if (tp->undo_marker && tp->undo_retrans > 0 &&
1201                     after(end_seq, tp->undo_marker))
1202                         tp->undo_retrans--;
1203                 if (sacked & TCPCB_SACKED_ACKED)
1204                         state->reord = min(fack_count, state->reord);
1205         }
1206
1207         /* Nothing to do; acked frame is about to be dropped (was ACKed). */
1208         if (!after(end_seq, tp->snd_una))
1209                 return sacked;
1210
1211         if (!(sacked & TCPCB_SACKED_ACKED)) {
1212                 if (sacked & TCPCB_SACKED_RETRANS) {
1213                         /* If the segment is not tagged as lost,
1214                          * we do not clear RETRANS, believing
1215                          * that retransmission is still in flight.
1216                          */
1217                         if (sacked & TCPCB_LOST) {
1218                                 sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
1219                                 tp->lost_out -= pcount;
1220                                 tp->retrans_out -= pcount;
1221                         }
1222                 } else {
1223                         if (!(sacked & TCPCB_RETRANS)) {
1224                                 /* New sack for not retransmitted frame,
1225                                  * which was in hole. It is reordering.
1226                                  */
1227                                 if (before(start_seq,
1228                                            tcp_highest_sack_seq(tp)))
1229                                         state->reord = min(fack_count,
1230                                                            state->reord);
1231                                 if (!after(end_seq, tp->high_seq))
1232                                         state->flag |= FLAG_ORIG_SACK_ACKED;
1233                                 /* Pick the earliest sequence sacked for RTT */
1234                                 if (state->rtt_us < 0) {
1235                                         struct skb_mstamp now;
1236
1237                                         skb_mstamp_get(&now);
1238                                         state->rtt_us = skb_mstamp_us_delta(&now,
1239                                                                 xmit_time);
1240                                 }
1241                         }
1242
1243                         if (sacked & TCPCB_LOST) {
1244                                 sacked &= ~TCPCB_LOST;
1245                                 tp->lost_out -= pcount;
1246                         }
1247                 }
1248
1249                 sacked |= TCPCB_SACKED_ACKED;
1250                 state->flag |= FLAG_DATA_SACKED;
1251                 tp->sacked_out += pcount;
1252
1253                 fack_count += pcount;
1254
1255                 /* Lost marker hint past SACKed? Tweak RFC3517 cnt */
1256                 if (!tcp_is_fack(tp) && (tp->lost_skb_hint != NULL) &&
1257                     before(start_seq, TCP_SKB_CB(tp->lost_skb_hint)->seq))
1258                         tp->lost_cnt_hint += pcount;
1259
1260                 if (fack_count > tp->fackets_out)
1261                         tp->fackets_out = fack_count;
1262         }
1263
1264         /* D-SACK. We can detect redundant retransmission in S|R and plain R
1265          * frames and clear it. undo_retrans is decreased above, L|R frames
1266          * are accounted above as well.
1267          */
1268         if (dup_sack && (sacked & TCPCB_SACKED_RETRANS)) {
1269                 sacked &= ~TCPCB_SACKED_RETRANS;
1270                 tp->retrans_out -= pcount;
1271         }
1272
1273         return sacked;
1274 }
1275
1276 /* Shift newly-SACKed bytes from this skb to the immediately previous
1277  * already-SACKed sk_buff. Mark the newly-SACKed bytes as such.
1278  */
1279 static bool tcp_shifted_skb(struct sock *sk, struct sk_buff *skb,
1280                             struct tcp_sacktag_state *state,
1281                             unsigned int pcount, int shifted, int mss,
1282                             bool dup_sack)
1283 {
1284         struct tcp_sock *tp = tcp_sk(sk);
1285         struct sk_buff *prev = tcp_write_queue_prev(sk, skb);
1286         u32 start_seq = TCP_SKB_CB(skb)->seq;   /* start of newly-SACKed */
1287         u32 end_seq = start_seq + shifted;      /* end of newly-SACKed */
1288
1289         BUG_ON(!pcount);
1290
1291         /* Adjust counters and hints for the newly sacked sequence
1292          * range but discard the return value since prev is already
1293          * marked. We must tag the range first because the seq
1294          * advancement below implicitly advances
1295          * tcp_highest_sack_seq() when skb is highest_sack.
1296          */
1297         tcp_sacktag_one(sk, state, TCP_SKB_CB(skb)->sacked,
1298                         start_seq, end_seq, dup_sack, pcount,
1299                         &skb->skb_mstamp);
1300
1301         if (skb == tp->lost_skb_hint)
1302                 tp->lost_cnt_hint += pcount;
1303
1304         TCP_SKB_CB(prev)->end_seq += shifted;
1305         TCP_SKB_CB(skb)->seq += shifted;
1306
1307         tcp_skb_pcount_add(prev, pcount);
1308         BUG_ON(tcp_skb_pcount(skb) < pcount);
1309         tcp_skb_pcount_add(skb, -pcount);
1310
1311         /* When we're adding to gso_segs == 1, gso_size will be zero,
1312          * in theory this shouldn't be necessary but as long as DSACK
1313          * code can come after this skb later on it's better to keep
1314          * setting gso_size to something.
1315          */
1316         if (!skb_shinfo(prev)->gso_size) {
1317                 skb_shinfo(prev)->gso_size = mss;
1318                 skb_shinfo(prev)->gso_type = sk->sk_gso_type;
1319         }
1320
1321         /* CHECKME: To clear or not to clear? Mimics normal skb currently */
1322         if (tcp_skb_pcount(skb) <= 1) {
1323                 skb_shinfo(skb)->gso_size = 0;
1324                 skb_shinfo(skb)->gso_type = 0;
1325         }
1326
1327         /* Difference in this won't matter, both ACKed by the same cumul. ACK */
1328         TCP_SKB_CB(prev)->sacked |= (TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS);
1329
1330         if (skb->len > 0) {
1331                 BUG_ON(!tcp_skb_pcount(skb));
1332                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTED);
1333                 return false;
1334         }
1335
1336         /* Whole SKB was eaten :-) */
1337
1338         if (skb == tp->retransmit_skb_hint)
1339                 tp->retransmit_skb_hint = prev;
1340         if (skb == tp->lost_skb_hint) {
1341                 tp->lost_skb_hint = prev;
1342                 tp->lost_cnt_hint -= tcp_skb_pcount(prev);
1343         }
1344
1345         TCP_SKB_CB(prev)->tcp_flags |= TCP_SKB_CB(skb)->tcp_flags;
1346         if (TCP_SKB_CB(skb)->tcp_flags & TCPHDR_FIN)
1347                 TCP_SKB_CB(prev)->end_seq++;
1348
1349         if (skb == tcp_highest_sack(sk))
1350                 tcp_advance_highest_sack(sk, skb);
1351
1352         tcp_unlink_write_queue(skb, sk);
1353         sk_wmem_free_skb(sk, skb);
1354
1355         NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKMERGED);
1356
1357         return true;
1358 }
1359
1360 /* I wish gso_size would have a bit more sane initialization than
1361  * something-or-zero which complicates things
1362  */
1363 static int tcp_skb_seglen(const struct sk_buff *skb)
1364 {
1365         return tcp_skb_pcount(skb) == 1 ? skb->len : tcp_skb_mss(skb);
1366 }
1367
1368 /* Shifting pages past head area doesn't work */
1369 static int skb_can_shift(const struct sk_buff *skb)
1370 {
1371         return !skb_headlen(skb) && skb_is_nonlinear(skb);
1372 }
1373
1374 /* Try collapsing SACK blocks spanning across multiple skbs to a single
1375  * skb.
1376  */
1377 static struct sk_buff *tcp_shift_skb_data(struct sock *sk, struct sk_buff *skb,
1378                                           struct tcp_sacktag_state *state,
1379                                           u32 start_seq, u32 end_seq,
1380                                           bool dup_sack)
1381 {
1382         struct tcp_sock *tp = tcp_sk(sk);
1383         struct sk_buff *prev;
1384         int mss;
1385         int pcount = 0;
1386         int len;
1387         int in_sack;
1388
1389         if (!sk_can_gso(sk))
1390                 goto fallback;
1391
1392         /* Normally R but no L won't result in plain S */
1393         if (!dup_sack &&
1394             (TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_RETRANS)) == TCPCB_SACKED_RETRANS)
1395                 goto fallback;
1396         if (!skb_can_shift(skb))
1397                 goto fallback;
1398         /* This frame is about to be dropped (was ACKed). */
1399         if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
1400                 goto fallback;
1401
1402         /* Can only happen with delayed DSACK + discard craziness */
1403         if (unlikely(skb == tcp_write_queue_head(sk)))
1404                 goto fallback;
1405         prev = tcp_write_queue_prev(sk, skb);
1406
1407         if ((TCP_SKB_CB(prev)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED)
1408                 goto fallback;
1409
1410         in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
1411                   !before(end_seq, TCP_SKB_CB(skb)->end_seq);
1412
1413         if (in_sack) {
1414                 len = skb->len;
1415                 pcount = tcp_skb_pcount(skb);
1416                 mss = tcp_skb_seglen(skb);
1417
1418                 /* TODO: Fix DSACKs to not fragment already SACKed and we can
1419                  * drop this restriction as unnecessary
1420                  */
1421                 if (mss != tcp_skb_seglen(prev))
1422                         goto fallback;
1423         } else {
1424                 if (!after(TCP_SKB_CB(skb)->end_seq, start_seq))
1425                         goto noop;
1426                 /* CHECKME: This is non-MSS split case only?, this will
1427                  * cause skipped skbs due to advancing loop btw, original
1428                  * has that feature too
1429                  */
1430                 if (tcp_skb_pcount(skb) <= 1)
1431                         goto noop;
1432
1433                 in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
1434                 if (!in_sack) {
1435                         /* TODO: head merge to next could be attempted here
1436                          * if (!after(TCP_SKB_CB(skb)->end_seq, end_seq)),
1437                          * though it might not be worth of the additional hassle
1438                          *
1439                          * ...we can probably just fallback to what was done
1440                          * previously. We could try merging non-SACKed ones
1441                          * as well but it probably isn't going to buy off
1442                          * because later SACKs might again split them, and
1443                          * it would make skb timestamp tracking considerably
1444                          * harder problem.
1445                          */
1446                         goto fallback;
1447                 }
1448
1449                 len = end_seq - TCP_SKB_CB(skb)->seq;
1450                 BUG_ON(len < 0);
1451                 BUG_ON(len > skb->len);
1452
1453                 /* MSS boundaries should be honoured or else pcount will
1454                  * severely break even though it makes things bit trickier.
1455                  * Optimize common case to avoid most of the divides
1456                  */
1457                 mss = tcp_skb_mss(skb);
1458
1459                 /* TODO: Fix DSACKs to not fragment already SACKed and we can
1460                  * drop this restriction as unnecessary
1461                  */
1462                 if (mss != tcp_skb_seglen(prev))
1463                         goto fallback;
1464
1465                 if (len == mss) {
1466                         pcount = 1;
1467                 } else if (len < mss) {
1468                         goto noop;
1469                 } else {
1470                         pcount = len / mss;
1471                         len = pcount * mss;
1472                 }
1473         }
1474
1475         /* tcp_sacktag_one() won't SACK-tag ranges below snd_una */
1476         if (!after(TCP_SKB_CB(skb)->seq + len, tp->snd_una))
1477                 goto fallback;
1478
1479         if (!skb_shift(prev, skb, len))
1480                 goto fallback;
1481         if (!tcp_shifted_skb(sk, skb, state, pcount, len, mss, dup_sack))
1482                 goto out;
1483
1484         /* Hole filled allows collapsing with the next as well, this is very
1485          * useful when hole on every nth skb pattern happens
1486          */
1487         if (prev == tcp_write_queue_tail(sk))
1488                 goto out;
1489         skb = tcp_write_queue_next(sk, prev);
1490
1491         if (!skb_can_shift(skb) ||
1492             (skb == tcp_send_head(sk)) ||
1493             ((TCP_SKB_CB(skb)->sacked & TCPCB_TAGBITS) != TCPCB_SACKED_ACKED) ||
1494             (mss != tcp_skb_seglen(skb)))
1495                 goto out;
1496
1497         len = skb->len;
1498         if (skb_shift(prev, skb, len)) {
1499                 pcount += tcp_skb_pcount(skb);
1500                 tcp_shifted_skb(sk, skb, state, tcp_skb_pcount(skb), len, mss, 0);
1501         }
1502
1503 out:
1504         state->fack_count += pcount;
1505         return prev;
1506
1507 noop:
1508         return skb;
1509
1510 fallback:
1511         NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_SACKSHIFTFALLBACK);
1512         return NULL;
1513 }
1514
1515 static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk,
1516                                         struct tcp_sack_block *next_dup,
1517                                         struct tcp_sacktag_state *state,
1518                                         u32 start_seq, u32 end_seq,
1519                                         bool dup_sack_in)
1520 {
1521         struct tcp_sock *tp = tcp_sk(sk);
1522         struct sk_buff *tmp;
1523
1524         tcp_for_write_queue_from(skb, sk) {
1525                 int in_sack = 0;
1526                 bool dup_sack = dup_sack_in;
1527
1528                 if (skb == tcp_send_head(sk))
1529                         break;
1530
1531                 /* queue is in-order => we can short-circuit the walk early */
1532                 if (!before(TCP_SKB_CB(skb)->seq, end_seq))
1533                         break;
1534
1535                 if ((next_dup != NULL) &&
1536                     before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) {
1537                         in_sack = tcp_match_skb_to_sack(sk, skb,
1538                                                         next_dup->start_seq,
1539                                                         next_dup->end_seq);
1540                         if (in_sack > 0)
1541                                 dup_sack = true;
1542                 }
1543
1544                 /* skb reference here is a bit tricky to get right, since
1545                  * shifting can eat and free both this skb and the next,
1546                  * so not even _safe variant of the loop is enough.
1547                  */
1548                 if (in_sack <= 0) {
1549                         tmp = tcp_shift_skb_data(sk, skb, state,
1550                                                  start_seq, end_seq, dup_sack);
1551                         if (tmp != NULL) {
1552                                 if (tmp != skb) {
1553                                         skb = tmp;
1554                                         continue;
1555                                 }
1556
1557                                 in_sack = 0;
1558                         } else {
1559                                 in_sack = tcp_match_skb_to_sack(sk, skb,
1560                                                                 start_seq,
1561                                                                 end_seq);
1562                         }
1563                 }
1564
1565                 if (unlikely(in_sack < 0))
1566                         break;
1567
1568                 if (in_sack) {
1569                         TCP_SKB_CB(skb)->sacked =
1570                                 tcp_sacktag_one(sk,
1571                                                 state,
1572                                                 TCP_SKB_CB(skb)->sacked,
1573                                                 TCP_SKB_CB(skb)->seq,
1574                                                 TCP_SKB_CB(skb)->end_seq,
1575                                                 dup_sack,
1576                                                 tcp_skb_pcount(skb),
1577                                                 &skb->skb_mstamp);
1578
1579                         if (!before(TCP_SKB_CB(skb)->seq,
1580                                     tcp_highest_sack_seq(tp)))
1581                                 tcp_advance_highest_sack(sk, skb);
1582                 }
1583
1584                 state->fack_count += tcp_skb_pcount(skb);
1585         }
1586         return skb;
1587 }
1588
1589 /* Avoid all extra work that is being done by sacktag while walking in
1590  * a normal way
1591  */
1592 static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk,
1593                                         struct tcp_sacktag_state *state,
1594                                         u32 skip_to_seq)
1595 {
1596         tcp_for_write_queue_from(skb, sk) {
1597                 if (skb == tcp_send_head(sk))
1598                         break;
1599
1600                 if (after(TCP_SKB_CB(skb)->end_seq, skip_to_seq))
1601                         break;
1602
1603                 state->fack_count += tcp_skb_pcount(skb);
1604         }
1605         return skb;
1606 }
1607
1608 static struct sk_buff *tcp_maybe_skipping_dsack(struct sk_buff *skb,
1609                                                 struct sock *sk,
1610                                                 struct tcp_sack_block *next_dup,
1611                                                 struct tcp_sacktag_state *state,
1612                                                 u32 skip_to_seq)
1613 {
1614         if (next_dup == NULL)
1615                 return skb;
1616
1617         if (before(next_dup->start_seq, skip_to_seq)) {
1618                 skb = tcp_sacktag_skip(skb, sk, state, next_dup->start_seq);
1619                 skb = tcp_sacktag_walk(skb, sk, NULL, state,
1620                                        next_dup->start_seq, next_dup->end_seq,
1621                                        1);
1622         }
1623
1624         return skb;
1625 }
1626
1627 static int tcp_sack_cache_ok(const struct tcp_sock *tp, const struct tcp_sack_block *cache)
1628 {
1629         return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
1630 }
1631
1632 static int
1633 tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb,
1634                         u32 prior_snd_una, long *sack_rtt_us)
1635 {
1636         struct tcp_sock *tp = tcp_sk(sk);
1637         const unsigned char *ptr = (skb_transport_header(ack_skb) +
1638                                     TCP_SKB_CB(ack_skb)->sacked);
1639         struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2);
1640         struct tcp_sack_block sp[TCP_NUM_SACKS];
1641         struct tcp_sack_block *cache;
1642         struct tcp_sacktag_state state;
1643         struct sk_buff *skb;
1644         int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3);
1645         int used_sacks;
1646         bool found_dup_sack = false;
1647         int i, j;
1648         int first_sack_index;
1649
1650         state.flag = 0;
1651         state.reord = tp->packets_out;
1652         state.rtt_us = -1L;
1653
1654         if (!tp->sacked_out) {
1655                 if (WARN_ON(tp->fackets_out))
1656                         tp->fackets_out = 0;
1657                 tcp_highest_sack_reset(sk);
1658         }
1659
1660         found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire,
1661                                          num_sacks, prior_snd_una);
1662         if (found_dup_sack)
1663                 state.flag |= FLAG_DSACKING_ACK;
1664
1665         /* Eliminate too old ACKs, but take into
1666          * account more or less fresh ones, they can
1667          * contain valid SACK info.
1668          */
1669         if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
1670                 return 0;
1671
1672         if (!tp->packets_out)
1673                 goto out;
1674
1675         used_sacks = 0;
1676         first_sack_index = 0;
1677         for (i = 0; i < num_sacks; i++) {
1678                 bool dup_sack = !i && found_dup_sack;
1679
1680                 sp[used_sacks].start_seq = get_unaligned_be32(&sp_wire[i].start_seq);
1681                 sp[used_sacks].end_seq = get_unaligned_be32(&sp_wire[i].end_seq);
1682
1683                 if (!tcp_is_sackblock_valid(tp, dup_sack,
1684                                             sp[used_sacks].start_seq,
1685                                             sp[used_sacks].end_seq)) {
1686                         int mib_idx;
1687
1688                         if (dup_sack) {
1689                                 if (!tp->undo_marker)
1690                                         mib_idx = LINUX_MIB_TCPDSACKIGNOREDNOUNDO;
1691                                 else
1692                                         mib_idx = LINUX_MIB_TCPDSACKIGNOREDOLD;
1693                         } else {
1694                                 /* Don't count olds caused by ACK reordering */
1695                                 if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) &&
1696                                     !after(sp[used_sacks].end_seq, tp->snd_una))
1697                                         continue;
1698                                 mib_idx = LINUX_MIB_TCPSACKDISCARD;
1699                         }
1700
1701                         NET_INC_STATS_BH(sock_net(sk), mib_idx);
1702                         if (i == 0)
1703                                 first_sack_index = -1;
1704                         continue;
1705                 }
1706
1707                 /* Ignore very old stuff early */
1708                 if (!after(sp[used_sacks].end_seq, prior_snd_una))
1709                         continue;
1710
1711                 used_sacks++;
1712         }
1713
1714         /* order SACK blocks to allow in order walk of the retrans queue */
1715         for (i = used_sacks - 1; i > 0; i--) {
1716                 for (j = 0; j < i; j++) {
1717                         if (after(sp[j].start_seq, sp[j + 1].start_seq)) {
1718                                 swap(sp[j], sp[j + 1]);
1719
1720                                 /* Track where the first SACK block goes to */
1721                                 if (j == first_sack_index)
1722                                         first_sack_index = j + 1;
1723                         }
1724                 }
1725         }
1726
1727         skb = tcp_write_queue_head(sk);
1728         state.fack_count = 0;
1729         i = 0;
1730
1731         if (!tp->sacked_out) {
1732                 /* It's already past, so skip checking against it */
1733                 cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
1734         } else {
1735                 cache = tp->recv_sack_cache;
1736                 /* Skip empty blocks in at head of the cache */
1737                 while (tcp_sack_cache_ok(tp, cache) && !cache->start_seq &&
1738                        !cache->end_seq)
1739                         cache++;
1740         }
1741
1742         while (i < used_sacks) {
1743                 u32 start_seq = sp[i].start_seq;
1744                 u32 end_seq = sp[i].end_seq;
1745                 bool dup_sack = (found_dup_sack && (i == first_sack_index));
1746                 struct tcp_sack_block *next_dup = NULL;
1747
1748                 if (found_dup_sack && ((i + 1) == first_sack_index))
1749                         next_dup = &sp[i + 1];
1750
1751                 /* Skip too early cached blocks */
1752                 while (tcp_sack_cache_ok(tp, cache) &&
1753                        !before(start_seq, cache->end_seq))
1754                         cache++;
1755
1756                 /* Can skip some work by looking recv_sack_cache? */
1757                 if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
1758                     after(end_seq, cache->start_seq)) {
1759
1760                         /* Head todo? */
1761                         if (before(start_seq, cache->start_seq)) {
1762                                 skb = tcp_sacktag_skip(skb, sk, &state,
1763                                                        start_seq);
1764                                 skb = tcp_sacktag_walk(skb, sk, next_dup,
1765                                                        &state,
1766                                                        start_seq,
1767                                                        cache->start_seq,
1768                                                        dup_sack);
1769                         }
1770
1771                         /* Rest of the block already fully processed? */
1772                         if (!after(end_seq, cache->end_seq))
1773                                 goto advance_sp;
1774
1775                         skb = tcp_maybe_skipping_dsack(skb, sk, next_dup,
1776                                                        &state,
1777                                                        cache->end_seq);
1778
1779                         /* ...tail remains todo... */
1780                         if (tcp_highest_sack_seq(tp) == cache->end_seq) {
1781                                 /* ...but better entrypoint exists! */
1782                                 skb = tcp_highest_sack(sk);
1783                                 if (skb == NULL)
1784                                         break;
1785                                 state.fack_count = tp->fackets_out;
1786                                 cache++;
1787                                 goto walk;
1788                         }
1789
1790                         skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq);
1791                         /* Check overlap against next cached too (past this one already) */
1792                         cache++;
1793                         continue;
1794                 }
1795
1796                 if (!before(start_seq, tcp_highest_sack_seq(tp))) {
1797                         skb = tcp_highest_sack(sk);
1798                         if (skb == NULL)
1799                                 break;
1800                         state.fack_count = tp->fackets_out;
1801                 }
1802                 skb = tcp_sacktag_skip(skb, sk, &state, start_seq);
1803
1804 walk:
1805                 skb = tcp_sacktag_walk(skb, sk, next_dup, &state,
1806                                        start_seq, end_seq, dup_sack);
1807
1808 advance_sp:
1809                 i++;
1810         }
1811
1812         /* Clear the head of the cache sack blocks so we can skip it next time */
1813         for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) {
1814                 tp->recv_sack_cache[i].start_seq = 0;
1815                 tp->recv_sack_cache[i].end_seq = 0;
1816         }
1817         for (j = 0; j < used_sacks; j++)
1818                 tp->recv_sack_cache[i++] = sp[j];
1819
1820         tcp_mark_lost_retrans(sk);
1821
1822         tcp_verify_left_out(tp);
1823
1824         if ((state.reord < tp->fackets_out) &&
1825             ((inet_csk(sk)->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker))
1826                 tcp_update_reordering(sk, tp->fackets_out - state.reord, 0);
1827
1828 out:
1829
1830 #if FASTRETRANS_DEBUG > 0
1831         WARN_ON((int)tp->sacked_out < 0);
1832         WARN_ON((int)tp->lost_out < 0);
1833         WARN_ON((int)tp->retrans_out < 0);
1834         WARN_ON((int)tcp_packets_in_flight(tp) < 0);
1835 #endif
1836         *sack_rtt_us = state.rtt_us;
1837         return state.flag;
1838 }
1839
1840 /* Limits sacked_out so that sum with lost_out isn't ever larger than
1841  * packets_out. Returns false if sacked_out adjustement wasn't necessary.
1842  */
1843 static bool tcp_limit_reno_sacked(struct tcp_sock *tp)
1844 {
1845         u32 holes;
1846
1847         holes = max(tp->lost_out, 1U);
1848         holes = min(holes, tp->packets_out);
1849
1850         if ((tp->sacked_out + holes) > tp->packets_out) {
1851                 tp->sacked_out = tp->packets_out - holes;
1852                 return true;
1853         }
1854         return false;
1855 }
1856
1857 /* If we receive more dupacks than we expected counting segments
1858  * in assumption of absent reordering, interpret this as reordering.
1859  * The only another reason could be bug in receiver TCP.
1860  */
1861 static void tcp_check_reno_reordering(struct sock *sk, const int addend)
1862 {
1863         struct tcp_sock *tp = tcp_sk(sk);
1864         if (tcp_limit_reno_sacked(tp))
1865                 tcp_update_reordering(sk, tp->packets_out + addend, 0);
1866 }
1867
1868 /* Emulate SACKs for SACKless connection: account for a new dupack. */
1869
1870 static void tcp_add_reno_sack(struct sock *sk)
1871 {
1872         struct tcp_sock *tp = tcp_sk(sk);
1873         tp->sacked_out++;
1874         tcp_check_reno_reordering(sk, 0);
1875         tcp_verify_left_out(tp);
1876 }
1877
1878 /* Account for ACK, ACKing some data in Reno Recovery phase. */
1879
1880 static void tcp_remove_reno_sacks(struct sock *sk, int acked)
1881 {
1882         struct tcp_sock *tp = tcp_sk(sk);
1883
1884         if (acked > 0) {
1885                 /* One ACK acked hole. The rest eat duplicate ACKs. */
1886                 if (acked - 1 >= tp->sacked_out)
1887                         tp->sacked_out = 0;
1888                 else
1889                         tp->sacked_out -= acked - 1;
1890         }
1891         tcp_check_reno_reordering(sk, acked);
1892         tcp_verify_left_out(tp);
1893 }
1894
1895 static inline void tcp_reset_reno_sack(struct tcp_sock *tp)
1896 {
1897         tp->sacked_out = 0;
1898 }
1899
1900 void tcp_clear_retrans(struct tcp_sock *tp)
1901 {
1902         tp->retrans_out = 0;
1903         tp->lost_out = 0;
1904         tp->undo_marker = 0;
1905         tp->undo_retrans = -1;
1906         tp->fackets_out = 0;
1907         tp->sacked_out = 0;
1908 }
1909
1910 static inline void tcp_init_undo(struct tcp_sock *tp)
1911 {
1912         tp->undo_marker = tp->snd_una;
1913         /* Retransmission still in flight may cause DSACKs later. */
1914         tp->undo_retrans = tp->retrans_out ? : -1;
1915 }
1916
1917 /* Enter Loss state. If we detect SACK reneging, forget all SACK information
1918  * and reset tags completely, otherwise preserve SACKs. If receiver
1919  * dropped its ofo queue, we will know this due to reneging detection.
1920  */
1921 void tcp_enter_loss(struct sock *sk)
1922 {
1923         const struct inet_connection_sock *icsk = inet_csk(sk);
1924         struct tcp_sock *tp = tcp_sk(sk);
1925         struct sk_buff *skb;
1926         bool new_recovery = false;
1927         bool is_reneg;                  /* is receiver reneging on SACKs? */
1928
1929         /* Reduce ssthresh if it has not yet been made inside this window. */
1930         if (icsk->icsk_ca_state <= TCP_CA_Disorder ||
1931             !after(tp->high_seq, tp->snd_una) ||
1932             (icsk->icsk_ca_state == TCP_CA_Loss && !icsk->icsk_retransmits)) {
1933                 new_recovery = true;
1934                 tp->prior_ssthresh = tcp_current_ssthresh(sk);
1935                 tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
1936                 tcp_ca_event(sk, CA_EVENT_LOSS);
1937                 tcp_init_undo(tp);
1938         }
1939         tp->snd_cwnd       = 1;
1940         tp->snd_cwnd_cnt   = 0;
1941         tp->snd_cwnd_stamp = tcp_time_stamp;
1942
1943         tp->retrans_out = 0;
1944         tp->lost_out = 0;
1945
1946         if (tcp_is_reno(tp))
1947                 tcp_reset_reno_sack(tp);
1948
1949         skb = tcp_write_queue_head(sk);
1950         is_reneg = skb && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED);
1951         if (is_reneg) {
1952                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPSACKRENEGING);
1953                 tp->sacked_out = 0;
1954                 tp->fackets_out = 0;
1955         }
1956         tcp_clear_all_retrans_hints(tp);
1957
1958         tcp_for_write_queue(skb, sk) {
1959                 if (skb == tcp_send_head(sk))
1960                         break;
1961
1962                 TCP_SKB_CB(skb)->sacked &= (~TCPCB_TAGBITS)|TCPCB_SACKED_ACKED;
1963                 if (!(TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_ACKED) || is_reneg) {
1964                         TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_ACKED;
1965                         TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
1966                         tp->lost_out += tcp_skb_pcount(skb);
1967                         tp->retransmit_high = TCP_SKB_CB(skb)->end_seq;
1968                 }
1969         }
1970         tcp_verify_left_out(tp);
1971
1972         /* Timeout in disordered state after receiving substantial DUPACKs
1973          * suggests that the degree of reordering is over-estimated.
1974          */
1975         if (icsk->icsk_ca_state <= TCP_CA_Disorder &&
1976             tp->sacked_out >= sysctl_tcp_reordering)
1977                 tp->reordering = min_t(unsigned int, tp->reordering,
1978                                        sysctl_tcp_reordering);
1979         tcp_set_ca_state(sk, TCP_CA_Loss);
1980         tp->high_seq = tp->snd_nxt;
1981         tcp_ecn_queue_cwr(tp);
1982
1983         /* F-RTO RFC5682 sec 3.1 step 1: retransmit SND.UNA if no previous
1984          * loss recovery is underway except recurring timeout(s) on
1985          * the same SND.UNA (sec 3.2). Disable F-RTO on path MTU probing
1986          */
1987         tp->frto = sysctl_tcp_frto &&
1988                    (new_recovery || icsk->icsk_retransmits) &&
1989                    !inet_csk(sk)->icsk_mtup.probe_size;
1990 }
1991
1992 /* If ACK arrived pointing to a remembered SACK, it means that our
1993  * remembered SACKs do not reflect real state of receiver i.e.
1994  * receiver _host_ is heavily congested (or buggy).
1995  *
1996  * To avoid big spurious retransmission bursts due to transient SACK
1997  * scoreboard oddities that look like reneging, we give the receiver a
1998  * little time (max(RTT/2, 10ms)) to send us some more ACKs that will
1999  * restore sanity to the SACK scoreboard. If the apparent reneging
2000  * persists until this RTO then we'll clear the SACK scoreboard.
2001  */
2002 static bool tcp_check_sack_reneging(struct sock *sk, int flag)
2003 {
2004         if (flag & FLAG_SACK_RENEGING) {
2005                 struct tcp_sock *tp = tcp_sk(sk);
2006                 unsigned long delay = max(usecs_to_jiffies(tp->srtt_us >> 4),
2007                                           msecs_to_jiffies(10));
2008
2009                 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS,
2010                                           delay, TCP_RTO_MAX);
2011                 return true;
2012         }
2013         return false;
2014 }
2015
2016 static inline int tcp_fackets_out(const struct tcp_sock *tp)
2017 {
2018         return tcp_is_reno(tp) ? tp->sacked_out + 1 : tp->fackets_out;
2019 }
2020
2021 /* Heurestics to calculate number of duplicate ACKs. There's no dupACKs
2022  * counter when SACK is enabled (without SACK, sacked_out is used for
2023  * that purpose).
2024  *
2025  * Instead, with FACK TCP uses fackets_out that includes both SACKed
2026  * segments up to the highest received SACK block so far and holes in
2027  * between them.
2028  *
2029  * With reordering, holes may still be in flight, so RFC3517 recovery
2030  * uses pure sacked_out (total number of SACKed segments) even though
2031  * it violates the RFC that uses duplicate ACKs, often these are equal
2032  * but when e.g. out-of-window ACKs or packet duplication occurs,
2033  * they differ. Since neither occurs due to loss, TCP should really
2034  * ignore them.
2035  */
2036 static inline int tcp_dupack_heuristics(const struct tcp_sock *tp)
2037 {
2038         return tcp_is_fack(tp) ? tp->fackets_out : tp->sacked_out + 1;
2039 }
2040
2041 static bool tcp_pause_early_retransmit(struct sock *sk, int flag)
2042 {
2043         struct tcp_sock *tp = tcp_sk(sk);
2044         unsigned long delay;
2045
2046         /* Delay early retransmit and entering fast recovery for
2047          * max(RTT/4, 2msec) unless ack has ECE mark, no RTT samples
2048          * available, or RTO is scheduled to fire first.
2049          */
2050         if (sysctl_tcp_early_retrans < 2 || sysctl_tcp_early_retrans > 3 ||
2051             (flag & FLAG_ECE) || !tp->srtt_us)
2052                 return false;
2053
2054         delay = max(usecs_to_jiffies(tp->srtt_us >> 5),
2055                     msecs_to_jiffies(2));
2056
2057         if (!time_after(inet_csk(sk)->icsk_timeout, (jiffies + delay)))
2058                 return false;
2059
2060         inet_csk_reset_xmit_timer(sk, ICSK_TIME_EARLY_RETRANS, delay,
2061                                   TCP_RTO_MAX);
2062         return true;
2063 }
2064
2065 /* Linux NewReno/SACK/FACK/ECN state machine.
2066  * --------------------------------------
2067  *
2068  * "Open"       Normal state, no dubious events, fast path.
2069  * "Disorder"   In all the respects it is "Open",
2070  *              but requires a bit more attention. It is entered when
2071  *              we see some SACKs or dupacks. It is split of "Open"
2072  *              mainly to move some processing from fast path to slow one.
2073  * "CWR"        CWND was reduced due to some Congestion Notification event.
2074  *              It can be ECN, ICMP source quench, local device congestion.
2075  * "Recovery"   CWND was reduced, we are fast-retransmitting.
2076  * "Loss"       CWND was reduced due to RTO timeout or SACK reneging.
2077  *
2078  * tcp_fastretrans_alert() is entered:
2079  * - each incoming ACK, if state is not "Open"
2080  * - when arrived ACK is unusual, namely:
2081  *      * SACK
2082  *      * Duplicate ACK.
2083  *      * ECN ECE.
2084  *
2085  * Counting packets in flight is pretty simple.
2086  *
2087  *      in_flight = packets_out - left_out + retrans_out
2088  *
2089  *      packets_out is SND.NXT-SND.UNA counted in packets.
2090  *
2091  *      retrans_out is number of retransmitted segments.
2092  *
2093  *      left_out is number of segments left network, but not ACKed yet.
2094  *
2095  *              left_out = sacked_out + lost_out
2096  *
2097  *     sacked_out: Packets, which arrived to receiver out of order
2098  *                 and hence not ACKed. With SACKs this number is simply
2099  *                 amount of SACKed data. Even without SACKs
2100  *                 it is easy to give pretty reliable estimate of this number,
2101  *                 counting duplicate ACKs.
2102  *
2103  *       lost_out: Packets lost by network. TCP has no explicit
2104  *                 "loss notification" feedback from network (for now).
2105  *                 It means that this number can be only _guessed_.
2106  *                 Actually, it is the heuristics to predict lossage that
2107  *                 distinguishes different algorithms.
2108  *
2109  *      F.e. after RTO, when all the queue is considered as lost,
2110  *      lost_out = packets_out and in_flight = retrans_out.
2111  *
2112  *              Essentially, we have now two algorithms counting
2113  *              lost packets.
2114  *
2115  *              FACK: It is the simplest heuristics. As soon as we decided
2116  *              that something is lost, we decide that _all_ not SACKed
2117  *              packets until the most forward SACK are lost. I.e.
2118  *              lost_out = fackets_out - sacked_out and left_out = fackets_out.
2119  *              It is absolutely correct estimate, if network does not reorder
2120  *              packets. And it loses any connection to reality when reordering
2121  *              takes place. We use FACK by default until reordering
2122  *              is suspected on the path to this destination.
2123  *
2124  *              NewReno: when Recovery is entered, we assume that one segment
2125  *              is lost (classic Reno). While we are in Recovery and
2126  *              a partial ACK arrives, we assume that one more packet
2127  *              is lost (NewReno). This heuristics are the same in NewReno
2128  *              and SACK.
2129  *
2130  *  Imagine, that's all! Forget about all this shamanism about CWND inflation
2131  *  deflation etc. CWND is real congestion window, never inflated, changes
2132  *  only according to classic VJ rules.
2133  *
2134  * Really tricky (and requiring careful tuning) part of algorithm
2135  * is hidden in functions tcp_time_to_recover() and tcp_xmit_retransmit_queue().
2136  * The first determines the moment _when_ we should reduce CWND and,
2137  * hence, slow down forward transmission. In fact, it determines the moment
2138  * when we decide that hole is caused by loss, rather than by a reorder.
2139  *
2140  * tcp_xmit_retransmit_queue() decides, _what_ we should retransmit to fill
2141  * holes, caused by lost packets.
2142  *
2143  * And the most logically complicated part of algorithm is undo
2144  * heuristics. We detect false retransmits due to both too early
2145  * fast retransmit (reordering) and underestimated RTO, analyzing
2146  * timestamps and D-SACKs. When we detect that some segments were
2147  * retransmitted by mistake and CWND reduction was wrong, we undo
2148  * window reduction and abort recovery phase. This logic is hidden
2149  * inside several functions named tcp_try_undo_<something>.
2150  */
2151
2152 /* This function decides, when we should leave Disordered state
2153  * and enter Recovery phase, reducing congestion window.
2154  *
2155  * Main question: may we further continue forward transmission
2156  * with the same cwnd?
2157  */
2158 static bool tcp_time_to_recover(struct sock *sk, int flag)
2159 {
2160         struct tcp_sock *tp = tcp_sk(sk);
2161         __u32 packets_out;
2162
2163         /* Trick#1: The loss is proven. */
2164         if (tp->lost_out)
2165                 return true;
2166
2167         /* Not-A-Trick#2 : Classic rule... */
2168         if (tcp_dupack_heuristics(tp) > tp->reordering)
2169                 return true;
2170
2171         /* Trick#4: It is still not OK... But will it be useful to delay
2172          * recovery more?
2173          */
2174         packets_out = tp->packets_out;
2175         if (packets_out <= tp->reordering &&
2176             tp->sacked_out >= max_t(__u32, packets_out/2, sysctl_tcp_reordering) &&
2177             !tcp_may_send_now(sk)) {
2178                 /* We have nothing to send. This connection is limited
2179                  * either by receiver window or by application.
2180                  */
2181                 return true;
2182         }
2183
2184         /* If a thin stream is detected, retransmit after first
2185          * received dupack. Employ only if SACK is supported in order
2186          * to avoid possible corner-case series of spurious retransmissions
2187          * Use only if there are no unsent data.
2188          */
2189         if ((tp->thin_dupack || sysctl_tcp_thin_dupack) &&
2190             tcp_stream_is_thin(tp) && tcp_dupack_heuristics(tp) > 1 &&
2191             tcp_is_sack(tp) && !tcp_send_head(sk))
2192                 return true;
2193
2194         /* Trick#6: TCP early retransmit, per RFC5827.  To avoid spurious
2195          * retransmissions due to small network reorderings, we implement
2196          * Mitigation A.3 in the RFC and delay the retransmission for a short
2197          * interval if appropriate.
2198          */
2199         if (tp->do_early_retrans && !tp->retrans_out && tp->sacked_out &&
2200             (tp->packets_out >= (tp->sacked_out + 1) && tp->packets_out < 4) &&
2201             !tcp_may_send_now(sk))
2202                 return !tcp_pause_early_retransmit(sk, flag);
2203
2204         return false;
2205 }
2206
2207 /* Detect loss in event "A" above by marking head of queue up as lost.
2208  * For FACK or non-SACK(Reno) senders, the first "packets" number of segments
2209  * are considered lost. For RFC3517 SACK, a segment is considered lost if it
2210  * has at least tp->reordering SACKed seqments above it; "packets" refers to
2211  * the maximum SACKed segments to pass before reaching this limit.
2212  */
2213 static void tcp_mark_head_lost(struct sock *sk, int packets, int mark_head)
2214 {
2215         struct tcp_sock *tp = tcp_sk(sk);
2216         struct sk_buff *skb;
2217         int cnt, oldcnt;
2218         int err;
2219         unsigned int mss;
2220         /* Use SACK to deduce losses of new sequences sent during recovery */
2221         const u32 loss_high = tcp_is_sack(tp) ?  tp->snd_nxt : tp->high_seq;
2222
2223         WARN_ON(packets > tp->packets_out);
2224         if (tp->lost_skb_hint) {
2225                 skb = tp->lost_skb_hint;
2226                 cnt = tp->lost_cnt_hint;
2227                 /* Head already handled? */
2228                 if (mark_head && skb != tcp_write_queue_head(sk))
2229                         return;
2230         } else {
2231                 skb = tcp_write_queue_head(sk);
2232                 cnt = 0;
2233         }
2234
2235         tcp_for_write_queue_from(skb, sk) {
2236                 if (skb == tcp_send_head(sk))
2237                         break;
2238                 /* TODO: do this better */
2239                 /* this is not the most efficient way to do this... */
2240                 tp->lost_skb_hint = skb;
2241                 tp->lost_cnt_hint = cnt;
2242
2243                 if (after(TCP_SKB_CB(skb)->end_seq, loss_high))
2244                         break;
2245
2246                 oldcnt = cnt;
2247                 if (tcp_is_fack(tp) || tcp_is_reno(tp) ||
2248                     (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
2249                         cnt += tcp_skb_pcount(skb);
2250
2251                 if (cnt > packets) {
2252                         if ((tcp_is_sack(tp) && !tcp_is_fack(tp)) ||
2253                             (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED) ||
2254                             (oldcnt >= packets))
2255                                 break;
2256
2257                         mss = skb_shinfo(skb)->gso_size;
2258                         err = tcp_fragment(sk, skb, (packets - oldcnt) * mss,
2259                                            mss, GFP_ATOMIC);
2260                         if (err < 0)
2261                                 break;
2262                         cnt = packets;
2263                 }
2264
2265                 tcp_skb_mark_lost(tp, skb);
2266
2267                 if (mark_head)
2268                         break;
2269         }
2270         tcp_verify_left_out(tp);
2271 }
2272
2273 /* Account newly detected lost packet(s) */
2274
2275 static void tcp_update_scoreboard(struct sock *sk, int fast_rexmit)
2276 {
2277         struct tcp_sock *tp = tcp_sk(sk);
2278
2279         if (tcp_is_reno(tp)) {
2280                 tcp_mark_head_lost(sk, 1, 1);
2281         } else if (tcp_is_fack(tp)) {
2282                 int lost = tp->fackets_out - tp->reordering;
2283                 if (lost <= 0)
2284                         lost = 1;
2285                 tcp_mark_head_lost(sk, lost, 0);
2286         } else {
2287                 int sacked_upto = tp->sacked_out - tp->reordering;
2288                 if (sacked_upto >= 0)
2289                         tcp_mark_head_lost(sk, sacked_upto, 0);
2290                 else if (fast_rexmit)
2291                         tcp_mark_head_lost(sk, 1, 1);
2292         }
2293 }
2294
2295 /* CWND moderation, preventing bursts due to too big ACKs
2296  * in dubious situations.
2297  */
2298 static inline void tcp_moderate_cwnd(struct tcp_sock *tp)
2299 {
2300         tp->snd_cwnd = min(tp->snd_cwnd,
2301                            tcp_packets_in_flight(tp) + tcp_max_burst(tp));
2302         tp->snd_cwnd_stamp = tcp_time_stamp;
2303 }
2304
2305 /* Nothing was retransmitted or returned timestamp is less
2306  * than timestamp of the first retransmission.
2307  */
2308 static inline bool tcp_packet_delayed(const struct tcp_sock *tp)
2309 {
2310         return !tp->retrans_stamp ||
2311                 (tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr &&
2312                  before(tp->rx_opt.rcv_tsecr, tp->retrans_stamp));
2313 }
2314
2315 /* Undo procedures. */
2316
2317 #if FASTRETRANS_DEBUG > 1
2318 static void DBGUNDO(struct sock *sk, const char *msg)
2319 {
2320         struct tcp_sock *tp = tcp_sk(sk);
2321         struct inet_sock *inet = inet_sk(sk);
2322
2323         if (sk->sk_family == AF_INET) {
2324                 pr_debug("Undo %s %pI4/%u c%u l%u ss%u/%u p%u\n",
2325                          msg,
2326                          &inet->inet_daddr, ntohs(inet->inet_dport),
2327                          tp->snd_cwnd, tcp_left_out(tp),
2328                          tp->snd_ssthresh, tp->prior_ssthresh,
2329                          tp->packets_out);
2330         }
2331 #if IS_ENABLED(CONFIG_IPV6)
2332         else if (sk->sk_family == AF_INET6) {
2333                 struct ipv6_pinfo *np = inet6_sk(sk);
2334                 pr_debug("Undo %s %pI6/%u c%u l%u ss%u/%u p%u\n",
2335                          msg,
2336                          &np->daddr, ntohs(inet->inet_dport),
2337                          tp->snd_cwnd, tcp_left_out(tp),
2338                          tp->snd_ssthresh, tp->prior_ssthresh,
2339                          tp->packets_out);
2340         }
2341 #endif
2342 }
2343 #else
2344 #define DBGUNDO(x...) do { } while (0)
2345 #endif
2346
2347 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
2348 {
2349         struct tcp_sock *tp = tcp_sk(sk);
2350
2351         if (unmark_loss) {
2352                 struct sk_buff *skb;
2353
2354                 tcp_for_write_queue(skb, sk) {
2355                         if (skb == tcp_send_head(sk))
2356                                 break;
2357                         TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
2358                 }
2359                 tp->lost_out = 0;
2360                 tcp_clear_all_retrans_hints(tp);
2361         }
2362
2363         if (tp->prior_ssthresh) {
2364                 const struct inet_connection_sock *icsk = inet_csk(sk);
2365
2366                 if (icsk->icsk_ca_ops->undo_cwnd)
2367                         tp->snd_cwnd = icsk->icsk_ca_ops->undo_cwnd(sk);
2368                 else
2369                         tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh << 1);
2370
2371                 if (tp->prior_ssthresh > tp->snd_ssthresh) {
2372                         tp->snd_ssthresh = tp->prior_ssthresh;
2373                         tcp_ecn_withdraw_cwr(tp);
2374                 }
2375         } else {
2376                 tp->snd_cwnd = max(tp->snd_cwnd, tp->snd_ssthresh);
2377         }
2378         tp->snd_cwnd_stamp = tcp_time_stamp;
2379         tp->undo_marker = 0;
2380 }
2381
2382 static inline bool tcp_may_undo(const struct tcp_sock *tp)
2383 {
2384         return tp->undo_marker && (!tp->undo_retrans || tcp_packet_delayed(tp));
2385 }
2386
2387 /* People celebrate: "We love our President!" */
2388 static bool tcp_try_undo_recovery(struct sock *sk)
2389 {
2390         struct tcp_sock *tp = tcp_sk(sk);
2391
2392         if (tcp_may_undo(tp)) {
2393                 int mib_idx;
2394
2395                 /* Happy end! We did not retransmit anything
2396                  * or our original transmission succeeded.
2397                  */
2398                 DBGUNDO(sk, inet_csk(sk)->icsk_ca_state == TCP_CA_Loss ? "loss" : "retrans");
2399                 tcp_undo_cwnd_reduction(sk, false);
2400                 if (inet_csk(sk)->icsk_ca_state == TCP_CA_Loss)
2401                         mib_idx = LINUX_MIB_TCPLOSSUNDO;
2402                 else
2403                         mib_idx = LINUX_MIB_TCPFULLUNDO;
2404
2405                 NET_INC_STATS_BH(sock_net(sk), mib_idx);
2406         }
2407         if (tp->snd_una == tp->high_seq && tcp_is_reno(tp)) {
2408                 /* Hold old state until something *above* high_seq
2409                  * is ACKed. For Reno it is MUST to prevent false
2410                  * fast retransmits (RFC2582). SACK TCP is safe. */
2411                 tcp_moderate_cwnd(tp);
2412                 return true;
2413         }
2414         tcp_set_ca_state(sk, TCP_CA_Open);
2415         return false;
2416 }
2417
2418 /* Try to undo cwnd reduction, because D-SACKs acked all retransmitted data */
2419 static bool tcp_try_undo_dsack(struct sock *sk)
2420 {
2421         struct tcp_sock *tp = tcp_sk(sk);
2422
2423         if (tp->undo_marker && !tp->undo_retrans) {
2424                 DBGUNDO(sk, "D-SACK");
2425                 tcp_undo_cwnd_reduction(sk, false);
2426                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPDSACKUNDO);
2427                 return true;
2428         }
2429         return false;
2430 }
2431
2432 /* We can clear retrans_stamp when there are no retransmissions in the
2433  * window. It would seem that it is trivially available for us in
2434  * tp->retrans_out, however, that kind of assumptions doesn't consider
2435  * what will happen if errors occur when sending retransmission for the
2436  * second time. ...It could the that such segment has only
2437  * TCPCB_EVER_RETRANS set at the present time. It seems that checking
2438  * the head skb is enough except for some reneging corner cases that
2439  * are not worth the effort.
2440  *
2441  * Main reason for all this complexity is the fact that connection dying
2442  * time now depends on the validity of the retrans_stamp, in particular,
2443  * that successive retransmissions of a segment must not advance
2444  * retrans_stamp under any conditions.
2445  */
2446 static bool tcp_any_retrans_done(const struct sock *sk)
2447 {
2448         const struct tcp_sock *tp = tcp_sk(sk);
2449         struct sk_buff *skb;
2450
2451         if (tp->retrans_out)
2452                 return true;
2453
2454         skb = tcp_write_queue_head(sk);
2455         if (unlikely(skb && TCP_SKB_CB(skb)->sacked & TCPCB_EVER_RETRANS))
2456                 return true;
2457
2458         return false;
2459 }
2460
2461 /* Undo during loss recovery after partial ACK or using F-RTO. */
2462 static bool tcp_try_undo_loss(struct sock *sk, bool frto_undo)
2463 {
2464         struct tcp_sock *tp = tcp_sk(sk);
2465
2466         if (frto_undo || tcp_may_undo(tp)) {
2467                 tcp_undo_cwnd_reduction(sk, true);
2468
2469                 DBGUNDO(sk, "partial loss");
2470                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPLOSSUNDO);
2471                 if (frto_undo)
2472                         NET_INC_STATS_BH(sock_net(sk),
2473                                          LINUX_MIB_TCPSPURIOUSRTOS);
2474                 inet_csk(sk)->icsk_retransmits = 0;
2475                 if (frto_undo || tcp_is_sack(tp))
2476                         tcp_set_ca_state(sk, TCP_CA_Open);
2477                 return true;
2478         }
2479         return false;
2480 }
2481
2482 /* The cwnd reduction in CWR and Recovery use the PRR algorithm
2483  * https://datatracker.ietf.org/doc/draft-ietf-tcpm-proportional-rate-reduction/
2484  * It computes the number of packets to send (sndcnt) based on packets newly
2485  * delivered:
2486  *   1) If the packets in flight is larger than ssthresh, PRR spreads the
2487  *      cwnd reductions across a full RTT.
2488  *   2) If packets in flight is lower than ssthresh (such as due to excess
2489  *      losses and/or application stalls), do not perform any further cwnd
2490  *      reductions, but instead slow start up to ssthresh.
2491  */
2492 static void tcp_init_cwnd_reduction(struct sock *sk)
2493 {
2494         struct tcp_sock *tp = tcp_sk(sk);
2495
2496         tp->high_seq = tp->snd_nxt;
2497         tp->tlp_high_seq = 0;
2498         tp->snd_cwnd_cnt = 0;
2499         tp->prior_cwnd = tp->snd_cwnd;
2500         tp->prr_delivered = 0;
2501         tp->prr_out = 0;
2502         tp->snd_ssthresh = inet_csk(sk)->icsk_ca_ops->ssthresh(sk);
2503         tcp_ecn_queue_cwr(tp);
2504 }
2505
2506 static void tcp_cwnd_reduction(struct sock *sk, const int prior_unsacked,
2507                                int fast_rexmit)
2508 {
2509         struct tcp_sock *tp = tcp_sk(sk);
2510         int sndcnt = 0;
2511         int delta = tp->snd_ssthresh - tcp_packets_in_flight(tp);
2512         int newly_acked_sacked = prior_unsacked -
2513                                  (tp->packets_out - tp->sacked_out);
2514
2515         tp->prr_delivered += newly_acked_sacked;
2516         if (tcp_packets_in_flight(tp) > tp->snd_ssthresh) {
2517                 u64 dividend = (u64)tp->snd_ssthresh * tp->prr_delivered +
2518                                tp->prior_cwnd - 1;
2519                 sndcnt = div_u64(dividend, tp->prior_cwnd) - tp->prr_out;
2520         } else {
2521                 sndcnt = min_t(int, delta,
2522                                max_t(int, tp->prr_delivered - tp->prr_out,
2523                                      newly_acked_sacked) + 1);
2524         }
2525
2526         sndcnt = max(sndcnt, (fast_rexmit ? 1 : 0));
2527         tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt;
2528 }
2529
2530 static inline void tcp_end_cwnd_reduction(struct sock *sk)
2531 {
2532         struct tcp_sock *tp = tcp_sk(sk);
2533
2534         /* Reset cwnd to ssthresh in CWR or Recovery (unless it's undone) */
2535         if (inet_csk(sk)->icsk_ca_state == TCP_CA_CWR ||
2536             (tp->undo_marker && tp->snd_ssthresh < TCP_INFINITE_SSTHRESH)) {
2537                 tp->snd_cwnd = tp->snd_ssthresh;
2538                 tp->snd_cwnd_stamp = tcp_time_stamp;
2539         }
2540         tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR);
2541 }
2542
2543 /* Enter CWR state. Disable cwnd undo since congestion is proven with ECN */
2544 void tcp_enter_cwr(struct sock *sk)
2545 {
2546         struct tcp_sock *tp = tcp_sk(sk);
2547
2548         tp->prior_ssthresh = 0;
2549         if (inet_csk(sk)->icsk_ca_state < TCP_CA_CWR) {
2550                 tp->undo_marker = 0;
2551                 tcp_init_cwnd_reduction(sk);
2552                 tcp_set_ca_state(sk, TCP_CA_CWR);
2553         }
2554 }
2555
2556 static void tcp_try_keep_open(struct sock *sk)
2557 {
2558         struct tcp_sock *tp = tcp_sk(sk);
2559         int state = TCP_CA_Open;
2560
2561         if (tcp_left_out(tp) || tcp_any_retrans_done(sk))
2562                 state = TCP_CA_Disorder;
2563
2564         if (inet_csk(sk)->icsk_ca_state != state) {
2565                 tcp_set_ca_state(sk, state);
2566                 tp->high_seq = tp->snd_nxt;
2567         }
2568 }
2569
2570 static void tcp_try_to_open(struct sock *sk, int flag, const int prior_unsacked)
2571 {
2572         struct tcp_sock *tp = tcp_sk(sk);
2573
2574         tcp_verify_left_out(tp);
2575
2576         if (!tcp_any_retrans_done(sk))
2577                 tp->retrans_stamp = 0;
2578
2579         if (flag & FLAG_ECE)
2580                 tcp_enter_cwr(sk);
2581
2582         if (inet_csk(sk)->icsk_ca_state != TCP_CA_CWR) {
2583                 tcp_try_keep_open(sk);
2584         } else {
2585                 tcp_cwnd_reduction(sk, prior_unsacked, 0);
2586         }
2587 }
2588
2589 static void tcp_mtup_probe_failed(struct sock *sk)
2590 {
2591         struct inet_connection_sock *icsk = inet_csk(sk);
2592
2593         icsk->icsk_mtup.search_high = icsk->icsk_mtup.probe_size - 1;
2594         icsk->icsk_mtup.probe_size = 0;
2595 }
2596
2597 static void tcp_mtup_probe_success(struct sock *sk)
2598 {
2599         struct tcp_sock *tp = tcp_sk(sk);
2600         struct inet_connection_sock *icsk = inet_csk(sk);
2601
2602         /* FIXME: breaks with very large cwnd */
2603         tp->prior_ssthresh = tcp_current_ssthresh(sk);
2604         tp->snd_cwnd = tp->snd_cwnd *
2605                        tcp_mss_to_mtu(sk, tp->mss_cache) /
2606                        icsk->icsk_mtup.probe_size;
2607         tp->snd_cwnd_cnt = 0;
2608         tp->snd_cwnd_stamp = tcp_time_stamp;
2609         tp->snd_ssthresh = tcp_current_ssthresh(sk);
2610
2611         icsk->icsk_mtup.search_low = icsk->icsk_mtup.probe_size;
2612         icsk->icsk_mtup.probe_size = 0;
2613         tcp_sync_mss(sk, icsk->icsk_pmtu_cookie);
2614 }
2615
2616 /* Do a simple retransmit without using the backoff mechanisms in
2617  * tcp_timer. This is used for path mtu discovery.
2618  * The socket is already locked here.
2619  */
2620 void tcp_simple_retransmit(struct sock *sk)
2621 {
2622         const struct inet_connection_sock *icsk = inet_csk(sk);
2623         struct tcp_sock *tp = tcp_sk(sk);
2624         struct sk_buff *skb;
2625         unsigned int mss = tcp_current_mss(sk);
2626         u32 prior_lost = tp->lost_out;
2627
2628         tcp_for_write_queue(skb, sk) {
2629                 if (skb == tcp_send_head(sk))
2630                         break;
2631                 if (tcp_skb_seglen(skb) > mss &&
2632                     !(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)) {
2633                         if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) {
2634                                 TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
2635                                 tp->retrans_out -= tcp_skb_pcount(skb);
2636                         }
2637                         tcp_skb_mark_lost_uncond_verify(tp, skb);
2638                 }
2639         }
2640
2641         tcp_clear_retrans_hints_partial(tp);
2642
2643         if (prior_lost == tp->lost_out)
2644                 return;
2645
2646         if (tcp_is_reno(tp))
2647                 tcp_limit_reno_sacked(tp);
2648
2649         tcp_verify_left_out(tp);
2650
2651         /* Don't muck with the congestion window here.
2652          * Reason is that we do not increase amount of _data_
2653          * in network, but units changed and effective
2654          * cwnd/ssthresh really reduced now.
2655          */
2656         if (icsk->icsk_ca_state != TCP_CA_Loss) {
2657                 tp->high_seq = tp->snd_nxt;
2658                 tp->snd_ssthresh = tcp_current_ssthresh(sk);
2659                 tp->prior_ssthresh = 0;
2660                 tp->undo_marker = 0;
2661                 tcp_set_ca_state(sk, TCP_CA_Loss);
2662         }
2663         tcp_xmit_retransmit_queue(sk);
2664 }
2665 EXPORT_SYMBOL(tcp_simple_retransmit);
2666
2667 static void tcp_enter_recovery(struct sock *sk, bool ece_ack)
2668 {
2669         struct tcp_sock *tp = tcp_sk(sk);
2670         int mib_idx;
2671
2672         if (tcp_is_reno(tp))
2673                 mib_idx = LINUX_MIB_TCPRENORECOVERY;
2674         else
2675                 mib_idx = LINUX_MIB_TCPSACKRECOVERY;
2676
2677         NET_INC_STATS_BH(sock_net(sk), mib_idx);
2678
2679         tp->prior_ssthresh = 0;
2680         tcp_init_undo(tp);
2681
2682         if (inet_csk(sk)->icsk_ca_state < TCP_CA_CWR) {
2683                 if (!ece_ack)
2684                         tp->prior_ssthresh = tcp_current_ssthresh(sk);
2685                 tcp_init_cwnd_reduction(sk);
2686         }
2687         tcp_set_ca_state(sk, TCP_CA_Recovery);
2688 }
2689
2690 /* Process an ACK in CA_Loss state. Move to CA_Open if lost data are
2691  * recovered or spurious. Otherwise retransmits more on partial ACKs.
2692  */
2693 static void tcp_process_loss(struct sock *sk, int flag, bool is_dupack)
2694 {
2695         struct tcp_sock *tp = tcp_sk(sk);
2696         bool recovered = !before(tp->snd_una, tp->high_seq);
2697
2698         if (tp->frto) { /* F-RTO RFC5682 sec 3.1 (sack enhanced version). */
2699                 /* Step 3.b. A timeout is spurious if not all data are
2700                  * lost, i.e., never-retransmitted data are (s)acked.
2701                  */
2702                 if (tcp_try_undo_loss(sk, flag & FLAG_ORIG_SACK_ACKED))
2703                         return;
2704
2705                 if (after(tp->snd_nxt, tp->high_seq) &&
2706                     (flag & FLAG_DATA_SACKED || is_dupack)) {
2707                         tp->frto = 0; /* Loss was real: 2nd part of step 3.a */
2708                 } else if (flag & FLAG_SND_UNA_ADVANCED && !recovered) {
2709                         tp->high_seq = tp->snd_nxt;
2710                         __tcp_push_pending_frames(sk, tcp_current_mss(sk),
2711                                                   TCP_NAGLE_OFF);
2712                         if (after(tp->snd_nxt, tp->high_seq))
2713                                 return; /* Step 2.b */
2714                         tp->frto = 0;
2715                 }
2716         }
2717
2718         if (recovered) {
2719                 /* F-RTO RFC5682 sec 3.1 step 2.a and 1st part of step 3.a */
2720                 tcp_try_undo_recovery(sk);
2721                 return;
2722         }
2723         if (tcp_is_reno(tp)) {
2724                 /* A Reno DUPACK means new data in F-RTO step 2.b above are
2725                  * delivered. Lower inflight to clock out (re)tranmissions.
2726                  */
2727                 if (after(tp->snd_nxt, tp->high_seq) && is_dupack)
2728                         tcp_add_reno_sack(sk);
2729                 else if (flag & FLAG_SND_UNA_ADVANCED)
2730                         tcp_reset_reno_sack(tp);
2731         }
2732         if (tcp_try_undo_loss(sk, false))
2733                 return;
2734         tcp_xmit_retransmit_queue(sk);
2735 }
2736
2737 /* Undo during fast recovery after partial ACK. */
2738 static bool tcp_try_undo_partial(struct sock *sk, const int acked,
2739                                  const int prior_unsacked)
2740 {
2741         struct tcp_sock *tp = tcp_sk(sk);
2742
2743         if (tp->undo_marker && tcp_packet_delayed(tp)) {
2744                 /* Plain luck! Hole if filled with delayed
2745                  * packet, rather than with a retransmit.
2746                  */
2747                 tcp_update_reordering(sk, tcp_fackets_out(tp) + acked, 1);
2748
2749                 /* We are getting evidence that the reordering degree is higher
2750                  * than we realized. If there are no retransmits out then we
2751                  * can undo. Otherwise we clock out new packets but do not
2752                  * mark more packets lost or retransmit more.
2753                  */
2754                 if (tp->retrans_out) {
2755                         tcp_cwnd_reduction(sk, prior_unsacked, 0);
2756                         return true;
2757                 }
2758
2759                 if (!tcp_any_retrans_done(sk))
2760                         tp->retrans_stamp = 0;
2761
2762                 DBGUNDO(sk, "partial recovery");
2763                 tcp_undo_cwnd_reduction(sk, true);
2764                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPARTIALUNDO);
2765                 tcp_try_keep_open(sk);
2766                 return true;
2767         }
2768         return false;
2769 }
2770
2771 /* Process an event, which can update packets-in-flight not trivially.
2772  * Main goal of this function is to calculate new estimate for left_out,
2773  * taking into account both packets sitting in receiver's buffer and
2774  * packets lost by network.
2775  *
2776  * Besides that it does CWND reduction, when packet loss is detected
2777  * and changes state of machine.
2778  *
2779  * It does _not_ decide what to send, it is made in function
2780  * tcp_xmit_retransmit_queue().
2781  */
2782 static void tcp_fastretrans_alert(struct sock *sk, const int acked,
2783                                   const int prior_unsacked,
2784                                   bool is_dupack, int flag)
2785 {
2786         struct inet_connection_sock *icsk = inet_csk(sk);
2787         struct tcp_sock *tp = tcp_sk(sk);
2788         bool do_lost = is_dupack || ((flag & FLAG_DATA_SACKED) &&
2789                                     (tcp_fackets_out(tp) > tp->reordering));
2790         int fast_rexmit = 0;
2791
2792         if (WARN_ON(!tp->packets_out && tp->sacked_out))
2793                 tp->sacked_out = 0;
2794         if (WARN_ON(!tp->sacked_out && tp->fackets_out))
2795                 tp->fackets_out = 0;
2796
2797         /* Now state machine starts.
2798          * A. ECE, hence prohibit cwnd undoing, the reduction is required. */
2799         if (flag & FLAG_ECE)
2800                 tp->prior_ssthresh = 0;
2801
2802         /* B. In all the states check for reneging SACKs. */
2803         if (tcp_check_sack_reneging(sk, flag))
2804                 return;
2805
2806         /* C. Check consistency of the current state. */
2807         tcp_verify_left_out(tp);
2808
2809         /* D. Check state exit conditions. State can be terminated
2810          *    when high_seq is ACKed. */
2811         if (icsk->icsk_ca_state == TCP_CA_Open) {
2812                 WARN_ON(tp->retrans_out != 0);
2813                 tp->retrans_stamp = 0;
2814         } else if (!before(tp->snd_una, tp->high_seq)) {
2815                 switch (icsk->icsk_ca_state) {
2816                 case TCP_CA_CWR:
2817                         /* CWR is to be held something *above* high_seq
2818                          * is ACKed for CWR bit to reach receiver. */
2819                         if (tp->snd_una != tp->high_seq) {
2820                                 tcp_end_cwnd_reduction(sk);
2821                                 tcp_set_ca_state(sk, TCP_CA_Open);
2822                         }
2823                         break;
2824
2825                 case TCP_CA_Recovery:
2826                         if (tcp_is_reno(tp))
2827                                 tcp_reset_reno_sack(tp);
2828                         if (tcp_try_undo_recovery(sk))
2829                                 return;
2830                         tcp_end_cwnd_reduction(sk);
2831                         break;
2832                 }
2833         }
2834
2835         /* E. Process state. */
2836         switch (icsk->icsk_ca_state) {
2837         case TCP_CA_Recovery:
2838                 if (!(flag & FLAG_SND_UNA_ADVANCED)) {
2839                         if (tcp_is_reno(tp) && is_dupack)
2840                                 tcp_add_reno_sack(sk);
2841                 } else {
2842                         if (tcp_try_undo_partial(sk, acked, prior_unsacked))
2843                                 return;
2844                         /* Partial ACK arrived. Force fast retransmit. */
2845                         do_lost = tcp_is_reno(tp) ||
2846                                   tcp_fackets_out(tp) > tp->reordering;
2847                 }
2848                 if (tcp_try_undo_dsack(sk)) {
2849                         tcp_try_keep_open(sk);
2850                         return;
2851                 }
2852                 break;
2853         case TCP_CA_Loss:
2854                 tcp_process_loss(sk, flag, is_dupack);
2855                 if (icsk->icsk_ca_state != TCP_CA_Open)
2856                         return;
2857                 /* Fall through to processing in Open state. */
2858         default:
2859                 if (tcp_is_reno(tp)) {
2860                         if (flag & FLAG_SND_UNA_ADVANCED)
2861                                 tcp_reset_reno_sack(tp);
2862                         if (is_dupack)
2863                                 tcp_add_reno_sack(sk);
2864                 }
2865
2866                 if (icsk->icsk_ca_state <= TCP_CA_Disorder)
2867                         tcp_try_undo_dsack(sk);
2868
2869                 if (!tcp_time_to_recover(sk, flag)) {
2870                         tcp_try_to_open(sk, flag, prior_unsacked);
2871                         return;
2872                 }
2873
2874                 /* MTU probe failure: don't reduce cwnd */
2875                 if (icsk->icsk_ca_state < TCP_CA_CWR &&
2876                     icsk->icsk_mtup.probe_size &&
2877                     tp->snd_una == tp->mtu_probe.probe_seq_start) {
2878                         tcp_mtup_probe_failed(sk);
2879                         /* Restores the reduction we did in tcp_mtup_probe() */
2880                         tp->snd_cwnd++;
2881                         tcp_simple_retransmit(sk);
2882                         return;
2883                 }
2884
2885                 /* Otherwise enter Recovery state */
2886                 tcp_enter_recovery(sk, (flag & FLAG_ECE));
2887                 fast_rexmit = 1;
2888         }
2889
2890         if (do_lost)
2891                 tcp_update_scoreboard(sk, fast_rexmit);
2892         tcp_cwnd_reduction(sk, prior_unsacked, fast_rexmit);
2893         tcp_xmit_retransmit_queue(sk);
2894 }
2895
2896 static inline bool tcp_ack_update_rtt(struct sock *sk, const int flag,
2897                                       long seq_rtt_us, long sack_rtt_us)
2898 {
2899         const struct tcp_sock *tp = tcp_sk(sk);
2900
2901         /* Prefer RTT measured from ACK's timing to TS-ECR. This is because
2902          * broken middle-boxes or peers may corrupt TS-ECR fields. But
2903          * Karn's algorithm forbids taking RTT if some retransmitted data
2904          * is acked (RFC6298).
2905          */
2906         if (flag & FLAG_RETRANS_DATA_ACKED)
2907                 seq_rtt_us = -1L;
2908
2909         if (seq_rtt_us < 0)
2910                 seq_rtt_us = sack_rtt_us;
2911
2912         /* RTTM Rule: A TSecr value received in a segment is used to
2913          * update the averaged RTT measurement only if the segment
2914          * acknowledges some new data, i.e., only if it advances the
2915          * left edge of the send window.
2916          * See draft-ietf-tcplw-high-performance-00, section 3.3.
2917          */
2918         if (seq_rtt_us < 0 && tp->rx_opt.saw_tstamp && tp->rx_opt.rcv_tsecr &&
2919             flag & FLAG_ACKED)
2920                 seq_rtt_us = jiffies_to_usecs(tcp_time_stamp - tp->rx_opt.rcv_tsecr);
2921
2922         if (seq_rtt_us < 0)
2923                 return false;
2924
2925         tcp_rtt_estimator(sk, seq_rtt_us);
2926         tcp_set_rto(sk);
2927
2928         /* RFC6298: only reset backoff on valid RTT measurement. */
2929         inet_csk(sk)->icsk_backoff = 0;
2930         return true;
2931 }
2932
2933 /* Compute time elapsed between (last) SYNACK and the ACK completing 3WHS. */
2934 static void tcp_synack_rtt_meas(struct sock *sk, const u32 synack_stamp)
2935 {
2936         struct tcp_sock *tp = tcp_sk(sk);
2937         long seq_rtt_us = -1L;
2938
2939         if (synack_stamp && !tp->total_retrans)
2940                 seq_rtt_us = jiffies_to_usecs(tcp_time_stamp - synack_stamp);
2941
2942         /* If the ACK acks both the SYNACK and the (Fast Open'd) data packets
2943          * sent in SYN_RECV, SYNACK RTT is the smooth RTT computed in tcp_ack()
2944          */
2945         if (!tp->srtt_us)
2946                 tcp_ack_update_rtt(sk, FLAG_SYN_ACKED, seq_rtt_us, -1L);
2947 }
2948
2949 static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 acked)
2950 {
2951         const struct inet_connection_sock *icsk = inet_csk(sk);
2952
2953         icsk->icsk_ca_ops->cong_avoid(sk, ack, acked);
2954         tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp;
2955 }
2956
2957 /* Restart timer after forward progress on connection.
2958  * RFC2988 recommends to restart timer to now+rto.
2959  */
2960 void tcp_rearm_rto(struct sock *sk)
2961 {
2962         const struct inet_connection_sock *icsk = inet_csk(sk);
2963         struct tcp_sock *tp = tcp_sk(sk);
2964
2965         /* If the retrans timer is currently being used by Fast Open
2966          * for SYN-ACK retrans purpose, stay put.
2967          */
2968         if (tp->fastopen_rsk)
2969                 return;
2970
2971         if (!tp->packets_out) {
2972                 inet_csk_clear_xmit_timer(sk, ICSK_TIME_RETRANS);
2973         } else {
2974                 u32 rto = inet_csk(sk)->icsk_rto;
2975                 /* Offset the time elapsed after installing regular RTO */
2976                 if (icsk->icsk_pending == ICSK_TIME_EARLY_RETRANS ||
2977                     icsk->icsk_pending == ICSK_TIME_LOSS_PROBE) {
2978                         struct sk_buff *skb = tcp_write_queue_head(sk);
2979                         const u32 rto_time_stamp =
2980                                 tcp_skb_timestamp(skb) + rto;
2981                         s32 delta = (s32)(rto_time_stamp - tcp_time_stamp);
2982                         /* delta may not be positive if the socket is locked
2983                          * when the retrans timer fires and is rescheduled.
2984                          */
2985                         if (delta > 0)
2986                                 rto = delta;
2987                 }
2988                 inet_csk_reset_xmit_timer(sk, ICSK_TIME_RETRANS, rto,
2989                                           TCP_RTO_MAX);
2990         }
2991 }
2992
2993 /* This function is called when the delayed ER timer fires. TCP enters
2994  * fast recovery and performs fast-retransmit.
2995  */
2996 void tcp_resume_early_retransmit(struct sock *sk)
2997 {
2998         struct tcp_sock *tp = tcp_sk(sk);
2999
3000         tcp_rearm_rto(sk);
3001
3002         /* Stop if ER is disabled after the delayed ER timer is scheduled */
3003         if (!tp->do_early_retrans)
3004                 return;
3005
3006         tcp_enter_recovery(sk, false);
3007         tcp_update_scoreboard(sk, 1);
3008         tcp_xmit_retransmit_queue(sk);
3009 }
3010
3011 /* If we get here, the whole TSO packet has not been acked. */
3012 static u32 tcp_tso_acked(struct sock *sk, struct sk_buff *skb)
3013 {
3014         struct tcp_sock *tp = tcp_sk(sk);
3015         u32 packets_acked;
3016
3017         BUG_ON(!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una));
3018
3019         packets_acked = tcp_skb_pcount(skb);
3020         if (tcp_trim_head(sk, skb, tp->snd_una - TCP_SKB_CB(skb)->seq))
3021                 return 0;
3022         packets_acked -= tcp_skb_pcount(skb);
3023
3024         if (packets_acked) {
3025                 BUG_ON(tcp_skb_pcount(skb) == 0);
3026                 BUG_ON(!before(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq));
3027         }
3028
3029         return packets_acked;
3030 }
3031
3032 /* Remove acknowledged frames from the retransmission queue. If our packet
3033  * is before the ack sequence we can discard it as it's confirmed to have
3034  * arrived at the other end.
3035  */
3036 static int tcp_clean_rtx_queue(struct sock *sk, int prior_fackets,
3037                                u32 prior_snd_una, long sack_rtt_us)
3038 {
3039         const struct inet_connection_sock *icsk = inet_csk(sk);
3040         struct skb_mstamp first_ackt, last_ackt, now;
3041         struct tcp_sock *tp = tcp_sk(sk);
3042         u32 prior_sacked = tp->sacked_out;
3043         u32 reord = tp->packets_out;
3044         bool fully_acked = true;
3045         long ca_seq_rtt_us = -1L;
3046         long seq_rtt_us = -1L;
3047         struct sk_buff *skb;
3048         u32 pkts_acked = 0;
3049         bool rtt_update;
3050         int flag = 0;
3051
3052         first_ackt.v64 = 0;
3053
3054         while ((skb = tcp_write_queue_head(sk)) && skb != tcp_send_head(sk)) {
3055                 struct skb_shared_info *shinfo = skb_shinfo(skb);
3056                 struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
3057                 u8 sacked = scb->sacked;
3058                 u32 acked_pcount;
3059
3060                 if (unlikely(shinfo->tx_flags & SKBTX_ACK_TSTAMP) &&
3061                     between(shinfo->tskey, prior_snd_una, tp->snd_una - 1))
3062                         __skb_tstamp_tx(skb, NULL, sk, SCM_TSTAMP_ACK);
3063
3064                 /* Determine how many packets and what bytes were acked, tso and else */
3065                 if (after(scb->end_seq, tp->snd_una)) {
3066                         if (tcp_skb_pcount(skb) == 1 ||
3067                             !after(tp->snd_una, scb->seq))
3068                                 break;
3069
3070                         acked_pcount = tcp_tso_acked(sk, skb);
3071                         if (!acked_pcount)
3072                                 break;
3073
3074                         fully_acked = false;
3075                 } else {
3076                         acked_pcount = tcp_skb_pcount(skb);
3077                 }
3078
3079                 if (sacked & TCPCB_RETRANS) {
3080                         if (sacked & TCPCB_SACKED_RETRANS)
3081                                 tp->retrans_out -= acked_pcount;
3082                         flag |= FLAG_RETRANS_DATA_ACKED;
3083                 } else {
3084                         last_ackt = skb->skb_mstamp;
3085                         WARN_ON_ONCE(last_ackt.v64 == 0);
3086                         if (!first_ackt.v64)
3087                                 first_ackt = last_ackt;
3088
3089                         if (!(sacked & TCPCB_SACKED_ACKED))
3090                                 reord = min(pkts_acked, reord);
3091                         if (!after(scb->end_seq, tp->high_seq))
3092                                 flag |= FLAG_ORIG_SACK_ACKED;
3093                 }
3094
3095                 if (sacked & TCPCB_SACKED_ACKED)
3096                         tp->sacked_out -= acked_pcount;
3097                 if (sacked & TCPCB_LOST)
3098                         tp->lost_out -= acked_pcount;
3099
3100                 tp->packets_out -= acked_pcount;
3101                 pkts_acked += acked_pcount;
3102
3103                 /* Initial outgoing SYN's get put onto the write_queue
3104                  * just like anything else we transmit.  It is not
3105                  * true data, and if we misinform our callers that
3106                  * this ACK acks real data, we will erroneously exit
3107                  * connection startup slow start one packet too
3108                  * quickly.  This is severely frowned upon behavior.
3109                  */
3110                 if (!(scb->tcp_flags & TCPHDR_SYN)) {
3111                         flag |= FLAG_DATA_ACKED;
3112                 } else {
3113                         flag |= FLAG_SYN_ACKED;
3114                         tp->retrans_stamp = 0;
3115                 }
3116
3117                 if (!fully_acked)
3118                         break;
3119
3120                 tcp_unlink_write_queue(skb, sk);
3121                 sk_wmem_free_skb(sk, skb);
3122                 if (skb == tp->retransmit_skb_hint)
3123                         tp->retransmit_skb_hint = NULL;
3124                 if (skb == tp->lost_skb_hint)
3125                         tp->lost_skb_hint = NULL;
3126         }
3127
3128         if (likely(between(tp->snd_up, prior_snd_una, tp->snd_una)))
3129                 tp->snd_up = tp->snd_una;
3130
3131         if (skb && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
3132                 flag |= FLAG_SACK_RENEGING;
3133
3134         skb_mstamp_get(&now);
3135         if (first_ackt.v64) {
3136                 seq_rtt_us = skb_mstamp_us_delta(&now, &first_ackt);
3137                 ca_seq_rtt_us = skb_mstamp_us_delta(&now, &last_ackt);
3138         }
3139
3140         rtt_update = tcp_ack_update_rtt(sk, flag, seq_rtt_us, sack_rtt_us);
3141
3142         if (flag & FLAG_ACKED) {
3143                 const struct tcp_congestion_ops *ca_ops
3144                         = inet_csk(sk)->icsk_ca_ops;
3145
3146                 tcp_rearm_rto(sk);
3147                 if (unlikely(icsk->icsk_mtup.probe_size &&
3148                              !after(tp->mtu_probe.probe_seq_end, tp->snd_una))) {
3149                         tcp_mtup_probe_success(sk);
3150                 }
3151
3152                 if (tcp_is_reno(tp)) {
3153                         tcp_remove_reno_sacks(sk, pkts_acked);
3154                 } else {
3155                         int delta;
3156
3157                         /* Non-retransmitted hole got filled? That's reordering */
3158                         if (reord < prior_fackets)
3159                                 tcp_update_reordering(sk, tp->fackets_out - reord, 0);
3160
3161                         delta = tcp_is_fack(tp) ? pkts_acked :
3162                                                   prior_sacked - tp->sacked_out;
3163                         tp->lost_cnt_hint -= min(tp->lost_cnt_hint, delta);
3164                 }
3165
3166                 tp->fackets_out -= min(pkts_acked, tp->fackets_out);
3167
3168                 if (ca_ops->pkts_acked)
3169                         ca_ops->pkts_acked(sk, pkts_acked, ca_seq_rtt_us);
3170
3171         } else if (skb && rtt_update && sack_rtt_us >= 0 &&
3172                    sack_rtt_us > skb_mstamp_us_delta(&now, &skb->skb_mstamp)) {
3173                 /* Do not re-arm RTO if the sack RTT is measured from data sent
3174                  * after when the head was last (re)transmitted. Otherwise the
3175                  * timeout may continue to extend in loss recovery.
3176                  */
3177                 tcp_rearm_rto(sk);
3178         }
3179
3180 #if FASTRETRANS_DEBUG > 0
3181         WARN_ON((int)tp->sacked_out < 0);
3182         WARN_ON((int)tp->lost_out < 0);
3183         WARN_ON((int)tp->retrans_out < 0);
3184         if (!tp->packets_out && tcp_is_sack(tp)) {
3185                 icsk = inet_csk(sk);
3186                 if (tp->lost_out) {
3187                         pr_debug("Leak l=%u %d\n",
3188                                  tp->lost_out, icsk->icsk_ca_state);
3189                         tp->lost_out = 0;
3190                 }
3191                 if (tp->sacked_out) {
3192                         pr_debug("Leak s=%u %d\n",
3193                                  tp->sacked_out, icsk->icsk_ca_state);
3194                         tp->sacked_out = 0;
3195                 }
3196                 if (tp->retrans_out) {
3197                         pr_debug("Leak r=%u %d\n",
3198                                  tp->retrans_out, icsk->icsk_ca_state);
3199                         tp->retrans_out = 0;
3200                 }
3201         }
3202 #endif
3203         return flag;
3204 }
3205
3206 static void tcp_ack_probe(struct sock *sk)
3207 {
3208         const struct tcp_sock *tp = tcp_sk(sk);
3209         struct inet_connection_sock *icsk = inet_csk(sk);
3210
3211         /* Was it a usable window open? */
3212
3213         if (!after(TCP_SKB_CB(tcp_send_head(sk))->end_seq, tcp_wnd_end(tp))) {
3214                 icsk->icsk_backoff = 0;
3215                 inet_csk_clear_xmit_timer(sk, ICSK_TIME_PROBE0);
3216                 /* Socket must be waked up by subsequent tcp_data_snd_check().
3217                  * This function is not for random using!
3218                  */
3219         } else {
3220                 unsigned long when = inet_csk_rto_backoff(icsk, TCP_RTO_MAX);
3221
3222                 inet_csk_reset_xmit_timer(sk, ICSK_TIME_PROBE0,
3223                                           when, TCP_RTO_MAX);
3224         }
3225 }
3226
3227 static inline bool tcp_ack_is_dubious(const struct sock *sk, const int flag)
3228 {
3229         return !(flag & FLAG_NOT_DUP) || (flag & FLAG_CA_ALERT) ||
3230                 inet_csk(sk)->icsk_ca_state != TCP_CA_Open;
3231 }
3232
3233 /* Decide wheather to run the increase function of congestion control. */
3234 static inline bool tcp_may_raise_cwnd(const struct sock *sk, const int flag)
3235 {
3236         if (tcp_in_cwnd_reduction(sk))
3237                 return false;
3238
3239         /* If reordering is high then always grow cwnd whenever data is
3240          * delivered regardless of its ordering. Otherwise stay conservative
3241          * and only grow cwnd on in-order delivery (RFC5681). A stretched ACK w/
3242          * new SACK or ECE mark may first advance cwnd here and later reduce
3243          * cwnd in tcp_fastretrans_alert() based on more states.
3244          */
3245         if (tcp_sk(sk)->reordering > sysctl_tcp_reordering)
3246                 return flag & FLAG_FORWARD_PROGRESS;
3247
3248         return flag & FLAG_DATA_ACKED;
3249 }
3250
3251 /* Check that window update is acceptable.
3252  * The function assumes that snd_una<=ack<=snd_next.
3253  */
3254 static inline bool tcp_may_update_window(const struct tcp_sock *tp,
3255                                         const u32 ack, const u32 ack_seq,
3256                                         const u32 nwin)
3257 {
3258         return  after(ack, tp->snd_una) ||
3259                 after(ack_seq, tp->snd_wl1) ||
3260                 (ack_seq == tp->snd_wl1 && nwin > tp->snd_wnd);
3261 }
3262
3263 /* Update our send window.
3264  *
3265  * Window update algorithm, described in RFC793/RFC1122 (used in linux-2.2
3266  * and in FreeBSD. NetBSD's one is even worse.) is wrong.
3267  */
3268 static int tcp_ack_update_window(struct sock *sk, const struct sk_buff *skb, u32 ack,
3269                                  u32 ack_seq)
3270 {
3271         struct tcp_sock *tp = tcp_sk(sk);
3272         int flag = 0;
3273         u32 nwin = ntohs(tcp_hdr(skb)->window);
3274
3275         if (likely(!tcp_hdr(skb)->syn))
3276                 nwin <<= tp->rx_opt.snd_wscale;
3277
3278         if (tcp_may_update_window(tp, ack, ack_seq, nwin)) {
3279                 flag |= FLAG_WIN_UPDATE;
3280                 tcp_update_wl(tp, ack_seq);
3281
3282                 if (tp->snd_wnd != nwin) {
3283                         tp->snd_wnd = nwin;
3284
3285                         /* Note, it is the only place, where
3286                          * fast path is recovered for sending TCP.
3287                          */
3288                         tp->pred_flags = 0;
3289                         tcp_fast_path_check(sk);
3290
3291                         if (nwin > tp->max_window) {
3292                                 tp->max_window = nwin;
3293                                 tcp_sync_mss(sk, inet_csk(sk)->icsk_pmtu_cookie);
3294                         }
3295                 }
3296         }
3297
3298         tp->snd_una = ack;
3299
3300         return flag;
3301 }
3302
3303 /* RFC 5961 7 [ACK Throttling] */
3304 static void tcp_send_challenge_ack(struct sock *sk)
3305 {
3306         /* unprotected vars, we dont care of overwrites */
3307         static u32 challenge_timestamp;
3308         static unsigned int challenge_count;
3309         u32 now = jiffies / HZ;
3310
3311         if (now != challenge_timestamp) {
3312                 challenge_timestamp = now;
3313                 challenge_count = 0;
3314         }
3315         if (++challenge_count <= sysctl_tcp_challenge_ack_limit) {
3316                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPCHALLENGEACK);
3317                 tcp_send_ack(sk);
3318         }
3319 }
3320
3321 static void tcp_store_ts_recent(struct tcp_sock *tp)
3322 {
3323         tp->rx_opt.ts_recent = tp->rx_opt.rcv_tsval;
3324         tp->rx_opt.ts_recent_stamp = get_seconds();
3325 }
3326
3327 static void tcp_replace_ts_recent(struct tcp_sock *tp, u32 seq)
3328 {
3329         if (tp->rx_opt.saw_tstamp && !after(seq, tp->rcv_wup)) {
3330                 /* PAWS bug workaround wrt. ACK frames, the PAWS discard
3331                  * extra check below makes sure this can only happen
3332                  * for pure ACK frames.  -DaveM
3333                  *
3334                  * Not only, also it occurs for expired timestamps.
3335                  */
3336
3337                 if (tcp_paws_check(&tp->rx_opt, 0))
3338                         tcp_store_ts_recent(tp);
3339         }
3340 }
3341
3342 /* This routine deals with acks during a TLP episode.
3343  * Ref: loss detection algorithm in draft-dukkipati-tcpm-tcp-loss-probe.
3344  */
3345 static void tcp_process_tlp_ack(struct sock *sk, u32 ack, int flag)
3346 {
3347         struct tcp_sock *tp = tcp_sk(sk);
3348         bool is_tlp_dupack = (ack == tp->tlp_high_seq) &&
3349                              !(flag & (FLAG_SND_UNA_ADVANCED |
3350                                        FLAG_NOT_DUP | FLAG_DATA_SACKED));
3351
3352         /* Mark the end of TLP episode on receiving TLP dupack or when
3353          * ack is after tlp_high_seq.
3354          */
3355         if (is_tlp_dupack) {
3356                 tp->tlp_high_seq = 0;
3357                 return;
3358         }
3359
3360         if (after(ack, tp->tlp_high_seq)) {
3361                 tp->tlp_high_seq = 0;
3362                 /* Don't reduce cwnd if DSACK arrives for TLP retrans. */
3363                 if (!(flag & FLAG_DSACKING_ACK)) {
3364                         tcp_init_cwnd_reduction(sk);
3365                         tcp_set_ca_state(sk, TCP_CA_CWR);
3366                         tcp_end_cwnd_reduction(sk);
3367                         tcp_try_keep_open(sk);
3368                         NET_INC_STATS_BH(sock_net(sk),
3369                                          LINUX_MIB_TCPLOSSPROBERECOVERY);
3370                 }
3371         }
3372 }
3373
3374 static inline void tcp_in_ack_event(struct sock *sk, u32 flags)
3375 {
3376         const struct inet_connection_sock *icsk = inet_csk(sk);
3377
3378         if (icsk->icsk_ca_ops->in_ack_event)
3379                 icsk->icsk_ca_ops->in_ack_event(sk, flags);
3380 }
3381
3382 /* This routine deals with incoming acks, but not outgoing ones. */
3383 static int tcp_ack(struct sock *sk, const struct sk_buff *skb, int flag)
3384 {
3385         struct inet_connection_sock *icsk = inet_csk(sk);
3386         struct tcp_sock *tp = tcp_sk(sk);
3387         u32 prior_snd_una = tp->snd_una;
3388         u32 ack_seq = TCP_SKB_CB(skb)->seq;
3389         u32 ack = TCP_SKB_CB(skb)->ack_seq;
3390         bool is_dupack = false;
3391         u32 prior_fackets;
3392         int prior_packets = tp->packets_out;
3393         const int prior_unsacked = tp->packets_out - tp->sacked_out;
3394         int acked = 0; /* Number of packets newly acked */
3395         long sack_rtt_us = -1L;
3396
3397         /* If the ack is older than previous acks
3398          * then we can probably ignore it.
3399          */
3400         if (before(ack, prior_snd_una)) {
3401                 /* RFC 5961 5.2 [Blind Data Injection Attack].[Mitigation] */
3402                 if (before(ack, prior_snd_una - tp->max_window)) {
3403                         tcp_send_challenge_ack(sk);
3404                         return -1;
3405                 }
3406                 goto old_ack;
3407         }
3408
3409         /* If the ack includes data we haven't sent yet, discard
3410          * this segment (RFC793 Section 3.9).
3411          */
3412         if (after(ack, tp->snd_nxt))
3413                 goto invalid_ack;
3414
3415         if (icsk->icsk_pending == ICSK_TIME_EARLY_RETRANS ||
3416             icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
3417                 tcp_rearm_rto(sk);
3418
3419         if (after(ack, prior_snd_una)) {
3420                 flag |= FLAG_SND_UNA_ADVANCED;
3421                 icsk->icsk_retransmits = 0;
3422         }
3423
3424         prior_fackets = tp->fackets_out;
3425
3426         /* ts_recent update must be made after we are sure that the packet
3427          * is in window.
3428          */
3429         if (flag & FLAG_UPDATE_TS_RECENT)
3430                 tcp_replace_ts_recent(tp, TCP_SKB_CB(skb)->seq);
3431
3432         if (!(flag & FLAG_SLOWPATH) && after(ack, prior_snd_una)) {
3433                 /* Window is constant, pure forward advance.
3434                  * No more checks are required.
3435                  * Note, we use the fact that SND.UNA>=SND.WL2.
3436                  */
3437                 tcp_update_wl(tp, ack_seq);
3438                 tp->snd_una = ack;
3439                 flag |= FLAG_WIN_UPDATE;
3440
3441                 tcp_in_ack_event(sk, CA_ACK_WIN_UPDATE);
3442
3443                 NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPHPACKS);
3444         } else {
3445                 u32 ack_ev_flags = CA_ACK_SLOWPATH;
3446
3447                 if (ack_seq != TCP_SKB_CB(skb)->end_seq)
3448                         flag |= FLAG_DATA;
3449                 else
3450                         NET_INC_STATS_BH(sock_net(sk), LINUX_MIB_TCPPUREACKS);
3451
3452                 flag |= tcp_ack_update_window(sk, skb, ack, ack_seq);
3453
3454                 if (TCP_SKB_CB(skb)->sacked)
3455                         flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una,
3456                                                         &sack_rtt_us);
3457
3458                 if (tcp_ecn_rcv_ecn_echo(tp, tcp_hdr(skb))) {
3459                         flag |= FLAG_ECE;
3460                         ack_ev_flags |= CA_ACK_ECE;
3461                 }
3462
3463                 if (flag & FLAG_WIN_UPDATE)
3464                         ack_ev_flags |= CA_ACK_WIN_UPDATE;
3465
3466                 tcp_in_ack_event(sk, ack_ev_flags);
3467         }
3468
3469         /* We passed data and got it acked, remove any soft error
3470          * log. Something worked...
3471          */
3472         sk->sk_err_soft = 0;
3473         icsk->icsk_probes_out = 0;
3474         tp->rcv_tstamp = tcp_time_stamp;
3475         if (!prior_packets)
3476                 goto no_queue;
3477
3478         /* See if we can take anything off of the retransmit queue. */
3479         acked = tp->packets_out;
3480         flag |= tcp_clean_rtx_queue(sk, prior_fackets, prior_snd_una,
3481                                     sack_rtt_us);
3482         acked -= tp->packets_out;
3483
3484         /* Advance cwnd if state allows */
3485         if (tcp_may_raise_cwnd(sk, flag))
3486                 tcp_cong_avoid(sk, ack, acked);
3487
3488         if (tcp_ack_is_dubious(sk, flag)) {
3489                 is_dupack = !(flag & (FLAG_SND_UNA_ADVANCED | FLAG_NOT_DUP));
3490                 tcp_fastretrans_alert(sk, acked, prior_unsacked,
3491                                       is_dupack, flag);
3492         }
3493         if (tp->tlp_high_seq)
3494                 tcp_process_tlp_ack(sk, ack, flag);
3495
3496         if ((flag & FLAG_FORWARD_PROGRESS) || !(flag & FLAG_NOT_DUP)) {
3497                 struct dst_entry *dst = __sk_dst_get(sk);
3498                 if (dst)
3499                         dst_confirm(dst);
3500         }
3501
3502         if (icsk->icsk_pending == ICSK_TIME_RETRANS)
3503                 tcp_schedule_loss_probe(sk);
3504         tcp_update_pacing_rate(sk);
3505         return 1;
3506
3507 no_queue:
3508         /* If data was DSACKed, see if we can undo a cwnd reduction. */
3509         if (flag & FLAG_DSACKING_ACK)
3510                 tcp_fastretrans_alert(sk, acked, prior_unsacked,
3511                                       is_dupack, flag);
3512         /* If this ack opens up a zero window, clear backoff.  It was
3513          * being used to time the probes, and is probably far higher than
3514          * it needs to be for normal retransmission.
3515          */
3516         if (tcp_send_head(sk))
3517                 tcp_ack_probe(sk);
3518
3519         if (tp->tlp_high_seq)
3520                 tcp_process_tlp_ack(sk, ack, flag);
3521         return 1;
3522
3523 invalid_ack:
3524         SOCK_DEBUG(sk, "Ack %u after %u:%u\n", ack, tp->snd_una, tp->snd_nxt);
3525         return -1;
3526
3527 old_ack:
3528         /* If data was SACKed, tag it and see if we should send more data.
3529          * If data was DSACKed, see if we can undo a cwnd reduction.
3530          */
3531         if (TCP_SKB_CB(skb)->sacked) {
3532                 flag |= tcp_sacktag_write_queue(sk, skb, prior_snd_una,
3533                                               &nb