1659a8ad5SYuchung Cheng #include <linux/tcp.h> 2659a8ad5SYuchung Cheng #include <net/tcp.h> 3659a8ad5SYuchung Cheng 44f41b1c5SYuchung Cheng int sysctl_tcp_recovery __read_mostly = TCP_RACK_LOST_RETRANS; 54f41b1c5SYuchung Cheng 6db8da6bbSYuchung Cheng static void tcp_rack_mark_skb_lost(struct sock *sk, struct sk_buff *skb) 7db8da6bbSYuchung Cheng { 8db8da6bbSYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 9db8da6bbSYuchung Cheng 10db8da6bbSYuchung Cheng tcp_skb_mark_lost_uncond_verify(tp, skb); 11db8da6bbSYuchung Cheng if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) { 12db8da6bbSYuchung Cheng /* Account for retransmits that are lost again */ 13db8da6bbSYuchung Cheng TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS; 14db8da6bbSYuchung Cheng tp->retrans_out -= tcp_skb_pcount(skb); 15db8da6bbSYuchung Cheng NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPLOSTRETRANSMIT); 16db8da6bbSYuchung Cheng } 17db8da6bbSYuchung Cheng } 18db8da6bbSYuchung Cheng 19*1d0833dfSYuchung Cheng static bool tcp_rack_sent_after(const struct skb_mstamp *t1, 20*1d0833dfSYuchung Cheng const struct skb_mstamp *t2, 21*1d0833dfSYuchung Cheng u32 seq1, u32 seq2) 22*1d0833dfSYuchung Cheng { 23*1d0833dfSYuchung Cheng return skb_mstamp_after(t1, t2) || 24*1d0833dfSYuchung Cheng (t1->v64 == t2->v64 && after(seq1, seq2)); 25*1d0833dfSYuchung Cheng } 26*1d0833dfSYuchung Cheng 274f41b1c5SYuchung Cheng /* Marks a packet lost, if some packet sent later has been (s)acked. 284f41b1c5SYuchung Cheng * The underlying idea is similar to the traditional dupthresh and FACK 294f41b1c5SYuchung Cheng * but they look at different metrics: 304f41b1c5SYuchung Cheng * 314f41b1c5SYuchung Cheng * dupthresh: 3 OOO packets delivered (packet count) 324f41b1c5SYuchung Cheng * FACK: sequence delta to highest sacked sequence (sequence space) 334f41b1c5SYuchung Cheng * RACK: sent time delta to the latest delivered packet (time domain) 344f41b1c5SYuchung Cheng * 354f41b1c5SYuchung Cheng * The advantage of RACK is it applies to both original and retransmitted 364f41b1c5SYuchung Cheng * packet and therefore is robust against tail losses. Another advantage 374f41b1c5SYuchung Cheng * is being more resilient to reordering by simply allowing some 384f41b1c5SYuchung Cheng * "settling delay", instead of tweaking the dupthresh. 394f41b1c5SYuchung Cheng * 404f41b1c5SYuchung Cheng * The current version is only used after recovery starts but can be 414f41b1c5SYuchung Cheng * easily extended to detect the first loss. 424f41b1c5SYuchung Cheng */ 4357dde7f7SYuchung Cheng static void tcp_rack_detect_loss(struct sock *sk, const struct skb_mstamp *now, 4457dde7f7SYuchung Cheng u32 *reo_timeout) 454f41b1c5SYuchung Cheng { 464f41b1c5SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 474f41b1c5SYuchung Cheng struct sk_buff *skb; 48e636f8b0SYuchung Cheng u32 reo_wnd; 494f41b1c5SYuchung Cheng 5057dde7f7SYuchung Cheng *reo_timeout = 0; 514f41b1c5SYuchung Cheng /* To be more reordering resilient, allow min_rtt/4 settling delay 524f41b1c5SYuchung Cheng * (lower-bounded to 1000uS). We use min_rtt instead of the smoothed 534f41b1c5SYuchung Cheng * RTT because reordering is often a path property and less related 544f41b1c5SYuchung Cheng * to queuing or delayed ACKs. 554f41b1c5SYuchung Cheng */ 564f41b1c5SYuchung Cheng reo_wnd = 1000; 574f41b1c5SYuchung Cheng if (tp->rack.reord && tcp_min_rtt(tp) != ~0U) 584f41b1c5SYuchung Cheng reo_wnd = max(tcp_min_rtt(tp) >> 2, reo_wnd); 594f41b1c5SYuchung Cheng 604f41b1c5SYuchung Cheng tcp_for_write_queue(skb, sk) { 614f41b1c5SYuchung Cheng struct tcp_skb_cb *scb = TCP_SKB_CB(skb); 624f41b1c5SYuchung Cheng 634f41b1c5SYuchung Cheng if (skb == tcp_send_head(sk)) 644f41b1c5SYuchung Cheng break; 654f41b1c5SYuchung Cheng 664f41b1c5SYuchung Cheng /* Skip ones already (s)acked */ 674f41b1c5SYuchung Cheng if (!after(scb->end_seq, tp->snd_una) || 684f41b1c5SYuchung Cheng scb->sacked & TCPCB_SACKED_ACKED) 694f41b1c5SYuchung Cheng continue; 704f41b1c5SYuchung Cheng 71*1d0833dfSYuchung Cheng if (tcp_rack_sent_after(&tp->rack.mstamp, &skb->skb_mstamp, 72*1d0833dfSYuchung Cheng tp->rack.end_seq, scb->end_seq)) { 73deed7be7SYuchung Cheng /* Step 3 in draft-cheng-tcpm-rack-00.txt: 74deed7be7SYuchung Cheng * A packet is lost if its elapsed time is beyond 75deed7be7SYuchung Cheng * the recent RTT plus the reordering window. 76deed7be7SYuchung Cheng */ 7757dde7f7SYuchung Cheng u32 elapsed = skb_mstamp_us_delta(now, 7857dde7f7SYuchung Cheng &skb->skb_mstamp); 7957dde7f7SYuchung Cheng s32 remaining = tp->rack.rtt_us + reo_wnd - elapsed; 8057dde7f7SYuchung Cheng 8157dde7f7SYuchung Cheng if (remaining < 0) { 82db8da6bbSYuchung Cheng tcp_rack_mark_skb_lost(sk, skb); 8357dde7f7SYuchung Cheng continue; 84deed7be7SYuchung Cheng } 8557dde7f7SYuchung Cheng 8657dde7f7SYuchung Cheng /* Skip ones marked lost but not yet retransmitted */ 8757dde7f7SYuchung Cheng if ((scb->sacked & TCPCB_LOST) && 8857dde7f7SYuchung Cheng !(scb->sacked & TCPCB_SACKED_RETRANS)) 8957dde7f7SYuchung Cheng continue; 9057dde7f7SYuchung Cheng 9157dde7f7SYuchung Cheng /* Record maximum wait time (+1 to avoid 0) */ 9257dde7f7SYuchung Cheng *reo_timeout = max_t(u32, *reo_timeout, 1 + remaining); 9357dde7f7SYuchung Cheng 944f41b1c5SYuchung Cheng } else if (!(scb->sacked & TCPCB_RETRANS)) { 954f41b1c5SYuchung Cheng /* Original data are sent sequentially so stop early 964f41b1c5SYuchung Cheng * b/c the rest are all sent after rack_sent 974f41b1c5SYuchung Cheng */ 984f41b1c5SYuchung Cheng break; 994f41b1c5SYuchung Cheng } 1004f41b1c5SYuchung Cheng } 101e636f8b0SYuchung Cheng } 102e636f8b0SYuchung Cheng 103deed7be7SYuchung Cheng void tcp_rack_mark_lost(struct sock *sk, const struct skb_mstamp *now) 104e636f8b0SYuchung Cheng { 105e636f8b0SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 10657dde7f7SYuchung Cheng u32 timeout; 107e636f8b0SYuchung Cheng 108e636f8b0SYuchung Cheng if (inet_csk(sk)->icsk_ca_state < TCP_CA_Recovery || !tp->rack.advanced) 109e636f8b0SYuchung Cheng return; 11057dde7f7SYuchung Cheng 111e636f8b0SYuchung Cheng /* Reset the advanced flag to avoid unnecessary queue scanning */ 112e636f8b0SYuchung Cheng tp->rack.advanced = 0; 11357dde7f7SYuchung Cheng tcp_rack_detect_loss(sk, now, &timeout); 11457dde7f7SYuchung Cheng if (timeout) { 11557dde7f7SYuchung Cheng timeout = usecs_to_jiffies(timeout + TCP_REO_TIMEOUT_MIN); 11657dde7f7SYuchung Cheng inet_csk_reset_xmit_timer(sk, ICSK_TIME_REO_TIMEOUT, 11757dde7f7SYuchung Cheng timeout, inet_csk(sk)->icsk_rto); 11857dde7f7SYuchung Cheng } 1194f41b1c5SYuchung Cheng } 1204f41b1c5SYuchung Cheng 121deed7be7SYuchung Cheng /* Record the most recently (re)sent time among the (s)acked packets 122deed7be7SYuchung Cheng * This is "Step 3: Advance RACK.xmit_time and update RACK.RTT" from 123deed7be7SYuchung Cheng * draft-cheng-tcpm-rack-00.txt 124deed7be7SYuchung Cheng */ 125*1d0833dfSYuchung Cheng void tcp_rack_advance(struct tcp_sock *tp, u8 sacked, u32 end_seq, 126deed7be7SYuchung Cheng const struct skb_mstamp *xmit_time, 127deed7be7SYuchung Cheng const struct skb_mstamp *ack_time) 128659a8ad5SYuchung Cheng { 129deed7be7SYuchung Cheng u32 rtt_us; 130deed7be7SYuchung Cheng 131659a8ad5SYuchung Cheng if (tp->rack.mstamp.v64 && 132*1d0833dfSYuchung Cheng !tcp_rack_sent_after(xmit_time, &tp->rack.mstamp, 133*1d0833dfSYuchung Cheng end_seq, tp->rack.end_seq)) 134659a8ad5SYuchung Cheng return; 135659a8ad5SYuchung Cheng 136deed7be7SYuchung Cheng rtt_us = skb_mstamp_us_delta(ack_time, xmit_time); 137659a8ad5SYuchung Cheng if (sacked & TCPCB_RETRANS) { 138659a8ad5SYuchung Cheng /* If the sacked packet was retransmitted, it's ambiguous 139659a8ad5SYuchung Cheng * whether the retransmission or the original (or the prior 140659a8ad5SYuchung Cheng * retransmission) was sacked. 141659a8ad5SYuchung Cheng * 142659a8ad5SYuchung Cheng * If the original is lost, there is no ambiguity. Otherwise 143659a8ad5SYuchung Cheng * we assume the original can be delayed up to aRTT + min_rtt. 144659a8ad5SYuchung Cheng * the aRTT term is bounded by the fast recovery or timeout, 145659a8ad5SYuchung Cheng * so it's at least one RTT (i.e., retransmission is at least 146659a8ad5SYuchung Cheng * an RTT later). 147659a8ad5SYuchung Cheng */ 148deed7be7SYuchung Cheng if (rtt_us < tcp_min_rtt(tp)) 149659a8ad5SYuchung Cheng return; 150659a8ad5SYuchung Cheng } 151deed7be7SYuchung Cheng tp->rack.rtt_us = rtt_us; 152659a8ad5SYuchung Cheng tp->rack.mstamp = *xmit_time; 153*1d0833dfSYuchung Cheng tp->rack.end_seq = end_seq; 154659a8ad5SYuchung Cheng tp->rack.advanced = 1; 155659a8ad5SYuchung Cheng } 15657dde7f7SYuchung Cheng 15757dde7f7SYuchung Cheng /* We have waited long enough to accommodate reordering. Mark the expired 15857dde7f7SYuchung Cheng * packets lost and retransmit them. 15957dde7f7SYuchung Cheng */ 16057dde7f7SYuchung Cheng void tcp_rack_reo_timeout(struct sock *sk) 16157dde7f7SYuchung Cheng { 16257dde7f7SYuchung Cheng struct tcp_sock *tp = tcp_sk(sk); 16357dde7f7SYuchung Cheng struct skb_mstamp now; 16457dde7f7SYuchung Cheng u32 timeout, prior_inflight; 16557dde7f7SYuchung Cheng 16657dde7f7SYuchung Cheng skb_mstamp_get(&now); 16757dde7f7SYuchung Cheng prior_inflight = tcp_packets_in_flight(tp); 16857dde7f7SYuchung Cheng tcp_rack_detect_loss(sk, &now, &timeout); 16957dde7f7SYuchung Cheng if (prior_inflight != tcp_packets_in_flight(tp)) { 17057dde7f7SYuchung Cheng if (inet_csk(sk)->icsk_ca_state != TCP_CA_Recovery) { 17157dde7f7SYuchung Cheng tcp_enter_recovery(sk, false); 17257dde7f7SYuchung Cheng if (!inet_csk(sk)->icsk_ca_ops->cong_control) 17357dde7f7SYuchung Cheng tcp_cwnd_reduction(sk, 1, 0); 17457dde7f7SYuchung Cheng } 17557dde7f7SYuchung Cheng tcp_xmit_retransmit_queue(sk); 17657dde7f7SYuchung Cheng } 17757dde7f7SYuchung Cheng if (inet_csk(sk)->icsk_pending != ICSK_TIME_RETRANS) 17857dde7f7SYuchung Cheng tcp_rearm_rto(sk); 17957dde7f7SYuchung Cheng } 180