[BRIDGE]: Use cpu_to_be16() where appropriate.
[safe/jmp/linux-2.6] / net / ipv4 / tcp_input.c
index 4238ed9..bc2d5f7 100644 (file)
@@ -85,7 +85,7 @@ int sysctl_tcp_adv_win_scale __read_mostly = 2;
 int sysctl_tcp_stdurg __read_mostly;
 int sysctl_tcp_rfc1337 __read_mostly;
 int sysctl_tcp_max_orphans __read_mostly = NR_FILE;
-int sysctl_tcp_frto __read_mostly;
+int sysctl_tcp_frto __read_mostly = 2;
 int sysctl_tcp_frto_response __read_mostly;
 int sysctl_tcp_nometrics_save __read_mostly;
 
@@ -103,7 +103,8 @@ int sysctl_tcp_abc __read_mostly;
 #define FLAG_SLOWPATH          0x100 /* Do not skip RFC checks for window update.*/
 #define FLAG_ONLY_ORIG_SACKED  0x200 /* SACKs only non-rexmit sent before RTO */
 #define FLAG_SND_UNA_ADVANCED  0x400 /* Snd_una was changed (!= FLAG_DATA_ACKED) */
-#define FLAG_DSACKING_ACK      0x800 /* SACK blocks contained DSACK info */
+#define FLAG_DSACKING_ACK      0x800 /* SACK blocks contained D-SACK info */
+#define FLAG_NONHEAD_RETRANS_ACKED     0x1000 /* Non-head rexmitted data was ACKed */
 
 #define FLAG_ACKED             (FLAG_DATA_ACKED|FLAG_SYN_ACKED)
 #define FLAG_NOT_DUP           (FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)
@@ -862,10 +863,13 @@ void tcp_enter_cwr(struct sock *sk, const int set_ssthresh)
  */
 static void tcp_disable_fack(struct tcp_sock *tp)
 {
+       /* RFC3517 uses different metric in lost marker => reset on change */
+       if (tcp_is_fack(tp))
+               tp->lost_skb_hint = NULL;
        tp->rx_opt.sack_ok &= ~2;
 }
 
-/* Take a notice that peer is sending DSACKs */
+/* Take a notice that peer is sending D-SACKs */
 static void tcp_dsack_seen(struct tcp_sock *tp)
 {
        tp->rx_opt.sack_ok |= 4;
@@ -922,7 +926,7 @@ static void tcp_init_metrics(struct sock *sk)
        }
        if (dst_metric(dst, RTAX_RTTVAR) > tp->mdev) {
                tp->mdev = dst_metric(dst, RTAX_RTTVAR);
-               tp->mdev_max = tp->rttvar = max(tp->mdev, TCP_RTO_MIN);
+               tp->mdev_max = tp->rttvar = max(tp->mdev, tcp_rto_min(sk));
        }
        tcp_set_rto(sk);
        tcp_bound_rto(sk);
@@ -1026,8 +1030,15 @@ static void tcp_update_reordering(struct sock *sk, const int metric,
  * SACK block range validation checks that the received SACK block fits to
  * the expected sequence limits, i.e., it is between SND.UNA and SND.NXT.
  * Note that SND.UNA is not included to the range though being valid because
- * it means that the receiver is rather inconsistent with itself (reports
- * SACK reneging when it should advance SND.UNA).
+ * it means that the receiver is rather inconsistent with itself reporting
+ * SACK reneging when it should advance SND.UNA. Such SACK block this is
+ * perfectly valid, however, in light of RFC2018 which explicitly states
+ * that "SACK block MUST reflect the newest segment.  Even if the newest
+ * segment is going to be discarded ...", not that it looks very clever
+ * in case of head skb. Due to potentional receiver driven attacks, we
+ * choose to avoid immediate execution of a walk in write queue due to
+ * reneging and defer head skb's loss recovery to standard loss recovery
+ * procedure that will eventually trigger (nothing forbids us doing this).
  *
  * Implements also blockage to start_seq wrap-around. Problem lies in the
  * fact that though start_seq (s) is before end_seq (i.e., not reversed),
@@ -1050,7 +1061,7 @@ static void tcp_update_reordering(struct sock *sk, const int metric,
  *
  * With D-SACK the lower bound is extended to cover sequence space below
  * SND.UNA down to undo_marker, which is the last point of interest. Yet
- * again, DSACK block must not to go across snd_una (for the same reason as
+ * again, D-SACK block must not to go across snd_una (for the same reason as
  * for the normal SACK blocks, explained above). But there all simplicity
  * ends, TCP might receive valid D-SACKs below that. As long as they reside
  * fully below undo_marker they do not affect behavior in anyway and can
@@ -1072,7 +1083,7 @@ static int tcp_is_sackblock_valid(struct tcp_sock *tp, int is_dsack,
        if (!before(start_seq, tp->snd_nxt))
                return 0;
 
-       /* In outstanding window? ...This is valid exit for DSACKs too.
+       /* In outstanding window? ...This is valid exit for D-SACKs too.
         * start_seq == snd_una is non-sensical (see comments above)
         */
        if (after(start_seq, tp->snd_una))
@@ -1098,6 +1109,67 @@ static int tcp_is_sackblock_valid(struct tcp_sock *tp, int is_dsack,
        return !before(start_seq, end_seq - tp->max_window);
 }
 
+/* Check for lost retransmit. This superb idea is borrowed from "ratehalving".
+ * Event "C". Later note: FACK people cheated me again 8), we have to account
+ * for reordering! Ugly, but should help.
+ *
+ * Search retransmitted skbs from write_queue that were sent when snd_nxt was
+ * less than what is now known to be received by the other end (derived from
+ * highest SACK block). Also calculate the lowest snd_nxt among the remaining
+ * retransmitted skbs to avoid some costly processing per ACKs.
+ */
+static void tcp_mark_lost_retrans(struct sock *sk)
+{
+       const struct inet_connection_sock *icsk = inet_csk(sk);
+       struct tcp_sock *tp = tcp_sk(sk);
+       struct sk_buff *skb;
+       int cnt = 0;
+       u32 new_low_seq = tp->snd_nxt;
+       u32 received_upto = tcp_highest_sack_seq(tp);
+
+       if (!tcp_is_fack(tp) || !tp->retrans_out ||
+           !after(received_upto, tp->lost_retrans_low) ||
+           icsk->icsk_ca_state != TCP_CA_Recovery)
+               return;
+
+       tcp_for_write_queue(skb, sk) {
+               u32 ack_seq = TCP_SKB_CB(skb)->ack_seq;
+
+               if (skb == tcp_send_head(sk))
+                       break;
+               if (cnt == tp->retrans_out)
+                       break;
+               if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
+                       continue;
+
+               if (!(TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS))
+                       continue;
+
+               if (after(received_upto, ack_seq) &&
+                   (tcp_is_fack(tp) ||
+                    !before(received_upto,
+                            ack_seq + tp->reordering * tp->mss_cache))) {
+                       TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
+                       tp->retrans_out -= tcp_skb_pcount(skb);
+
+                       /* clear lost hint */
+                       tp->retransmit_skb_hint = NULL;
+
+                       if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_LOST|TCPCB_SACKED_ACKED))) {
+                               tp->lost_out += tcp_skb_pcount(skb);
+                               TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
+                       }
+                       NET_INC_STATS_BH(LINUX_MIB_TCPLOSTRETRANSMIT);
+               } else {
+                       if (before(ack_seq, new_low_seq))
+                               new_low_seq = ack_seq;
+                       cnt += tcp_skb_pcount(skb);
+               }
+       }
+
+       if (tp->retrans_out)
+               tp->lost_retrans_low = new_low_seq;
+}
 
 static int tcp_check_dsack(struct tcp_sock *tp, struct sk_buff *ack_skb,
                           struct tcp_sack_block_wire *sp, int num_sacks,
@@ -1132,6 +1204,207 @@ static int tcp_check_dsack(struct tcp_sock *tp, struct sk_buff *ack_skb,
        return dup_sack;
 }
 
+/* Check if skb is fully within the SACK block. In presence of GSO skbs,
+ * the incoming SACK may not exactly match but we can find smaller MSS
+ * aligned portion of it that matches. Therefore we might need to fragment
+ * which may fail and creates some hassle (caller must handle error case
+ * returns).
+ */
+static int tcp_match_skb_to_sack(struct sock *sk, struct sk_buff *skb,
+                                u32 start_seq, u32 end_seq)
+{
+       int in_sack, err;
+       unsigned int pkt_len;
+
+       in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
+                 !before(end_seq, TCP_SKB_CB(skb)->end_seq);
+
+       if (tcp_skb_pcount(skb) > 1 && !in_sack &&
+           after(TCP_SKB_CB(skb)->end_seq, start_seq)) {
+
+               in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq);
+
+               if (!in_sack)
+                       pkt_len = start_seq - TCP_SKB_CB(skb)->seq;
+               else
+                       pkt_len = end_seq - TCP_SKB_CB(skb)->seq;
+               err = tcp_fragment(sk, skb, pkt_len, skb_shinfo(skb)->gso_size);
+               if (err < 0)
+                       return err;
+       }
+
+       return in_sack;
+}
+
+static int tcp_sacktag_one(struct sk_buff *skb, struct sock *sk,
+                          int *reord, int dup_sack, int fack_count)
+{
+       struct tcp_sock *tp = tcp_sk(sk);
+       u8 sacked = TCP_SKB_CB(skb)->sacked;
+       int flag = 0;
+
+       /* Account D-SACK for retransmitted packet. */
+       if (dup_sack && (sacked & TCPCB_RETRANS)) {
+               if (after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker))
+                       tp->undo_retrans--;
+               if (sacked & TCPCB_SACKED_ACKED)
+                       *reord = min(fack_count, *reord);
+       }
+
+       /* Nothing to do; acked frame is about to be dropped (was ACKed). */
+       if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
+               return flag;
+
+       if (!(sacked & TCPCB_SACKED_ACKED)) {
+               if (sacked & TCPCB_SACKED_RETRANS) {
+                       /* If the segment is not tagged as lost,
+                        * we do not clear RETRANS, believing
+                        * that retransmission is still in flight.
+                        */
+                       if (sacked & TCPCB_LOST) {
+                               TCP_SKB_CB(skb)->sacked &=
+                                       ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
+                               tp->lost_out -= tcp_skb_pcount(skb);
+                               tp->retrans_out -= tcp_skb_pcount(skb);
+
+                               /* clear lost hint */
+                               tp->retransmit_skb_hint = NULL;
+                       }
+               } else {
+                       if (!(sacked & TCPCB_RETRANS)) {
+                               /* New sack for not retransmitted frame,
+                                * which was in hole. It is reordering.
+                                */
+                               if (before(TCP_SKB_CB(skb)->seq,
+                                          tcp_highest_sack_seq(tp)))
+                                       *reord = min(fack_count, *reord);
+
+                               /* SACK enhanced F-RTO (RFC4138; Appendix B) */
+                               if (!after(TCP_SKB_CB(skb)->end_seq, tp->frto_highmark))
+                                       flag |= FLAG_ONLY_ORIG_SACKED;
+                       }
+
+                       if (sacked & TCPCB_LOST) {
+                               TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
+                               tp->lost_out -= tcp_skb_pcount(skb);
+
+                               /* clear lost hint */
+                               tp->retransmit_skb_hint = NULL;
+                       }
+               }
+
+               TCP_SKB_CB(skb)->sacked |= TCPCB_SACKED_ACKED;
+               flag |= FLAG_DATA_SACKED;
+               tp->sacked_out += tcp_skb_pcount(skb);
+
+               fack_count += tcp_skb_pcount(skb);
+
+               /* Lost marker hint past SACKed? Tweak RFC3517 cnt */
+               if (!tcp_is_fack(tp) && (tp->lost_skb_hint != NULL) &&
+                   before(TCP_SKB_CB(skb)->seq,
+                          TCP_SKB_CB(tp->lost_skb_hint)->seq))
+                       tp->lost_cnt_hint += tcp_skb_pcount(skb);
+
+               if (fack_count > tp->fackets_out)
+                       tp->fackets_out = fack_count;
+
+               if (!before(TCP_SKB_CB(skb)->seq, tcp_highest_sack_seq(tp)))
+                       tcp_advance_highest_sack(sk, skb);
+       }
+
+       /* D-SACK. We can detect redundant retransmission in S|R and plain R
+        * frames and clear it. undo_retrans is decreased above, L|R frames
+        * are accounted above as well.
+        */
+       if (dup_sack && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS)) {
+               TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
+               tp->retrans_out -= tcp_skb_pcount(skb);
+               tp->retransmit_skb_hint = NULL;
+       }
+
+       return flag;
+}
+
+static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk,
+                                       struct tcp_sack_block *next_dup,
+                                       u32 start_seq, u32 end_seq,
+                                       int dup_sack_in, int *fack_count,
+                                       int *reord, int *flag)
+{
+       tcp_for_write_queue_from(skb, sk) {
+               int in_sack = 0;
+               int dup_sack = dup_sack_in;
+
+               if (skb == tcp_send_head(sk))
+                       break;
+
+               /* queue is in-order => we can short-circuit the walk early */
+               if (!before(TCP_SKB_CB(skb)->seq, end_seq))
+                       break;
+
+               if ((next_dup != NULL) &&
+                   before(TCP_SKB_CB(skb)->seq, next_dup->end_seq)) {
+                       in_sack = tcp_match_skb_to_sack(sk, skb,
+                                                       next_dup->start_seq,
+                                                       next_dup->end_seq);
+                       if (in_sack > 0)
+                               dup_sack = 1;
+               }
+
+               if (in_sack <= 0)
+                       in_sack = tcp_match_skb_to_sack(sk, skb, start_seq, end_seq);
+               if (unlikely(in_sack < 0))
+                       break;
+
+               if (in_sack)
+                       *flag |= tcp_sacktag_one(skb, sk, reord, dup_sack, *fack_count);
+
+               *fack_count += tcp_skb_pcount(skb);
+       }
+       return skb;
+}
+
+/* Avoid all extra work that is being done by sacktag while walking in
+ * a normal way
+ */
+static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk,
+                                       u32 skip_to_seq)
+{
+       tcp_for_write_queue_from(skb, sk) {
+               if (skb == tcp_send_head(sk))
+                       break;
+
+               if (!before(TCP_SKB_CB(skb)->end_seq, skip_to_seq))
+                       break;
+       }
+       return skb;
+}
+
+static struct sk_buff *tcp_maybe_skipping_dsack(struct sk_buff *skb,
+                                               struct sock *sk,
+                                               struct tcp_sack_block *next_dup,
+                                               u32 skip_to_seq,
+                                               int *fack_count, int *reord,
+                                               int *flag)
+{
+       if (next_dup == NULL)
+               return skb;
+
+       if (before(next_dup->start_seq, skip_to_seq)) {
+               skb = tcp_sacktag_skip(skb, sk, next_dup->start_seq);
+               tcp_sacktag_walk(skb, sk, NULL,
+                                next_dup->start_seq, next_dup->end_seq,
+                                1, fack_count, reord, flag);
+       }
+
+       return skb;
+}
+
+static int tcp_sack_cache_ok(struct tcp_sock *tp, struct tcp_sack_block *cache)
+{
+       return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
+}
+
 static int
 tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_una)
 {
@@ -1139,25 +1412,26 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
        struct tcp_sock *tp = tcp_sk(sk);
        unsigned char *ptr = (skb_transport_header(ack_skb) +
                              TCP_SKB_CB(ack_skb)->sacked);
-       struct tcp_sack_block_wire *sp = (struct tcp_sack_block_wire *)(ptr+2);
-       struct sk_buff *cached_skb;
+       struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *)(ptr+2);
+       struct tcp_sack_block sp[4];
+       struct tcp_sack_block *cache;
+       struct sk_buff *skb;
        int num_sacks = (ptr[1] - TCPOLEN_SACK_BASE)>>3;
+       int used_sacks;
        int reord = tp->packets_out;
-       int prior_fackets;
-       u32 lost_retrans = 0;
        int flag = 0;
        int found_dup_sack = 0;
-       int cached_fack_count;
-       int i;
+       int fack_count;
+       int i, j;
        int first_sack_index;
 
        if (!tp->sacked_out) {
-               tp->fackets_out = 0;
-               tp->highest_sack = tp->snd_una;
+               if (WARN_ON(tp->fackets_out))
+                       tp->fackets_out = 0;
+               tcp_highest_sack_reset(sk);
        }
-       prior_fackets = tp->fackets_out;
 
-       found_dup_sack = tcp_check_dsack(tp, ack_skb, sp,
+       found_dup_sack = tcp_check_dsack(tp, ack_skb, sp_wire,
                                         num_sacks, prior_snd_una);
        if (found_dup_sack)
                flag |= FLAG_DSACKING_ACK;
@@ -1169,288 +1443,170 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
        if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
                return 0;
 
-       /* SACK fastpath:
-        * if the only SACK change is the increase of the end_seq of
-        * the first block then only apply that SACK block
-        * and use retrans queue hinting otherwise slowpath */
-       flag = 1;
-       for (i = 0; i < num_sacks; i++) {
-               __be32 start_seq = sp[i].start_seq;
-               __be32 end_seq = sp[i].end_seq;
-
-               if (i == 0) {
-                       if (tp->recv_sack_cache[i].start_seq != start_seq)
-                               flag = 0;
-               } else {
-                       if ((tp->recv_sack_cache[i].start_seq != start_seq) ||
-                           (tp->recv_sack_cache[i].end_seq != end_seq))
-                               flag = 0;
-               }
-               tp->recv_sack_cache[i].start_seq = start_seq;
-               tp->recv_sack_cache[i].end_seq = end_seq;
-       }
-       /* Clear the rest of the cache sack blocks so they won't match mistakenly. */
-       for (; i < ARRAY_SIZE(tp->recv_sack_cache); i++) {
-               tp->recv_sack_cache[i].start_seq = 0;
-               tp->recv_sack_cache[i].end_seq = 0;
-       }
+       if (!tp->packets_out)
+               goto out;
 
+       used_sacks = 0;
        first_sack_index = 0;
-       if (flag)
-               num_sacks = 1;
-       else {
-               int j;
-               tp->fastpath_skb_hint = NULL;
-
-               /* order SACK blocks to allow in order walk of the retrans queue */
-               for (i = num_sacks-1; i > 0; i--) {
-                       for (j = 0; j < i; j++){
-                               if (after(ntohl(sp[j].start_seq),
-                                         ntohl(sp[j+1].start_seq))){
-                                       struct tcp_sack_block_wire tmp;
-
-                                       tmp = sp[j];
-                                       sp[j] = sp[j+1];
-                                       sp[j+1] = tmp;
-
-                                       /* Track where the first SACK block goes to */
-                                       if (j == first_sack_index)
-                                               first_sack_index = j+1;
-                               }
-
-                       }
-               }
-       }
-
-       /* clear flag as used for different purpose in following code */
-       flag = 0;
-
-       /* Use SACK fastpath hint if valid */
-       cached_skb = tp->fastpath_skb_hint;
-       cached_fack_count = tp->fastpath_cnt_hint;
-       if (!cached_skb) {
-               cached_skb = tcp_write_queue_head(sk);
-               cached_fack_count = 0;
-       }
+       for (i = 0; i < num_sacks; i++) {
+               int dup_sack = !i && found_dup_sack;
 
-       for (i=0; i<num_sacks; i++, sp++) {
-               struct sk_buff *skb;
-               __u32 start_seq = ntohl(sp->start_seq);
-               __u32 end_seq = ntohl(sp->end_seq);
-               int fack_count;
-               int dup_sack = (found_dup_sack && (i == first_sack_index));
+               sp[used_sacks].start_seq = ntohl(get_unaligned(&sp_wire[i].start_seq));
+               sp[used_sacks].end_seq = ntohl(get_unaligned(&sp_wire[i].end_seq));
 
-               if (!tcp_is_sackblock_valid(tp, dup_sack, start_seq, end_seq)) {
+               if (!tcp_is_sackblock_valid(tp, dup_sack,
+                                           sp[used_sacks].start_seq,
+                                           sp[used_sacks].end_seq)) {
                        if (dup_sack) {
                                if (!tp->undo_marker)
                                        NET_INC_STATS_BH(LINUX_MIB_TCPDSACKIGNOREDNOUNDO);
                                else
                                        NET_INC_STATS_BH(LINUX_MIB_TCPDSACKIGNOREDOLD);
-                       } else
+                       } else {
+                               /* Don't count olds caused by ACK reordering */
+                               if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) &&
+                                   !after(sp[used_sacks].end_seq, tp->snd_una))
+                                       continue;
                                NET_INC_STATS_BH(LINUX_MIB_TCPSACKDISCARD);
+                       }
+                       if (i == 0)
+                               first_sack_index = -1;
                        continue;
                }
 
-               skb = cached_skb;
-               fack_count = cached_fack_count;
+               /* Ignore very old stuff early */
+               if (!after(sp[used_sacks].end_seq, prior_snd_una))
+                       continue;
 
-               /* Event "B" in the comment above. */
-               if (after(end_seq, tp->high_seq))
-                       flag |= FLAG_DATA_LOST;
+               used_sacks++;
+       }
 
-               tcp_for_write_queue_from(skb, sk) {
-                       int in_sack, pcount;
-                       u8 sacked;
+       /* order SACK blocks to allow in order walk of the retrans queue */
+       for (i = used_sacks - 1; i > 0; i--) {
+               for (j = 0; j < i; j++){
+                       if (after(sp[j].start_seq, sp[j+1].start_seq)) {
+                               struct tcp_sack_block tmp;
 
-                       if (skb == tcp_send_head(sk))
-                               break;
+                               tmp = sp[j];
+                               sp[j] = sp[j+1];
+                               sp[j+1] = tmp;
 
-                       cached_skb = skb;
-                       cached_fack_count = fack_count;
-                       if (i == first_sack_index) {
-                               tp->fastpath_skb_hint = skb;
-                               tp->fastpath_cnt_hint = fack_count;
+                               /* Track where the first SACK block goes to */
+                               if (j == first_sack_index)
+                                       first_sack_index = j+1;
                        }
+               }
+       }
 
-                       /* The retransmission queue is always in order, so
-                        * we can short-circuit the walk early.
-                        */
-                       if (!before(TCP_SKB_CB(skb)->seq, end_seq))
-                               break;
-
-                       in_sack = !after(start_seq, TCP_SKB_CB(skb)->seq) &&
-                               !before(end_seq, TCP_SKB_CB(skb)->end_seq);
-
-                       pcount = tcp_skb_pcount(skb);
+       skb = tcp_write_queue_head(sk);
+       fack_count = 0;
+       i = 0;
 
-                       if (pcount > 1 && !in_sack &&
-                           after(TCP_SKB_CB(skb)->end_seq, start_seq)) {
-                               unsigned int pkt_len;
+       if (!tp->sacked_out) {
+               /* It's already past, so skip checking against it */
+               cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
+       } else {
+               cache = tp->recv_sack_cache;
+               /* Skip empty blocks in at head of the cache */
+               while (tcp_sack_cache_ok(tp, cache) && !cache->start_seq &&
+                      !cache->end_seq)
+                       cache++;
+       }
 
-                               in_sack = !after(start_seq,
-                                                TCP_SKB_CB(skb)->seq);
+       while (i < used_sacks) {
+               u32 start_seq = sp[i].start_seq;
+               u32 end_seq = sp[i].end_seq;
+               int dup_sack = (found_dup_sack && (i == first_sack_index));
+               struct tcp_sack_block *next_dup = NULL;
 
-                               if (!in_sack)
-                                       pkt_len = (start_seq -
-                                                  TCP_SKB_CB(skb)->seq);
-                               else
-                                       pkt_len = (end_seq -
-                                                  TCP_SKB_CB(skb)->seq);
-                               if (tcp_fragment(sk, skb, pkt_len, skb_shinfo(skb)->gso_size))
-                                       break;
-                               pcount = tcp_skb_pcount(skb);
-                       }
+               if (found_dup_sack && ((i + 1) == first_sack_index))
+                       next_dup = &sp[i + 1];
 
-                       fack_count += pcount;
-
-                       sacked = TCP_SKB_CB(skb)->sacked;
-
-                       /* Account D-SACK for retransmitted packet. */
-                       if ((dup_sack && in_sack) &&
-                           (sacked & TCPCB_RETRANS) &&
-                           after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker))
-                               tp->undo_retrans--;
-
-                       /* The frame is ACKed. */
-                       if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) {
-                               if (sacked&TCPCB_RETRANS) {
-                                       if ((dup_sack && in_sack) &&
-                                           (sacked&TCPCB_SACKED_ACKED))
-                                               reord = min(fack_count, reord);
-                               } else {
-                                       /* If it was in a hole, we detected reordering. */
-                                       if (fack_count < prior_fackets &&
-                                           !(sacked&TCPCB_SACKED_ACKED))
-                                               reord = min(fack_count, reord);
-                               }
+               /* Event "B" in the comment above. */
+               if (after(end_seq, tp->high_seq))
+                       flag |= FLAG_DATA_LOST;
 
-                               /* Nothing to do; acked frame is about to be dropped. */
-                               continue;
+               /* Skip too early cached blocks */
+               while (tcp_sack_cache_ok(tp, cache) &&
+                      !before(start_seq, cache->end_seq))
+                       cache++;
+
+               /* Can skip some work by looking recv_sack_cache? */
+               if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
+                   after(end_seq, cache->start_seq)) {
+
+                       /* Head todo? */
+                       if (before(start_seq, cache->start_seq)) {
+                               skb = tcp_sacktag_skip(skb, sk, start_seq);
+                               skb = tcp_sacktag_walk(skb, sk, next_dup, start_seq,
+                                                      cache->start_seq, dup_sack,
+                                                      &fack_count, &reord, &flag);
                        }
 
-                       if ((sacked&TCPCB_SACKED_RETRANS) &&
-                           after(end_seq, TCP_SKB_CB(skb)->ack_seq) &&
-                           (!lost_retrans || after(end_seq, lost_retrans)))
-                               lost_retrans = end_seq;
-
-                       if (!in_sack)
-                               continue;
-
-                       if (!(sacked&TCPCB_SACKED_ACKED)) {
-                               if (sacked & TCPCB_SACKED_RETRANS) {
-                                       /* If the segment is not tagged as lost,
-                                        * we do not clear RETRANS, believing
-                                        * that retransmission is still in flight.
-                                        */
-                                       if (sacked & TCPCB_LOST) {
-                                               TCP_SKB_CB(skb)->sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
-                                               tp->lost_out -= tcp_skb_pcount(skb);
-                                               tp->retrans_out -= tcp_skb_pcount(skb);
-
-                                               /* clear lost hint */
-                                               tp->retransmit_skb_hint = NULL;
-                                       }
-                               } else {
-                                       /* New sack for not retransmitted frame,
-                                        * which was in hole. It is reordering.
-                                        */
-                                       if (!(sacked & TCPCB_RETRANS) &&
-                                           fack_count < prior_fackets)
-                                               reord = min(fack_count, reord);
-
-                                       if (sacked & TCPCB_LOST) {
-                                               TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
-                                               tp->lost_out -= tcp_skb_pcount(skb);
-
-                                               /* clear lost hint */
-                                               tp->retransmit_skb_hint = NULL;
-                                       }
-                                       /* SACK enhanced F-RTO detection.
-                                        * Set flag if and only if non-rexmitted
-                                        * segments below frto_highmark are
-                                        * SACKed (RFC4138; Appendix B).
-                                        * Clearing correct due to in-order walk
-                                        */
-                                       if (after(end_seq, tp->frto_highmark)) {
-                                               flag &= ~FLAG_ONLY_ORIG_SACKED;
-                                       } else {
-                                               if (!(sacked & TCPCB_RETRANS))
-                                                       flag |= FLAG_ONLY_ORIG_SACKED;
-                                       }
-                               }
-
-                               TCP_SKB_CB(skb)->sacked |= TCPCB_SACKED_ACKED;
-                               flag |= FLAG_DATA_SACKED;
-                               tp->sacked_out += tcp_skb_pcount(skb);
+                       /* Rest of the block already fully processed? */
+                       if (!after(end_seq, cache->end_seq))
+                               goto advance_sp;
 
-                               if (fack_count > tp->fackets_out)
-                                       tp->fackets_out = fack_count;
+                       skb = tcp_maybe_skipping_dsack(skb, sk, next_dup, cache->end_seq,
+                                                      &fack_count, &reord, &flag);
 
-                               if (after(TCP_SKB_CB(skb)->seq,
-                                   tp->highest_sack))
-                                       tp->highest_sack = TCP_SKB_CB(skb)->seq;
-                       } else {
-                               if (dup_sack && (sacked&TCPCB_RETRANS))
-                                       reord = min(fack_count, reord);
+                       /* ...tail remains todo... */
+                       if (tcp_highest_sack_seq(tp) == cache->end_seq) {
+                               /* ...but better entrypoint exists! */
+                               skb = tcp_highest_sack(sk);
+                               if (skb == NULL)
+                                       break;
+                               fack_count = tp->fackets_out;
+                               cache++;
+                               goto walk;
                        }
 
-                       /* D-SACK. We can detect redundant retransmission
-                        * in S|R and plain R frames and clear it.
-                        * undo_retrans is decreased above, L|R frames
-                        * are accounted above as well.
-                        */
-                       if (dup_sack &&
-                           (TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_RETRANS)) {
-                               TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
-                               tp->retrans_out -= tcp_skb_pcount(skb);
-                               tp->retransmit_skb_hint = NULL;
-                       }
+                       skb = tcp_sacktag_skip(skb, sk, cache->end_seq);
+                       /* Check overlap against next cached too (past this one already) */
+                       cache++;
+                       continue;
                }
-       }
-
-       /* Check for lost retransmit. This superb idea is
-        * borrowed from "ratehalving". Event "C".
-        * Later note: FACK people cheated me again 8),
-        * we have to account for reordering! Ugly,
-        * but should help.
-        */
-       if (lost_retrans && icsk->icsk_ca_state == TCP_CA_Recovery) {
-               struct sk_buff *skb;
 
-               tcp_for_write_queue(skb, sk) {
-                       if (skb == tcp_send_head(sk))
+               if (!before(start_seq, tcp_highest_sack_seq(tp))) {
+                       skb = tcp_highest_sack(sk);
+                       if (skb == NULL)
                                break;
-                       if (after(TCP_SKB_CB(skb)->seq, lost_retrans))
-                               break;
-                       if (!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una))
-                               continue;
-                       if ((TCP_SKB_CB(skb)->sacked&TCPCB_SACKED_RETRANS) &&
-                           after(lost_retrans, TCP_SKB_CB(skb)->ack_seq) &&
-                           (tcp_is_fack(tp) ||
-                            !before(lost_retrans,
-                                    TCP_SKB_CB(skb)->ack_seq + tp->reordering *
-                                    tp->mss_cache))) {
-                               TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
-                               tp->retrans_out -= tcp_skb_pcount(skb);
+                       fack_count = tp->fackets_out;
+               }
+               skb = tcp_sacktag_skip(skb, sk, start_seq);
 
-                               /* clear lost hint */
-                               tp->retransmit_skb_hint = NULL;
+walk:
+               skb = tcp_sacktag_walk(skb, sk, next_dup, start_seq, end_seq,
+                                      dup_sack, &fack_count, &reord, &flag);
 
-                               if (!(TCP_SKB_CB(skb)->sacked&(TCPCB_LOST|TCPCB_SACKED_ACKED))) {
-                                       tp->lost_out += tcp_skb_pcount(skb);
-                                       TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
-                                       flag |= FLAG_DATA_SACKED;
-                                       NET_INC_STATS_BH(LINUX_MIB_TCPLOSTRETRANSMIT);
-                               }
-                       }
-               }
+advance_sp:
+               /* SACK enhanced FRTO (RFC4138, Appendix B): Clearing correct
+                * due to in-order walk
+                */
+               if (after(end_seq, tp->frto_highmark))
+                       flag &= ~FLAG_ONLY_ORIG_SACKED;
+
+               i++;
        }
 
+       /* Clear the head of the cache sack blocks so we can skip it next time */
+       for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) {
+               tp->recv_sack_cache[i].start_seq = 0;
+               tp->recv_sack_cache[i].end_seq = 0;
+       }
+       for (j = 0; j < used_sacks; j++)
+               tp->recv_sack_cache[i++] = sp[j];
+
+       tcp_mark_lost_retrans(sk);
+
        tcp_verify_left_out(tp);
 
-       if ((reord < tp->fackets_out) && icsk->icsk_ca_state != TCP_CA_Loss &&
+       if ((reord < tp->fackets_out) &&
+           ((icsk->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker) &&
            (!tp->frto_highmark || after(tp->snd_una, tp->frto_highmark)))
-               tcp_update_reordering(sk, ((tp->fackets_out + 1) - reord), 0);
+               tcp_update_reordering(sk, tp->fackets_out - reord, 0);
+
+out:
 
 #if FASTRETRANS_DEBUG > 0
        BUG_TRAP((int)tp->sacked_out >= 0);
@@ -1461,8 +1617,9 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
        return flag;
 }
 
-/* F-RTO can only be used if TCP has never retransmitted anything other than
- * head (SACK enhanced variant from Appendix B of RFC4138 is more robust here)
+/* If we receive more dupacks than we expected counting segments
+ * in assumption of absent reordering, interpret this as reordering.
+ * The only another reason could be bug in receiver TCP.
  */
 static void tcp_check_reno_reordering(struct sock *sk, const int addend)
 {
@@ -1510,6 +1667,9 @@ static inline void tcp_reset_reno_sack(struct tcp_sock *tp)
        tp->sacked_out = 0;
 }
 
+/* F-RTO can only be used if TCP has never retransmitted anything other than
+ * head (SACK enhanced variant from Appendix B of RFC4138 is more robust here)
+ */
 int tcp_use_frto(struct sock *sk)
 {
        const struct tcp_sock *tp = tcp_sk(sk);
@@ -1563,7 +1723,7 @@ void tcp_enter_frto(struct sock *sk)
             !icsk->icsk_retransmits)) {
                tp->prior_ssthresh = tcp_current_ssthresh(sk);
                /* Our state is too optimistic in ssthresh() call because cwnd
-                * is not reduced until tcp_enter_frto_loss() when previous FRTO
+                * is not reduced until tcp_enter_frto_loss() when previous F-RTO
                 * recovery has not yet completed. Pattern would be this: RTO,
                 * Cumulative ACK, RTO (2xRTO for the same segment does not end
                 * up here twice).
@@ -1594,12 +1754,17 @@ void tcp_enter_frto(struct sock *sk)
        tp->undo_retrans = 0;
 
        skb = tcp_write_queue_head(sk);
+       if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
+               tp->undo_marker = 0;
        if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) {
                TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
                tp->retrans_out -= tcp_skb_pcount(skb);
        }
        tcp_verify_left_out(tp);
 
+       /* Too bad if TCP was application limited */
+       tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp) + 1);
+
        /* Earlier loss recovery underway (see RFC4138; Appendix B).
         * The last condition is necessary at least in tp->frto_counter case.
         */
@@ -1632,6 +1797,8 @@ static void tcp_enter_frto_loss(struct sock *sk, int allowed_segments, int flag)
        tcp_for_write_queue(skb, sk) {
                if (skb == tcp_send_head(sk))
                        break;
+
+               TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
                /*
                 * Count the retransmission made on RTO correctly (only when
                 * waiting for the first ACK and did not get it)...
@@ -1643,7 +1810,9 @@ static void tcp_enter_frto_loss(struct sock *sk, int allowed_segments, int flag)
                        /* ...enter this if branch just for the first segment */
                        flag |= FLAG_DATA_ACKED;
                } else {
-                       TCP_SKB_CB(skb)->sacked &= ~(TCPCB_LOST|TCPCB_SACKED_RETRANS);
+                       if (TCP_SKB_CB(skb)->sacked & TCPCB_RETRANS)
+                               tp->undo_marker = 0;
+                       TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
                }
 
                /* Don't lost mark skbs that were fwd transmitted after RTO */
@@ -1658,8 +1827,8 @@ static void tcp_enter_frto_loss(struct sock *sk, int allowed_segments, int flag)
        tp->snd_cwnd = tcp_packets_in_flight(tp) + allowed_segments;
        tp->snd_cwnd_cnt = 0;
        tp->snd_cwnd_stamp = tcp_time_stamp;
-       tp->undo_marker = 0;
        tp->frto_counter = 0;
+       tp->bytes_acked = 0;
 
        tp->reordering = min_t(unsigned int, tp->reordering,
                                             sysctl_tcp_reordering);
@@ -1667,21 +1836,26 @@ static void tcp_enter_frto_loss(struct sock *sk, int allowed_segments, int flag)
        tp->high_seq = tp->frto_highmark;
        TCP_ECN_queue_cwr(tp);
 
-       tcp_clear_all_retrans_hints(tp);
+       tcp_clear_retrans_hints_partial(tp);
 }
 
-void tcp_clear_retrans(struct tcp_sock *tp)
+static void tcp_clear_retrans_partial(struct tcp_sock *tp)
 {
        tp->retrans_out = 0;
-
-       tp->fackets_out = 0;
-       tp->sacked_out = 0;
        tp->lost_out = 0;
 
        tp->undo_marker = 0;
        tp->undo_retrans = 0;
 }
 
+void tcp_clear_retrans(struct tcp_sock *tp)
+{
+       tcp_clear_retrans_partial(tp);
+
+       tp->fackets_out = 0;
+       tp->sacked_out = 0;
+}
+
 /* Enter Loss state. If "how" is not zero, forget all SACK information
  * and reset tags completely, otherwise preserve SACKs. If receiver
  * dropped its ofo queue, we will know this due to reneging detection.
@@ -1691,7 +1865,6 @@ void tcp_enter_loss(struct sock *sk, int how)
        const struct inet_connection_sock *icsk = inet_csk(sk);
        struct tcp_sock *tp = tcp_sk(sk);
        struct sk_buff *skb;
-       int cnt = 0;
 
        /* Reduce ssthresh if it has not yet been made inside this window. */
        if (icsk->icsk_ca_state <= TCP_CA_Disorder || tp->snd_una == tp->high_seq ||
@@ -1705,17 +1878,26 @@ void tcp_enter_loss(struct sock *sk, int how)
        tp->snd_cwnd_stamp = tcp_time_stamp;
 
        tp->bytes_acked = 0;
-       tcp_clear_retrans(tp);
+       tcp_clear_retrans_partial(tp);
+
+       if (tcp_is_reno(tp))
+               tcp_reset_reno_sack(tp);
 
-       /* Push undo marker, if it was plain RTO and nothing
-        * was retransmitted. */
-       if (!how)
+       if (!how) {
+               /* Push undo marker, if it was plain RTO and nothing
+                * was retransmitted. */
                tp->undo_marker = tp->snd_una;
+               tcp_clear_retrans_hints_partial(tp);
+       } else {
+               tp->sacked_out = 0;
+               tp->fackets_out = 0;
+               tcp_clear_all_retrans_hints(tp);
+       }
 
        tcp_for_write_queue(skb, sk) {
                if (skb == tcp_send_head(sk))
                        break;
-               cnt += tcp_skb_pcount(skb);
+
                if (TCP_SKB_CB(skb)->sacked&TCPCB_RETRANS)
                        tp->undo_marker = 0;
                TCP_SKB_CB(skb)->sacked &= (~TCPCB_TAGBITS)|TCPCB_SACKED_ACKED;
@@ -1723,9 +1905,6 @@ void tcp_enter_loss(struct sock *sk, int how)
                        TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_ACKED;
                        TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
                        tp->lost_out += tcp_skb_pcount(skb);
-               } else {
-                       tp->sacked_out += tcp_skb_pcount(skb);
-                       tp->fackets_out = cnt;
                }
        }
        tcp_verify_left_out(tp);
@@ -1735,10 +1914,8 @@ void tcp_enter_loss(struct sock *sk, int how)
        tcp_set_ca_state(sk, TCP_CA_Loss);
        tp->high_seq = tp->snd_nxt;
        TCP_ECN_queue_cwr(tp);
-       /* Abort FRTO algorithm if one is in progress */
+       /* Abort F-RTO algorithm if one is in progress */
        tp->frto_counter = 0;
-
-       tcp_clear_all_retrans_hints(tp);
 }
 
 static int tcp_check_sack_reneging(struct sock *sk)
@@ -1771,6 +1948,26 @@ static inline int tcp_fackets_out(struct tcp_sock *tp)
        return tcp_is_reno(tp) ? tp->sacked_out+1 : tp->fackets_out;
 }
 
+/* Heurestics to calculate number of duplicate ACKs. There's no dupACKs
+ * counter when SACK is enabled (without SACK, sacked_out is used for
+ * that purpose).
+ *
+ * Instead, with FACK TCP uses fackets_out that includes both SACKed
+ * segments up to the highest received SACK block so far and holes in
+ * between them.
+ *
+ * With reordering, holes may still be in flight, so RFC3517 recovery
+ * uses pure sacked_out (total number of SACKed segments) even though
+ * it violates the RFC that uses duplicate ACKs, often these are equal
+ * but when e.g. out-of-window ACKs or packet duplication occurs,
+ * they differ. Since neither occurs due to loss, TCP should really
+ * ignore them.
+ */
+static inline int tcp_dupack_heurestics(struct tcp_sock *tp)
+{
+       return tcp_is_fack(tp) ? tp->fackets_out : tp->sacked_out + 1;
+}
+
 static inline int tcp_skb_timedout(struct sock *sk, struct sk_buff *skb)
 {
        return (tcp_time_stamp - TCP_SKB_CB(skb)->when > inet_csk(sk)->icsk_rto);
@@ -1882,7 +2079,7 @@ static int tcp_time_to_recover(struct sock *sk)
        struct tcp_sock *tp = tcp_sk(sk);
        __u32 packets_out;
 
-       /* Do not perform any recovery during FRTO algorithm */
+       /* Do not perform any recovery during F-RTO algorithm */
        if (tp->frto_counter)
                return 0;
 
@@ -1891,13 +2088,13 @@ static int tcp_time_to_recover(struct sock *sk)
                return 1;
 
        /* Not-A-Trick#2 : Classic rule... */
-       if (tcp_fackets_out(tp) > tp->reordering)
+       if (tcp_dupack_heurestics(tp) > tp->reordering)
                return 1;
 
        /* Trick#3 : when we use RFC2988 timer restart, fast
         * retransmit can be triggered by timeout of queue head.
         */
-       if (tcp_head_timedout(sk))
+       if (tcp_is_fack(tp) && tcp_head_timedout(sk))
                return 1;
 
        /* Trick#4: It is still not OK... But will it be useful to delay
@@ -1930,9 +2127,10 @@ static void tcp_verify_retransmit_hint(struct tcp_sock *tp,
                tp->retransmit_skb_hint = NULL;
 }
 
-/* Mark head of queue up as lost. */
-static void tcp_mark_head_lost(struct sock *sk,
-                              int packets, u32 high_seq)
+/* Mark head of queue up as lost. With RFC3517 SACK, the packets is
+ * is against sacked "cnt", otherwise it's against facked "cnt"
+ */
+static void tcp_mark_head_lost(struct sock *sk, int packets, int fast_rexmit)
 {
        struct tcp_sock *tp = tcp_sk(sk);
        struct sk_buff *skb;
@@ -1954,10 +2152,15 @@ static void tcp_mark_head_lost(struct sock *sk,
                /* this is not the most efficient way to do this... */
                tp->lost_skb_hint = skb;
                tp->lost_cnt_hint = cnt;
-               cnt += tcp_skb_pcount(skb);
-               if (cnt > packets || after(TCP_SKB_CB(skb)->end_seq, high_seq))
+
+               if (tcp_is_fack(tp) ||
+                   (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED))
+                       cnt += tcp_skb_pcount(skb);
+
+               if (((!fast_rexmit || (tp->lost_out > 0)) && (cnt > packets)) ||
+                    after(TCP_SKB_CB(skb)->end_seq, tp->high_seq))
                        break;
-               if (!(TCP_SKB_CB(skb)->sacked&TCPCB_TAGBITS)) {
+               if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_SACKED_ACKED|TCPCB_LOST))) {
                        TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
                        tp->lost_out += tcp_skb_pcount(skb);
                        tcp_verify_retransmit_hint(tp, skb);
@@ -1968,17 +2171,22 @@ static void tcp_mark_head_lost(struct sock *sk,
 
 /* Account newly detected lost packet(s) */
 
-static void tcp_update_scoreboard(struct sock *sk)
+static void tcp_update_scoreboard(struct sock *sk, int fast_rexmit)
 {
        struct tcp_sock *tp = tcp_sk(sk);
 
-       if (tcp_is_fack(tp)) {
+       if (tcp_is_reno(tp)) {
+               tcp_mark_head_lost(sk, 1, fast_rexmit);
+       } else if (tcp_is_fack(tp)) {
                int lost = tp->fackets_out - tp->reordering;
                if (lost <= 0)
                        lost = 1;
-               tcp_mark_head_lost(sk, lost, tp->high_seq);
+               tcp_mark_head_lost(sk, lost, fast_rexmit);
        } else {
-               tcp_mark_head_lost(sk, 1, tp->high_seq);
+               int sacked_upto = tp->sacked_out - tp->reordering;
+               if (sacked_upto < 0)
+                       sacked_upto = 0;
+               tcp_mark_head_lost(sk, sacked_upto, fast_rexmit);
        }
 
        /* New heuristics: it is possible only after we switched
@@ -1986,7 +2194,7 @@ static void tcp_update_scoreboard(struct sock *sk)
         * Hence, we can detect timed out packets during fast
         * retransmit without falling to slow start.
         */
-       if (!tcp_is_reno(tp) && tcp_head_timedout(sk)) {
+       if (tcp_is_fack(tp) && tcp_head_timedout(sk)) {
                struct sk_buff *skb;
 
                skb = tp->scoreboard_skb_hint ? tp->scoreboard_skb_hint
@@ -1998,7 +2206,7 @@ static void tcp_update_scoreboard(struct sock *sk)
                        if (!tcp_skb_timedout(sk, skb))
                                break;
 
-                       if (!(TCP_SKB_CB(skb)->sacked&TCPCB_TAGBITS)) {
+                       if (!(TCP_SKB_CB(skb)->sacked & (TCPCB_SACKED_ACKED|TCPCB_LOST))) {
                                TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;
                                tp->lost_out += tcp_skb_pcount(skb);
                                tcp_verify_retransmit_hint(tp, skb);
@@ -2159,7 +2367,7 @@ static int tcp_try_undo_partial(struct sock *sk, int acked)
 {
        struct tcp_sock *tp = tcp_sk(sk);
        /* Partial ACK arrived. Force Hoe's retransmit. */
-       int failed = tcp_is_reno(tp) || tp->fackets_out>tp->reordering;
+       int failed = tcp_is_reno(tp) || (tcp_fackets_out(tp) > tp->reordering);
 
        if (tcp_may_undo(tp)) {
                /* Plain luck! Hole if filled with delayed
@@ -2293,7 +2501,8 @@ tcp_fastretrans_alert(struct sock *sk, int pkts_acked, int flag)
        struct tcp_sock *tp = tcp_sk(sk);
        int is_dupack = !(flag&(FLAG_SND_UNA_ADVANCED|FLAG_NOT_DUP));
        int do_lost = is_dupack || ((flag&FLAG_DATA_SACKED) &&
-                                   (tp->fackets_out > tp->reordering));
+                                   (tcp_fackets_out(tp) > tp->reordering));
+       int fast_rexmit = 0;
 
        /* Some technical things:
         * 1. Reno does not count dupacks (sacked_out) automatically. */
@@ -2313,11 +2522,11 @@ tcp_fastretrans_alert(struct sock *sk, int pkts_acked, int flag)
                return;
 
        /* C. Process data loss notification, provided it is valid. */
-       if ((flag&FLAG_DATA_LOST) &&
+       if (tcp_is_fack(tp) && (flag & FLAG_DATA_LOST) &&
            before(tp->snd_una, tp->high_seq) &&
            icsk->icsk_ca_state != TCP_CA_Open &&
            tp->fackets_out > tp->reordering) {
-               tcp_mark_head_lost(sk, tp->fackets_out-tp->reordering, tp->high_seq);
+               tcp_mark_head_lost(sk, tp->fackets_out-tp->reordering, 0);
                NET_INC_STATS_BH(LINUX_MIB_TCPLOSS);
        }
 
@@ -2436,10 +2645,11 @@ tcp_fastretrans_alert(struct sock *sk, int pkts_acked, int flag)
                tp->bytes_acked = 0;
                tp->snd_cwnd_cnt = 0;
                tcp_set_ca_state(sk, TCP_CA_Recovery);
+               fast_rexmit = 1;
        }
 
-       if (do_lost || tcp_head_timedout(sk))
-               tcp_update_scoreboard(sk);
+       if (do_lost || (tcp_is_fack(tp) && tcp_head_timedout(sk)))
+               tcp_update_scoreboard(sk, fast_rexmit);
        tcp_cwnd_down(sk, flag);
        tcp_xmit_retransmit_queue(sk);
 }
@@ -2503,11 +2713,10 @@ static inline void tcp_ack_update_rtt(struct sock *sk, const int flag,
                tcp_ack_no_tstamp(sk, seq_rtt, flag);
 }
 
-static void tcp_cong_avoid(struct sock *sk, u32 ack,
-                          u32 in_flight, int good)
+static void tcp_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
 {
        const struct inet_connection_sock *icsk = inet_csk(sk);
-       icsk->icsk_ca_ops->cong_avoid(sk, ack, in_flight, good);
+       icsk->icsk_ca_ops->cong_avoid(sk, ack, in_flight);
        tcp_sk(sk)->snd_cwnd_stamp = tcp_time_stamp;
 }
 
@@ -2525,71 +2734,106 @@ static void tcp_rearm_rto(struct sock *sk)
        }
 }
 
+/* If we get here, the whole TSO packet has not been acked. */
 static u32 tcp_tso_acked(struct sock *sk, struct sk_buff *skb)
 {
        struct tcp_sock *tp = tcp_sk(sk);
-       struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
-       __u32 seq = tp->snd_una;
-       __u32 packets_acked;
+       u32 packets_acked;
 
-       /* If we get here, the whole TSO packet has not been
-        * acked.
-        */
-       BUG_ON(!after(scb->end_seq, seq));
+       BUG_ON(!after(TCP_SKB_CB(skb)->end_seq, tp->snd_una));
 
        packets_acked = tcp_skb_pcount(skb);
-       if (tcp_trim_head(sk, skb, seq - scb->seq))
+       if (tcp_trim_head(sk, skb, tp->snd_una - TCP_SKB_CB(skb)->seq))
                return 0;
        packets_acked -= tcp_skb_pcount(skb);
 
        if (packets_acked) {
                BUG_ON(tcp_skb_pcount(skb) == 0);
-               BUG_ON(!before(scb->seq, scb->end_seq));
+               BUG_ON(!before(TCP_SKB_CB(skb)->seq, TCP_SKB_CB(skb)->end_seq));
        }
 
        return packets_acked;
 }
 
-/* Remove acknowledged frames from the retransmission queue. */
-static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p)
+/* Remove acknowledged frames from the retransmission queue. If our packet
+ * is before the ack sequence we can discard it as it's confirmed to have
+ * arrived at the other end.
+ */
+static int tcp_clean_rtx_queue(struct sock *sk, s32 *seq_rtt_p,
+                              int prior_fackets)
 {
        struct tcp_sock *tp = tcp_sk(sk);
        const struct inet_connection_sock *icsk = inet_csk(sk);
        struct sk_buff *skb;
-       __u32 now = tcp_time_stamp;
+       u32 now = tcp_time_stamp;
        int fully_acked = 1;
-       int acked = 0;
-       int prior_packets = tp->packets_out;
-       __s32 seq_rtt = -1;
+       int flag = 0;
+       u32 pkts_acked = 0;
+       u32 reord = tp->packets_out;
+       s32 seq_rtt = -1;
+       s32 ca_seq_rtt = -1;
        ktime_t last_ackt = net_invalid_timestamp();
 
-       while ((skb = tcp_write_queue_head(sk)) &&
-              skb != tcp_send_head(sk)) {
+       while ((skb = tcp_write_queue_head(sk)) && skb != tcp_send_head(sk)) {
                struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
                u32 end_seq;
-               u32 packets_acked;
-               __u8 sacked = scb->sacked;
+               u32 acked_pcount;
+               u8 sacked = scb->sacked;
 
-               /* If our packet is before the ack sequence we can
-                * discard it as it's confirmed to have arrived at
-                * the other end.
-                */
+               /* Determine how many packets and what bytes were acked, tso and else */
                if (after(scb->end_seq, tp->snd_una)) {
                        if (tcp_skb_pcount(skb) == 1 ||
                            !after(tp->snd_una, scb->seq))
                                break;
 
-                       packets_acked = tcp_tso_acked(sk, skb);
-                       if (!packets_acked)
+                       acked_pcount = tcp_tso_acked(sk, skb);
+                       if (!acked_pcount)
                                break;
 
                        fully_acked = 0;
                        end_seq = tp->snd_una;
                } else {
-                       packets_acked = tcp_skb_pcount(skb);
+                       acked_pcount = tcp_skb_pcount(skb);
                        end_seq = scb->end_seq;
                }
 
+               /* MTU probing checks */
+               if (fully_acked && icsk->icsk_mtup.probe_size &&
+                   !after(tp->mtu_probe.probe_seq_end, scb->end_seq)) {
+                       tcp_mtup_probe_success(sk, skb);
+               }
+
+               if (sacked & TCPCB_RETRANS) {
+                       if (sacked & TCPCB_SACKED_RETRANS)
+                               tp->retrans_out -= acked_pcount;
+                       flag |= FLAG_RETRANS_DATA_ACKED;
+                       ca_seq_rtt = -1;
+                       seq_rtt = -1;
+                       if ((flag & FLAG_DATA_ACKED) ||
+                           (acked_pcount > 1))
+                               flag |= FLAG_NONHEAD_RETRANS_ACKED;
+               } else {
+                       ca_seq_rtt = now - scb->when;
+                       last_ackt = skb->tstamp;
+                       if (seq_rtt < 0) {
+                               seq_rtt = ca_seq_rtt;
+                       }
+                       if (!(sacked & TCPCB_SACKED_ACKED))
+                               reord = min(pkts_acked, reord);
+               }
+
+               if (sacked & TCPCB_SACKED_ACKED)
+                       tp->sacked_out -= acked_pcount;
+               if (sacked & TCPCB_LOST)
+                       tp->lost_out -= acked_pcount;
+
+               if (unlikely((sacked & TCPCB_URG) && tp->urg_mode &&
+                            !before(end_seq, tp->snd_up)))
+                       tp->urg_mode = 0;
+
+               tp->packets_out -= acked_pcount;
+               pkts_acked += acked_pcount;
+
                /* Initial outgoing SYN's get put onto the write_queue
                 * just like anything else we transmit.  It is not
                 * true data, and if we misinform our callers that
@@ -2598,45 +2842,12 @@ static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p)
                 * quickly.  This is severely frowned upon behavior.
                 */
                if (!(scb->flags & TCPCB_FLAG_SYN)) {
-                       acked |= FLAG_DATA_ACKED;
+                       flag |= FLAG_DATA_ACKED;
                } else {
-                       acked |= FLAG_SYN_ACKED;
+                       flag |= FLAG_SYN_ACKED;
                        tp->retrans_stamp = 0;
                }
 
-               /* MTU probing checks */
-               if (fully_acked && icsk->icsk_mtup.probe_size) {
-                       if (!after(tp->mtu_probe.probe_seq_end, TCP_SKB_CB(skb)->end_seq)) {
-                               tcp_mtup_probe_success(sk, skb);
-                       }
-               }
-
-               if (sacked) {
-                       if (sacked & TCPCB_RETRANS) {
-                               if (sacked & TCPCB_SACKED_RETRANS)
-                                       tp->retrans_out -= packets_acked;
-                               acked |= FLAG_RETRANS_DATA_ACKED;
-                               seq_rtt = -1;
-                       } else if (seq_rtt < 0) {
-                               seq_rtt = now - scb->when;
-                               if (fully_acked)
-                                       last_ackt = skb->tstamp;
-                       }
-                       if (sacked & TCPCB_SACKED_ACKED)
-                               tp->sacked_out -= packets_acked;
-                       if (sacked & TCPCB_LOST)
-                               tp->lost_out -= packets_acked;
-                       if (sacked & TCPCB_URG) {
-                               if (tp->urg_mode && !before(end_seq, tp->snd_up))
-                                       tp->urg_mode = 0;
-                       }
-               } else if (seq_rtt < 0) {
-                       seq_rtt = now - scb->when;
-                       if (fully_acked)
-                               last_ackt = skb->tstamp;
-               }
-               tp->packets_out -= packets_acked;
-
                if (!fully_acked)
                        break;
 
@@ -2645,34 +2856,36 @@ static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p)
                tcp_clear_all_retrans_hints(tp);
        }
 
-       if (acked&FLAG_ACKED) {
-               u32 pkts_acked = prior_packets - tp->packets_out;
+       if (flag & FLAG_ACKED) {
                const struct tcp_congestion_ops *ca_ops
                        = inet_csk(sk)->icsk_ca_ops;
 
-               tcp_ack_update_rtt(sk, acked, seq_rtt);
+               tcp_ack_update_rtt(sk, flag, seq_rtt);
                tcp_rearm_rto(sk);
 
-               tp->fackets_out -= min(pkts_acked, tp->fackets_out);
-               /* hint's skb might be NULL but we don't need to care */
-               tp->fastpath_cnt_hint -= min_t(u32, pkts_acked,
-                                              tp->fastpath_cnt_hint);
-               if (tcp_is_reno(tp))
+               if (tcp_is_reno(tp)) {
                        tcp_remove_reno_sacks(sk, pkts_acked);
+               } else {
+                       /* Non-retransmitted hole got filled? That's reordering */
+                       if (reord < prior_fackets)
+                               tcp_update_reordering(sk, tp->fackets_out - reord, 0);
+               }
+
+               tp->fackets_out -= min(pkts_acked, tp->fackets_out);
 
                if (ca_ops->pkts_acked) {
                        s32 rtt_us = -1;
 
                        /* Is the ACK triggering packet unambiguous? */
-                       if (!(acked & FLAG_RETRANS_DATA_ACKED)) {
+                       if (!(flag & FLAG_RETRANS_DATA_ACKED)) {
                                /* High resolution needed and available? */
                                if (ca_ops->flags & TCP_CONG_RTT_STAMP &&
                                    !ktime_equal(last_ackt,
                                                 net_invalid_timestamp()))
                                        rtt_us = ktime_us_delta(ktime_get_real(),
                                                                last_ackt);
-                               else if (seq_rtt > 0)
-                                       rtt_us = jiffies_to_usecs(seq_rtt);
+                               else if (ca_seq_rtt > 0)
+                                       rtt_us = jiffies_to_usecs(ca_seq_rtt);
                        }
 
                        ca_ops->pkts_acked(sk, pkts_acked, rtt_us);
@@ -2684,7 +2897,7 @@ static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p)
        BUG_TRAP((int)tp->lost_out >= 0);
        BUG_TRAP((int)tp->retrans_out >= 0);
        if (!tp->packets_out && tcp_is_sack(tp)) {
-               const struct inet_connection_sock *icsk = inet_csk(sk);
+               icsk = inet_csk(sk);
                if (tp->lost_out) {
                        printk(KERN_DEBUG "Leak l=%u %d\n",
                               tp->lost_out, icsk->icsk_ca_state);
@@ -2703,7 +2916,7 @@ static int tcp_clean_rtx_queue(struct sock *sk, __s32 *seq_rtt_p)
        }
 #endif
        *seq_rtt_p = seq_rtt;
-       return acked;
+       return flag;
 }
 
 static void tcp_ack_probe(struct sock *sk)
@@ -2798,6 +3011,7 @@ static void tcp_conservative_spur_to_response(struct tcp_sock *tp)
 {
        tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);
        tp->snd_cwnd_cnt = 0;
+       tp->bytes_acked = 0;
        TCP_ECN_queue_cwr(tp);
        tcp_moderate_cwnd(tp);
 }
@@ -2858,6 +3072,10 @@ static int tcp_process_frto(struct sock *sk, int flag)
        if (flag&FLAG_DATA_ACKED)
                inet_csk(sk)->icsk_retransmits = 0;
 
+       if ((flag & FLAG_NONHEAD_RETRANS_ACKED) ||
+           ((tp->frto_counter >= 2) && (flag & FLAG_RETRANS_DATA_ACKED)))
+               tp->undo_marker = 0;
+
        if (!before(tp->snd_una, tp->frto_highmark)) {
                tcp_enter_frto_loss(sk, (tp->frto_counter == 1 ? 2 : 3), flag);
                return 1;
@@ -2897,17 +3115,13 @@ static int tcp_process_frto(struct sock *sk, int flag)
        }
 
        if (tp->frto_counter == 1) {
-               /* Sending of the next skb must be allowed or no FRTO */
-               if (!tcp_send_head(sk) ||
-                   after(TCP_SKB_CB(tcp_send_head(sk))->end_seq,
-                                    tp->snd_una + tp->snd_wnd)) {
-                       tcp_enter_frto_loss(sk, (tp->frto_counter == 1 ? 2 : 3),
-                                           flag);
-                       return 1;
-               }
-
+               /* tcp_may_send_now needs to see updated state */
                tp->snd_cwnd = tcp_packets_in_flight(tp) + 2;
                tp->frto_counter = 2;
+
+               if (!tcp_may_send_now(sk))
+                       tcp_enter_frto_loss(sk, 2, flag);
+
                return 1;
        } else {
                switch (sysctl_tcp_frto_response) {
@@ -2922,6 +3136,8 @@ static int tcp_process_frto(struct sock *sk, int flag)
                        break;
                }
                tp->frto_counter = 0;
+               tp->undo_marker = 0;
+               NET_INC_STATS_BH(LINUX_MIB_TCPSPURIOUSRTOS);
        }
        return 0;
 }
@@ -2935,6 +3151,7 @@ static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag)
        u32 ack_seq = TCP_SKB_CB(skb)->seq;
        u32 ack = TCP_SKB_CB(skb)->ack_seq;
        u32 prior_in_flight;
+       u32 prior_fackets;
        s32 seq_rtt;
        int prior_packets;
        int frto_cwnd = 0;
@@ -2959,6 +3176,9 @@ static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag)
                        tp->bytes_acked += min(ack - prior_snd_una, tp->mss_cache);
        }
 
+       prior_fackets = tp->fackets_out;
+       prior_in_flight = tcp_packets_in_flight(tp);
+
        if (!(flag&FLAG_SLOWPATH) && after(ack, prior_snd_una)) {
                /* Window is constant, pure forward advance.
                 * No more checks are required.
@@ -2997,23 +3217,24 @@ static int tcp_ack(struct sock *sk, struct sk_buff *skb, int flag)
        if (!prior_packets)
                goto no_queue;
 
-       prior_in_flight = tcp_packets_in_flight(tp);
-
        /* See if we can take anything off of the retransmit queue. */
-       flag |= tcp_clean_rtx_queue(sk, &seq_rtt);
+       flag |= tcp_clean_rtx_queue(sk, &seq_rtt, prior_fackets);
 
        if (tp->frto_counter)
                frto_cwnd = tcp_process_frto(sk, flag);
+       /* Guarantee sacktag reordering detection against wrap-arounds */
+       if (before(tp->frto_highmark, tp->snd_una))
+               tp->frto_highmark = 0;
 
        if (tcp_ack_is_dubious(sk, flag)) {
                /* Advance CWND, if state allows this. */
                if ((flag & FLAG_DATA_ACKED) && !frto_cwnd &&
                    tcp_may_raise_cwnd(sk, flag))
-                       tcp_cong_avoid(sk, ack, prior_in_flight, 0);
+                       tcp_cong_avoid(sk, ack, prior_in_flight);
                tcp_fastretrans_alert(sk, prior_packets - tp->packets_out, flag);
        } else {
                if ((flag & FLAG_DATA_ACKED) && !frto_cwnd)
-                       tcp_cong_avoid(sk, ack, prior_in_flight, 1);
+                       tcp_cong_avoid(sk, ack, prior_in_flight);
        }
 
        if ((flag & FLAG_FORWARD_PROGRESS) || !(flag&FLAG_NOT_DUP))
@@ -3357,9 +3578,9 @@ static void tcp_fin(struct sk_buff *skb, struct sock *sk, struct tcphdr *th)
                /* Do not send POLL_HUP for half duplex close. */
                if (sk->sk_shutdown == SHUTDOWN_MASK ||
                    sk->sk_state == TCP_CLOSE)
-                       sk_wake_async(sk, 1, POLL_HUP);
+                       sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_HUP);
                else
-                       sk_wake_async(sk, 1, POLL_IN);
+                       sk_wake_async(sk, SOCK_WAKE_WAITD, POLL_IN);
        }
 }
 
@@ -3839,7 +4060,7 @@ tcp_collapse(struct sock *sk, struct sk_buff_head *list,
 
        while (before(start, end)) {
                struct sk_buff *nskb;
-               int header = skb_headroom(skb);
+               unsigned int header = skb_headroom(skb);
                int copy = SKB_MAX_ORDER(header, 0);
 
                /* Too big header? This can happen with IPv6. */
@@ -4718,7 +4939,7 @@ static int tcp_rcv_synsent_state_process(struct sock *sk, struct sk_buff *skb,
 
                if (!sock_flag(sk, SOCK_DEAD)) {
                        sk->sk_state_change(sk);
-                       sk_wake_async(sk, 0, POLL_OUT);
+                       sk_wake_async(sk, SOCK_WAKE_IO, POLL_OUT);
                }
 
                if (sk->sk_write_pending ||
@@ -4948,9 +5169,9 @@ int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb,
                                 * are not waked up, because sk->sk_sleep ==
                                 * NULL and sk->sk_socket == NULL.
                                 */
-                               if (sk->sk_socket) {
-                                       sk_wake_async(sk,0,POLL_OUT);
-                               }
+                               if (sk->sk_socket)
+                                       sk_wake_async(sk,
+                                                       SOCK_WAKE_IO, POLL_OUT);
 
                                tp->snd_una = TCP_SKB_CB(skb)->ack_seq;
                                tp->snd_wnd = ntohs(th->window) <<