tcp_recovery.c 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238
  1. // SPDX-License-Identifier: GPL-2.0
  2. #include <linux/tcp.h>
  3. #include <net/tcp.h>
  4. static bool tcp_rack_sent_after(u64 t1, u64 t2, u32 seq1, u32 seq2)
  5. {
  6. return t1 > t2 || (t1 == t2 && after(seq1, seq2));
  7. }
  8. static u32 tcp_rack_reo_wnd(const struct sock *sk)
  9. {
  10. struct tcp_sock *tp = tcp_sk(sk);
  11. if (!tp->reord_seen) {
  12. /* If reordering has not been observed, be aggressive during
  13. * the recovery or starting the recovery by DUPACK threshold.
  14. */
  15. if (inet_csk(sk)->icsk_ca_state >= TCP_CA_Recovery)
  16. return 0;
  17. if (tp->sacked_out >= tp->reordering &&
  18. !(sock_net(sk)->ipv4.sysctl_tcp_recovery & TCP_RACK_NO_DUPTHRESH))
  19. return 0;
  20. }
  21. /* To be more reordering resilient, allow min_rtt/4 settling delay.
  22. * Use min_rtt instead of the smoothed RTT because reordering is
  23. * often a path property and less related to queuing or delayed ACKs.
  24. * Upon receiving DSACKs, linearly increase the window up to the
  25. * smoothed RTT.
  26. */
  27. return min((tcp_min_rtt(tp) >> 2) * tp->rack.reo_wnd_steps,
  28. tp->srtt_us >> 3);
  29. }
  30. s32 tcp_rack_skb_timeout(struct tcp_sock *tp, struct sk_buff *skb, u32 reo_wnd)
  31. {
  32. return tp->rack.rtt_us + reo_wnd -
  33. tcp_stamp_us_delta(tp->tcp_mstamp, tcp_skb_timestamp_us(skb));
  34. }
  35. /* RACK loss detection (IETF draft draft-ietf-tcpm-rack-01):
  36. *
  37. * Marks a packet lost, if some packet sent later has been (s)acked.
  38. * The underlying idea is similar to the traditional dupthresh and FACK
  39. * but they look at different metrics:
  40. *
  41. * dupthresh: 3 OOO packets delivered (packet count)
  42. * FACK: sequence delta to highest sacked sequence (sequence space)
  43. * RACK: sent time delta to the latest delivered packet (time domain)
  44. *
  45. * The advantage of RACK is it applies to both original and retransmitted
  46. * packet and therefore is robust against tail losses. Another advantage
  47. * is being more resilient to reordering by simply allowing some
  48. * "settling delay", instead of tweaking the dupthresh.
  49. *
  50. * When tcp_rack_detect_loss() detects some packets are lost and we
  51. * are not already in the CA_Recovery state, either tcp_rack_reo_timeout()
  52. * or tcp_time_to_recover()'s "Trick#1: the loss is proven" code path will
  53. * make us enter the CA_Recovery state.
  54. */
  55. static void tcp_rack_detect_loss(struct sock *sk, u32 *reo_timeout)
  56. {
  57. struct tcp_sock *tp = tcp_sk(sk);
  58. struct sk_buff *skb, *n;
  59. u32 reo_wnd;
  60. *reo_timeout = 0;
  61. reo_wnd = tcp_rack_reo_wnd(sk);
  62. list_for_each_entry_safe(skb, n, &tp->tsorted_sent_queue,
  63. tcp_tsorted_anchor) {
  64. struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
  65. s32 remaining;
  66. /* Skip ones marked lost but not yet retransmitted */
  67. if ((scb->sacked & TCPCB_LOST) &&
  68. !(scb->sacked & TCPCB_SACKED_RETRANS))
  69. continue;
  70. if (!tcp_rack_sent_after(tp->rack.mstamp,
  71. tcp_skb_timestamp_us(skb),
  72. tp->rack.end_seq, scb->end_seq))
  73. break;
  74. /* A packet is lost if it has not been s/acked beyond
  75. * the recent RTT plus the reordering window.
  76. */
  77. remaining = tcp_rack_skb_timeout(tp, skb, reo_wnd);
  78. if (remaining <= 0) {
  79. tcp_mark_skb_lost(sk, skb);
  80. list_del_init(&skb->tcp_tsorted_anchor);
  81. } else {
  82. /* Record maximum wait time */
  83. *reo_timeout = max_t(u32, *reo_timeout, remaining);
  84. }
  85. }
  86. }
  87. bool tcp_rack_mark_lost(struct sock *sk)
  88. {
  89. struct tcp_sock *tp = tcp_sk(sk);
  90. u32 timeout;
  91. if (!tp->rack.advanced)
  92. return false;
  93. /* Reset the advanced flag to avoid unnecessary queue scanning */
  94. tp->rack.advanced = 0;
  95. tcp_rack_detect_loss(sk, &timeout);
  96. if (timeout) {
  97. timeout = usecs_to_jiffies(timeout) + TCP_TIMEOUT_MIN;
  98. inet_csk_reset_xmit_timer(sk, ICSK_TIME_REO_TIMEOUT,
  99. timeout, inet_csk(sk)->icsk_rto);
  100. }
  101. return !!timeout;
  102. }
  103. /* Record the most recently (re)sent time among the (s)acked packets
  104. * This is "Step 3: Advance RACK.xmit_time and update RACK.RTT" from
  105. * draft-cheng-tcpm-rack-00.txt
  106. */
  107. void tcp_rack_advance(struct tcp_sock *tp, u8 sacked, u32 end_seq,
  108. u64 xmit_time)
  109. {
  110. u32 rtt_us;
  111. rtt_us = tcp_stamp_us_delta(tp->tcp_mstamp, xmit_time);
  112. if (rtt_us < tcp_min_rtt(tp) && (sacked & TCPCB_RETRANS)) {
  113. /* If the sacked packet was retransmitted, it's ambiguous
  114. * whether the retransmission or the original (or the prior
  115. * retransmission) was sacked.
  116. *
  117. * If the original is lost, there is no ambiguity. Otherwise
  118. * we assume the original can be delayed up to aRTT + min_rtt.
  119. * the aRTT term is bounded by the fast recovery or timeout,
  120. * so it's at least one RTT (i.e., retransmission is at least
  121. * an RTT later).
  122. */
  123. return;
  124. }
  125. tp->rack.advanced = 1;
  126. tp->rack.rtt_us = rtt_us;
  127. if (tcp_rack_sent_after(xmit_time, tp->rack.mstamp,
  128. end_seq, tp->rack.end_seq)) {
  129. tp->rack.mstamp = xmit_time;
  130. tp->rack.end_seq = end_seq;
  131. }
  132. }
  133. /* We have waited long enough to accommodate reordering. Mark the expired
  134. * packets lost and retransmit them.
  135. */
  136. void tcp_rack_reo_timeout(struct sock *sk)
  137. {
  138. struct tcp_sock *tp = tcp_sk(sk);
  139. u32 timeout, prior_inflight;
  140. prior_inflight = tcp_packets_in_flight(tp);
  141. tcp_rack_detect_loss(sk, &timeout);
  142. if (prior_inflight != tcp_packets_in_flight(tp)) {
  143. if (inet_csk(sk)->icsk_ca_state != TCP_CA_Recovery) {
  144. tcp_enter_recovery(sk, false);
  145. if (!inet_csk(sk)->icsk_ca_ops->cong_control)
  146. tcp_cwnd_reduction(sk, 1, 0);
  147. }
  148. tcp_xmit_retransmit_queue(sk);
  149. }
  150. if (inet_csk(sk)->icsk_pending != ICSK_TIME_RETRANS)
  151. tcp_rearm_rto(sk);
  152. }
  153. /* Updates the RACK's reo_wnd based on DSACK and no. of recoveries.
  154. *
  155. * If DSACK is received, increment reo_wnd by min_rtt/4 (upper bounded
  156. * by srtt), since there is possibility that spurious retransmission was
  157. * due to reordering delay longer than reo_wnd.
  158. *
  159. * Persist the current reo_wnd value for TCP_RACK_RECOVERY_THRESH (16)
  160. * no. of successful recoveries (accounts for full DSACK-based loss
  161. * recovery undo). After that, reset it to default (min_rtt/4).
  162. *
  163. * At max, reo_wnd is incremented only once per rtt. So that the new
  164. * DSACK on which we are reacting, is due to the spurious retx (approx)
  165. * after the reo_wnd has been updated last time.
  166. *
  167. * reo_wnd is tracked in terms of steps (of min_rtt/4), rather than
  168. * absolute value to account for change in rtt.
  169. */
  170. void tcp_rack_update_reo_wnd(struct sock *sk, struct rate_sample *rs)
  171. {
  172. struct tcp_sock *tp = tcp_sk(sk);
  173. if (sock_net(sk)->ipv4.sysctl_tcp_recovery & TCP_RACK_STATIC_REO_WND ||
  174. !rs->prior_delivered)
  175. return;
  176. /* Disregard DSACK if a rtt has not passed since we adjusted reo_wnd */
  177. if (before(rs->prior_delivered, tp->rack.last_delivered))
  178. tp->rack.dsack_seen = 0;
  179. /* Adjust the reo_wnd if update is pending */
  180. if (tp->rack.dsack_seen) {
  181. tp->rack.reo_wnd_steps = min_t(u32, 0xFF,
  182. tp->rack.reo_wnd_steps + 1);
  183. tp->rack.dsack_seen = 0;
  184. tp->rack.last_delivered = tp->delivered;
  185. tp->rack.reo_wnd_persist = TCP_RACK_RECOVERY_THRESH;
  186. } else if (!tp->rack.reo_wnd_persist) {
  187. tp->rack.reo_wnd_steps = 1;
  188. }
  189. }
  190. /* RFC6582 NewReno recovery for non-SACK connection. It simply retransmits
  191. * the next unacked packet upon receiving
  192. * a) three or more DUPACKs to start the fast recovery
  193. * b) an ACK acknowledging new data during the fast recovery.
  194. */
  195. void tcp_newreno_mark_lost(struct sock *sk, bool snd_una_advanced)
  196. {
  197. const u8 state = inet_csk(sk)->icsk_ca_state;
  198. struct tcp_sock *tp = tcp_sk(sk);
  199. if ((state < TCP_CA_Recovery && tp->sacked_out >= tp->reordering) ||
  200. (state == TCP_CA_Recovery && snd_una_advanced)) {
  201. struct sk_buff *skb = tcp_rtx_queue_head(sk);
  202. u32 mss;
  203. if (TCP_SKB_CB(skb)->sacked & TCPCB_LOST)
  204. return;
  205. mss = tcp_skb_mss(skb);
  206. if (tcp_skb_pcount(skb) > 1 && skb->len > mss)
  207. tcp_fragment(sk, TCP_FRAG_IN_RTX_QUEUE, skb,
  208. mss, mss, GFP_ATOMIC);
  209. tcp_mark_skb_lost(sk, skb);
  210. }
  211. }