5 files changed, 202 insertions, 26 deletions

diff --git a/include/linux/tcp.h b/include/linux/tcp.h
index 737b32e52956..0e1da6602e05 100644
--- a/include/linux/tcp.h
+++ b/include/linux/tcp.h
@@ -307,6 +307,21 @@ struct tcp_sock {
         struct tcp_sack_block duplicate_sack[1]; /* D-SACK block */
         struct tcp_sack_block selective_acks[4]; /* The SACKS themselves*/
 
+        struct tcp_sack_block recv_sack_cache[4];
+
+        /* from STCP, retrans queue hinting */
+        struct sk_buff* lost_skb_hint;
+
+        struct sk_buff *scoreboard_skb_hint;
+        struct sk_buff *retransmit_skb_hint;
+        struct sk_buff *forward_skb_hint;
+        struct sk_buff *fastpath_skb_hint;
+
+        int     fastpath_cnt_hint;
+        int     lost_cnt_hint;
+        int     retransmit_cnt_hint;
+        int     forward_cnt_hint;
+
         __u16   advmss;         /* Advertised MSS                       */
         __u16   prior_ssthresh; /* ssthresh saved at recovery start     */
         __u32   lost_out;       /* Lost packets                 */
diff --git a/include/net/sock.h b/include/net/sock.h
index ff13c4cc287a..982b4ecd187b 100644
--- a/include/net/sock.h
+++ b/include/net/sock.h
@@ -1247,6 +1247,12 @@ static inline struct page *sk_stream_alloc_page(struct sock *sk)
                      (skb != (struct sk_buff *)&(sk)->sk_write_queue);  \
                      skb = skb->next)
 
+/*from STCP for fast SACK Process*/
+#define sk_stream_for_retrans_queue_from(skb, sk)                       \
+                for (; (skb != (sk)->sk_send_head) &&                   \
+                     (skb != (struct sk_buff *)&(sk)->sk_write_queue);  \
+                     skb = skb->next)
+
 /*
  *      Default write policy as shown to user space via poll/select/SIGIO
  */
diff --git a/include/net/tcp.h b/include/net/tcp.h
index 6e6f0f3f1dd8..0f9848011972 100644
--- a/include/net/tcp.h
+++ b/include/net/tcp.h
@@ -1207,6 +1207,15 @@ static inline void tcp_mib_init(void)
         TCP_ADD_STATS_USER(TCP_MIB_MAXCONN, -1);
 }
 
+/*from STCP */
+static inline void clear_all_retrans_hints(struct tcp_sock *tp){
+        tp->lost_skb_hint = NULL;
+        tp->scoreboard_skb_hint = NULL;
+        tp->retransmit_skb_hint = NULL;
+        tp->forward_skb_hint = NULL;
+        tp->fastpath_skb_hint = NULL;
+}
+
 /* /proc */
 enum tcp_seq_states {
         TCP_SEQ_STATE_LISTENING,
diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 34cfa58eab76..40a26b7157b4 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -897,18 +897,32 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
         int prior_fackets;
         u32 lost_retrans = 0;
         int flag = 0;
+        int dup_sack = 0;
         int i;
 
         if (!tp->sacked_out)
                 tp->fackets_out = 0;
         prior_fackets = tp->fackets_out;
 
-        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 = 0;
-                int dup_sack = 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++) {
+                __u32 start_seq = ntohl(sp[i].start_seq);
+                __u32 end_seq =  ntohl(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;
 
                 /* Check for D-SACK. */
                 if (i == 0) {
@@ -940,15 +954,58 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
                         if (before(ack, prior_snd_una - tp->max_window))
                                 return 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))){
+                                        sp[j].start_seq = htonl(tp->recv_sack_cache[j+1].start_seq);
+                                        sp[j].end_seq = htonl(tp->recv_sack_cache[j+1].end_seq);
+                                        sp[j+1].start_seq = htonl(tp->recv_sack_cache[j].start_seq);
+                                        sp[j+1].end_seq = htonl(tp->recv_sack_cache[j].end_seq);
+                                }
+
+                        }
+                }
+        }
+
+        /* clear flag as used for different purpose in following code */
+        flag = 0;
+
+        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;
+
+                /* Use SACK fastpath hint if valid */
+                if (tp->fastpath_skb_hint) {
+                        skb = tp->fastpath_skb_hint;
+                        fack_count = tp->fastpath_cnt_hint;
+                } else {
+                        skb = sk->sk_write_queue.next;
+                        fack_count = 0;
+                }
 
                 /* Event "B" in the comment above. */
                 if (after(end_seq, tp->high_seq))
                         flag |= FLAG_DATA_LOST;
 
-                sk_stream_for_retrans_queue(skb, sk) {
+                sk_stream_for_retrans_queue_from(skb, sk) {
                         int in_sack, pcount;
                         u8 sacked;
 
+                        tp->fastpath_skb_hint = skb;
+                        tp->fastpath_cnt_hint = fack_count;
+
                         /* The retransmission queue is always in order, so
                          * we can short-circuit the walk early.
                          */
@@ -1023,6 +1080,9 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
                                                 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,
@@ -1035,6 +1095,9 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
                                         if (sacked & TCPCB_LOST) {
                                                 TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
                                                 tp->lost_out -= tcp_skb_pcount(skb);