[PATCH net v3 0/3] tcp: preserve RACK tracking across partial undo

[PATCH net v3 0/3] tcp: preserve RACK tracking across partial undo

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

Partial undo can clear the TCPCB_LOST flag on segments already removed
from RACK's list, which prevents subsequent RACK loss detection, leading
to segments only being retransmitted after the RTO.

My investigation started from seeing repeated TCP stalls in prod and the
mitigation that seemed to prevent these stalls was limiting SO_SNDBUF to
96 KiB. It also seems like others have seen similar symptoms before [1].

These changes use the implementation provided by Neal Cardwell to restore
elements to the RACK list that were lost but not yet retransmitted.
Segments that are lost but already retransmitted are explicitly left to be
handled by the RTO. Since I've used your implementation Neal, I'd love a
Co-developed-by and Signed-off-by if it still looks good.

Patch 2 tests that these changes allow RACK to (re-)track a segment marked
as TCPCB_LOST but not TCPCB_EVER_RETRANS. Patch 3 tests that a segment
marked as TCPCB_LOST and TCPCB_EVER_RETRANS is transmitted by an RTO.

Changes in v3:
- Replaced sorting with Neal's implementation [2]
- Clarified the relink helper's complexity comment
- Clarified the original packetdrill test's comments
- Added a new packetdrill test for the intended RTO fallback

v2:
https://lore.kernel.org/netdev/cover.1791248202.git.nramaswamy@openai.com/

v1:
https://lore.kernel.org/netdev/20260926002520.42955-4-nramaswamy@openai.com/

[1]
https://lore.kernel.org/netdev/35A4DDAA-7E8D-43CB-A1F5-D1E46A4ED42E@gmail.com/
[2]
https://lore.kernel.org/netdev/20261006141300.1722466-1-ncardwell.sw@gmail.com/

Neil Ramaswamy (3):
  tcp: restore RACK list membership when undoing loss
  selftests: net: packetdrill: test RACK after partial undo
  selftests: net: packetdrill: test RTO fallback after partial undo

 net/ipv4/tcp_input.c                          | 50 +++++++++++++-
 ...tcp_partial_undo-restores-to-rack-list.pkt | 54 +++++++++++++++
 .../tcp_partial_undo-rto-fallback.pkt         | 65 +++++++++++++++++++
 3 files changed, 168 insertions(+), 1 deletion(-)
 create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt
 create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-rto-fallback.pkt


base-commit: 11536ee3d3e0b1bd35b6f3f8df55a6053eb0c71d
-- 
2.55.0

[PATCH net v3 1/3] tcp: restore RACK list membership when undoing loss

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

Partial undo can clear the TCPCB_LOST flag on segments already removed
from RACK's list, which prevents subsequent RACK loss detection, leading
to segments only being retransmitted after the RTO.

This patch uses the implementation provided by Neal Cardwell to linearly
insert lost segments that have not been retransmitted back into the RACK
list. The core observation is that segments that are lost but not ever
retransmitted are already sorted by their transmission timestamp, which
allows us to insert them into RACK's list linearly, without needing to
pre-sort them.

Segments with TCPCB_EVER_RETRANS are left for RTO recovery. Their
transmission order can differ from their sequence order, so reinserting
them would require addiitonal work (e.g. sorting) before reinsertion into
the RACK list. We assume that this case is rare, and allow those segments
to be transmitted by the RTO.

My investigation started from seeing repeated TCP stalls in prod and the
mitigation that seemed to prevent these stalls was limiting SO_SNDBUF to
96 KiB. It also seems like others have seen similar symptoms before [1].

[1]
https://lore.kernel.org/netdev/35A4DDAA-7E8D-43CB-A1F5-D1E46A4ED42E@gmail.com/

Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
Suggested-by: Neal Cardwell <ncardwell@google.com>
Suggested-by: Yuchung Cheng <ycheng@google.com>
Link: https://lore.kernel.org/netdev/20261006141300.1722466-1-ncardwell.sw@gmail.com/
Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
Assisted-by: LLM sparse
---
 net/ipv4/tcp_input.c | 50 +++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 49 insertions(+), 1 deletion(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 92bc60716f33..d0a1e8899c4b 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -2840,15 +2840,63 @@ static void DBGUNDO(struct sock *sk, const char *msg)
 #endif
 }
 
+/* Is skb @a after skb @b in tp->tsorted_sent_queue (send) order? */
+static bool tcp_tsorted_after(const struct list_head *a,
+			      const struct list_head *b)
+{
+	const struct sk_buff *skb_a = list_entry(a, struct sk_buff,
+						 tcp_tsorted_anchor);
+	const struct sk_buff *skb_b = list_entry(b, struct sk_buff,
+						 tcp_tsorted_anchor);
+
+	return tcp_skb_sent_after(tcp_skb_timestamp_us(skb_a),
+				  tcp_skb_timestamp_us(skb_b),
+				  TCP_SKB_CB(skb_a)->end_seq,
+				  TCP_SKB_CB(skb_b)->end_seq);
+}
+
+/* Link skb back into tp->tsorted_sent_queue in send order, at or after
+ * pos, and advance pos to it. Leave skb alone if it was sent before
+ * pos. During undo, all relink calls together traverse the RACK list
+ * at most once, as pos only moves forward.
+ */
+static void tcp_tsorted_relink_skb(struct tcp_sock *tp, struct sk_buff *skb,
+				   struct list_head **pos_ptr)
+{
+	struct list_head *head = &tp->tsorted_sent_queue;
+	struct list_head *node = &skb->tcp_tsorted_anchor;
+	struct list_head *pos = *pos_ptr;
+
+	if (pos != head && !tcp_tsorted_after(node, pos))
+		return;
+	while (pos->next != head && !tcp_tsorted_after(pos->next, node))
+		pos = pos->next;
+	if (pos != node)		/* not already linked in place */
+		list_move(node, pos);
+	*pos_ptr = node;
+}
+
 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 
 	if (unmark_loss) {
+		struct list_head *pos = &tp->tsorted_sent_queue;
 		struct sk_buff *skb;
 
 		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
-			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
+			u8 sacked = TCP_SKB_CB(skb)->sacked;
+
+			TCP_SKB_CB(skb)->sacked = sacked & ~TCPCB_LOST;
+			/* RACK unlinked the skbs it marked lost. Skbs never
+			 * retransmitted keep their original send times, which
+			 * increase with sequence, so in one forward pass we
+			 * relink them all. For the rare case of undo after
+			 * lost retransmissions, we will fall back to RTO.
+			 */
+			if ((sacked & (TCPCB_LOST | TCPCB_EVER_RETRANS)) ==
+			    TCPCB_LOST)
+				tcp_tsorted_relink_skb(tp, skb, &pos);
 		}
 		tp->lost_out = 0;
 		tcp_clear_all_retrans_hints(tp);
-- 
2.55.0

[PATCH net v3 2/3] selftests: net: packetdrill: test RACK after partial undo

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

Reproduces a partial undo bug where a segment is unmarked as lost but is
never returned to RACK's timestamp sorted list, which makes it ineligible
for future fast retransmission.

Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
Assisted-by: LLM sparse
---
 ...tcp_partial_undo-restores-to-rack-list.pkt | 54 +++++++++++++++++++
 1 file changed, 54 insertions(+)
 create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt

diff --git a/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt
new file mode 100644
index 000000000000..e37e1e679e02
--- /dev/null
+++ b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt
@@ -0,0 +1,54 @@
+// SPDX-License-Identifier: GPL-2.0
+//
+// Test that a segment unmarked as lost during partial undo is eligible
+// for future fast retransmission.
+
+`./defaults.sh`
+
+// Establish a connection with a 100 ms RTT and a 1000-byte payload MSS.
+// Linux subtracts the 12-byte timestamp options from the advertised MSS.
+    0 socket(..., SOCK_STREAM, IPPROTO_TCP) = 3
+   +0 setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
+   +0 bind(3, ..., ...) = 0
+   +0 listen(3, 1) = 0
+
+  +.1 < S 0:0(0) win 20000 <mss 1012,sackOK,TS val 1000 ecr 0>
+   +0 > S. 0:0(0) ack 1 <mss 1460,sackOK,TS val 100 ecr 1000>
+  +.1 < . 1:1(0) ack 1 win 20000 <nop,nop,TS val 1100 ecr 100>
+   +0 accept(3, ..., ...) = 4
+
+// Send A, B, C and D, then E 47 ms after D.
+ +.01 write(4, ..., 1000) = 1000
+   +0 > P. 1:1001(1000) ack 1 <nop,nop,TS val 210 ecr 1100>
++.001 write(4, ..., 1000) = 1000
+   +0 > P. 1001:2001(1000) ack 1 <...>
++.001 write(4, ..., 1000) = 1000
+   +0 > P. 2001:3001(1000) ack 1 <...>
++.001 write(4, ..., 1000) = 1000
+   +0 > P. 3001:4001(1000) ack 1 <...>
++.047 write(4, ..., 1000) = 1000
+   +0 > P. 4001:5001(1000) ack 1 <...>
+
+// SACK C and E together. RACK marks A, B and D lost. D is old enough
+// to be retransmitted, but this ACK reports only two newly delivered
+// segments, allowing A and B to be retransmitted while D waits.
+ +.12 < . 1:1(0) ack 1 win 20000 <TS val 1280 ecr 100,sack 4001:5001 2001:3001>
+   +0 > P. 1:1001(1000) ack 1 <...>
+   +0 > P. 1001:2001(1000) ack 1 <...>
+   +0 %{
+assert tcpi_ca_state == TCP_CA_Recovery, tcpi_ca_state
+assert tcpi_lost == 3, tcpi_lost
+assert tcpi_retrans == 2, tcpi_retrans
+}%
+
+// Deliver retransmitted B and then the original A. D stays missing,
+// and we ACK through C with A's original timestamp, which is before
+// retransmission started. This triggers partial undo, but since D
+// is not EVER_RETRANS, partial undo should add it back to the RACK list.
+// Critically, we test that the RTO retry counter should stay 0.
+ +.07 < . 1:1(0) ack 3001 win 20000 <TS val 1350 ecr 210,sack 4001:5001>
+ +0~+.05 > P. 3001:4001(1000) ack 1 <nop,nop,TS val 450 ecr 1350>
+   +0 %{ assert tcpi_retransmits == 0, tcpi_retransmits }%
+
+// Acknowledge all five segments.
+ +.01 < . 1:1(0) ack 5001 win 20000 <nop,nop,TS val 1360 ecr 450>
-- 
2.55.0

[PATCH net v3 3/3] selftests: net: packetdrill: test RTO fallback after partial undo

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

Tests that a segment that is lost but also previously retransmitted is not
added back to the RACK list during partial undo, and is instead
retransmitted by the RTO. It utilizes the fact that a TLP doesn't increment
retrans_out, which needs to be 0 for partial undo (but this scenario may
also happen without the TLP).

Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
Assisted-by: LLM
---
 .../tcp_partial_undo-rto-fallback.pkt         | 65 +++++++++++++++++++
 1 file changed, 65 insertions(+)
 create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-rto-fallback.pkt

diff --git a/tools/testing/selftests/net/packetdrill/tcp_partial_undo-rto-fallback.pkt b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-rto-fallback.pkt
new file mode 100644
index 000000000000..844895121573
--- /dev/null
+++ b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-rto-fallback.pkt
@@ -0,0 +1,65 @@
+// SPDX-License-Identifier: GPL-2.0
+//
+// Test that a segment that is lost but also previously retransmitted is not
+// added back to the RACK list during partial undo.
+
+`./defaults.sh`
+
+// Establish a connection with a 100 ms RTT and a 1000-byte payload MSS.
+    0 socket(..., SOCK_STREAM, IPPROTO_TCP) = 3
+   +0 setsockopt(3, SOL_SOCKET, SO_REUSEADDR, [1], 4) = 0
+   +0 bind(3, ..., ...) = 0
+   +0 listen(3, 1) = 0
+
+  .100 < S 0:0(0) win 20000 <mss 1012,sackOK,TS val 1000 ecr 0>
+    +0 > S. 0:0(0) ack 1 <mss 1460,sackOK,TS val 100 ecr 1000>
+  .200 < . 1:1(0) ack 1 win 20000 <nop,nop,TS val 1100 ecr 100>
+    +0 accept(3, ..., ...) = 4
+
+// A is delayed. B, the tail segment, is lost.
+  .210 write(4, ..., 1000) = 1000
+    +0 > P. 1:1001(1000) ack 1 <nop,nop,TS val 210 ecr 1100>
+  .211 write(4, ..., 1000) = 1000
+    +0 > P. 1001:2001(1000) ack 1 <...>
+
+// With no ACKs, the TLP retransmits B at roughly 2*RTT after its send,
+// which adds TCPCB_EVER_RETRANS to B.
+  .400~.430 > P. 1001:2001(1000) ack 1 <...>
+  .435 %{
+assert tcpi_ca_state == TCP_CA_Open, tcpi_ca_state
+assert tcpi_total_retrans == 1, tcpi_total_retrans
+}%
+
+// C is sent and arrives with a 40ms RTT. It is sent after A and B's tail
+// retransmission, and both A and B have remained unack'd for RACK's
+// RTT + reorder window. So RACK marks them as TCPCB_LOST. C's SACK allows A to
+// be retransmitted as A'. Now, A and B are both TCPCB_LOST and
+// TCPCB_EVER_RETRANS.
+  .440 write(4, ..., 1000) = 1000
+    +0 > P. 2001:3001(1000) ack 1 <...>
+  .480 < . 1:1(0) ack 1 win 20000 <TS val 1380 ecr 100,sack 2001:3001>
+    +0 > P. 1:1001(1000) ack 1 <...>
+    +0 %{
+assert tcpi_ca_state == TCP_CA_Recovery, tcpi_ca_state
+assert tcpi_lost == 2, tcpi_lost
+assert tcpi_total_retrans == 2, tcpi_total_retrans
+}%
+
+// The original A arrives. Its timestamp predates A's retransmission,
+// which starts partial undo. B's TCPCB_LOST flag is cleared, but because it
+// is TCPCB_EVER_RETRANS, it is not restored to the RACK list. Only RTO will
+// rescue it.
+  .490 < . 1:1(0) ack 1001 win 20000 <TS val 1390 ecr 210,sack 2001:3001>
+  +.001 %{
+assert tcpi_unacked == 2, tcpi_unacked
+assert tcpi_lost == 0, tcpi_lost
+assert tcpi_retransmits == 0, tcpi_retransmits
+assert tcpi_total_retrans == 2, tcpi_total_retrans
+}%
+
+// No prompt retransmission: the remaining hole is recovered by one RTO.
+  +.100~+1.000 > P. 1001:2001(1000) ack 1 <...>
+    +0 %{
+assert tcpi_retransmits == 1, tcpi_retransmits
+assert tcpi_total_retrans == 3, tcpi_total_retrans
+}%
-- 
2.55.0

Re: [PATCH net v3 1/3] tcp: restore RACK list membership when undoing loss

[Eric Dumazet]

On 10/9/26 07:00, nramaswamy@openai.com wrote:
> From: Neil Ramaswamy <nramaswamy@openai.com>
> 
> Partial undo can clear the TCPCB_LOST flag on segments already removed
> from RACK's list, which prevents subsequent RACK loss detection, leading
> to segments only being retransmitted after the RTO.
> 
> This patch uses the implementation provided by Neal Cardwell to linearly
> insert lost segments that have not been retransmitted back into the RACK
> list. The core observation is that segments that are lost but not ever
> retransmitted are already sorted by their transmission timestamp, which
> allows us to insert them into RACK's list linearly, without needing to
> pre-sort them.
> 
> Segments with TCPCB_EVER_RETRANS are left for RTO recovery. Their
> transmission order can differ from their sequence order, so reinserting
> them would require addiitonal work (e.g. sorting) before reinsertion into
> the RACK list. We assume that this case is rare, and allow those segments
> to be transmitted by the RTO.
> 
> My investigation started from seeing repeated TCP stalls in prod and the
> mitigation that seemed to prevent these stalls was limiting SO_SNDBUF to
> 96 KiB. It also seems like others have seen similar symptoms before [1].
> 
> [1]
> https://lore.kernel.org/netdev/35A4DDAA-7E8D-43CB-A1F5-D1E46A4ED42E@gmail.com/
> 
> Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
> Suggested-by: Neal Cardwell <ncardwell@google.com>
> Suggested-by: Yuchung Cheng <ycheng@google.com>
> Link: https://lore.kernel.org/netdev/20261006141300.1722466-1-ncardwell.sw@gmail.com/
> Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
> Assisted-by: LLM sparse
> ---
>   net/ipv4/tcp_input.c | 50 +++++++++++++++++++++++++++++++++++++++++++-
>   1 file changed, 49 insertions(+), 1 deletion(-)
> 
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index 92bc60716f33..d0a1e8899c4b 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -2840,15 +2840,63 @@ static void DBGUNDO(struct sock *sk, const char *msg)
>   #endif
>   }
>   
> +/* Is skb @a after skb @b in tp->tsorted_sent_queue (send) order? */
> +static bool tcp_tsorted_after(const struct list_head *a,
> +			      const struct list_head *b)
> +{
> +	const struct sk_buff *skb_a = list_entry(a, struct sk_buff,
> +						 tcp_tsorted_anchor);
> +	const struct sk_buff *skb_b = list_entry(b, struct sk_buff,
> +						 tcp_tsorted_anchor);
> +
> +	return tcp_skb_sent_after(tcp_skb_timestamp_us(skb_a),
> +				  tcp_skb_timestamp_us(skb_b),
> +				  TCP_SKB_CB(skb_a)->end_seq,
> +				  TCP_SKB_CB(skb_b)->end_seq);

pw-bot: cr

You ignored my initial feedback.

https://lore.kernel.org/netdev/627cd81c-9824-4d1b-ae47-f7f929a96596@kernel.org/

Thanks.

> +}
> +
> +/* Link skb back into tp->tsorted_sent_queue in send order, at or after
> + * pos, and advance pos to it. Leave skb alone if it was sent before
> + * pos. During undo, all relink calls together traverse the RACK list
> + * at most once, as pos only moves forward.
> + */
> +static void tcp_tsorted_relink_skb(struct tcp_sock *tp, struct sk_buff *skb,
> +				   struct list_head **pos_ptr)
> +{
> +	struct list_head *head = &tp->tsorted_sent_queue;
> +	struct list_head *node = &skb->tcp_tsorted_anchor;
> +	struct list_head *pos = *pos_ptr;
> +
> +	if (pos != head && !tcp_tsorted_after(node, pos))
> +		return;
> +	while (pos->next != head && !tcp_tsorted_after(pos->next, node))
> +		pos = pos->next;
> +	if (pos != node)		/* not already linked in place */
> +		list_move(node, pos);
> +	*pos_ptr = node;
> +}
> +
>   static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
>   {
>   	struct tcp_sock *tp = tcp_sk(sk);
>   
>   	if (unmark_loss) {
> +		struct list_head *pos = &tp->tsorted_sent_queue;
>   		struct sk_buff *skb;
>   
>   		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
> -			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
> +			u8 sacked = TCP_SKB_CB(skb)->sacked;
> +
> +			TCP_SKB_CB(skb)->sacked = sacked & ~TCPCB_LOST;
> +			/* RACK unlinked the skbs it marked lost. Skbs never
> +			 * retransmitted keep their original send times, which
> +			 * increase with sequence, so in one forward pass we
> +			 * relink them all. For the rare case of undo after
> +			 * lost retransmissions, we will fall back to RTO.
> +			 */
> +			if ((sacked & (TCPCB_LOST | TCPCB_EVER_RETRANS)) ==
> +			    TCPCB_LOST)
> +				tcp_tsorted_relink_skb(tp, skb, &pos);
>   		}
>   		tp->lost_out = 0;
>   		tcp_clear_all_retrans_hints(tp);

Re: [PATCH net v3 2/3] selftests: net: packetdrill: test RACK after partial undo

[Eric Dumazet]

On 10/9/26 07:00, nramaswamy@openai.com wrote:
> From: Neil Ramaswamy <nramaswamy@openai.com>
> 
> Reproduces a partial undo bug where a segment is unmarked as lost but is
> never returned to RACK's timestamp sorted list, which makes it ineligible
> for future fast retransmission.
> 
> Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
> Assisted-by: LLM sparse
> ---

Was this test changed since last time?

I thought I already reviewed it.

https://lore.kernel.org/netdev/7a977ccc-b6e5-4430-8ffa-fbde5ed9f4f9@kernel.org/

You are supposed to carry the reviews from Vx to Vy if no significant 
change happened.

Please do whatever it takes to reduce our huge load.

Thanks.

Re: [PATCH net v3 3/3] selftests: net: packetdrill: test RTO fallback after partial undo

[Eric Dumazet]

Le ven. 9 oct. 2026 à 07:01, <nramaswamy@openai.com> a écrit :
>
> From: Neil Ramaswamy <nramaswamy@openai.com>
>
> Tests that a segment that is lost but also previously retransmitted is not
> added back to the RACK list during partial undo, and is instead
> retransmitted by the RTO. It utilizes the fact that a TLP doesn't increment
> retrans_out, which needs to be 0 for partial undo (but this scenario may
> also happen without the TLP).
>
> Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
> Assisted-by: LLM
> ---

This test passes with or without patch 1/3, so it does not test the fix.

It records that a 3-segment flow with one TLP and one late ACK has to
wait for an RTO, and whoever fixes that later will have to rewrite it.

A single TLP probe is enough to get TCPCB_EVER_RETRANS on a segment, so
I am not convinced this case is rare.

Let me come back to tp->tsorted_lost_queue [1]. I was too terse there
("often") and it did not get discussed.

tcp_rack_detect_loss() walks tsorted_sent_queue from oldest to newest,
and whatever it leaves there was sent after what it just marked lost.
So if it does

list_move_tail(&skb->tcp_tsorted_anchor, &tp->tsorted_lost_queue);

instead of list_del_init(), the lost queue stays sorted by send time
across scans, for free. This also holds for skbs that were retransmitted
(TLP probe, lost retransmit), because they sit in tsorted_sent_queue at
their last transmit time. No TCPCB_EVER_RETRANS special case, no
comparator.

- Retransmit: tcp_update_skb_after_send() already moves the skb to the
  tail of tsorted_sent_queue.
- SACK and cumulative ACK: list_del_init()/list_del() are unchanged.
- tcp_fragment(): buff lands next to skb in the lost queue. Today, for
  an skb RACK has unlinked, list_add() builds a 2-node ring that belongs
  to no list.
- Undo in fast recovery: everything in the lost queue was sent before
  everything still in tsorted_sent_queue, so this is a
  list_splice_init() at the head. O(1), no walk, no timestamp compare.

The "often" is the RTO case: tcp_timeout_mark_lost() leaves the skbs it
marks in tsorted_sent_queue, and they can be older than what RACK moves
to the lost queue afterwards. So undo needs a check: splice at the head
if tsorted_sent_queue is empty or the lost tail was sent before the sent
head, otherwise merge the two sorted lists (the forward walk from Neal's
patch, without the EVER_RETRANS test).

Cost is one list_head in tcp_sock and an INIT_LIST_HEAD() in
tcp_init_sock(), tcp_create_openreq_child() and tcp_write_queue_purge().
Reneged skbs are on neither list and would stay as they are today.
Neal's point about per-socket state is fair, but I think 16 bytes is a
reasonable price for not needing the RTO fallback at all.

With that, B is back in tsorted_sent_queue after the undo at .490 in
your scenario. tcp_undo_cwnd_reduction() sets tp->rack.advanced, RACK
looks at B in the same ACK (sent around .413, rack.rtt_us 40ms from C,
reo_wnd around 10ms), marks it lost again and it is retransmitted
immediately. The test then has the same shape as 2/3 (untested):

  .490 < . 1:1(0) ack 1001 win 20000 <TS val 1390 ecr 210,sack 2001:3001>
   +0~+.05 > P. 1001:2001(1000) ack 1 <...>
   +0 %{ assert tcpi_retransmits == 0, tcpi_retransmits }%

and it fails on current kernels, which is what we want from a selftest
shipped with a fix.

If Neal and Yuchung still prefer the stateless version I can live with
it, but then the 3/3 changelog should say that the test passes without
1/3 and documents a known limitation.

[1] https://lore.kernel.org/netdev/CAL4WiipKWgA-EcFWDQd3t7nBwU7AnkLvqs6j--he-dR-SAgqiw@mail.gmail.com/

Thanks.