[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

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);

[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

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.

[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 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.

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

[Neal Cardwell]

From: Neal Cardwell <ncardwell@google.com>

On Fri, Oct 9, 2026 at 1:47#AM Eric Dumazet <edumazet@kernel.org> wrote:

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

Thanks, Eric. Given that you are OK with the space overhead for a new
tp->tsorted_lost_queue field, I think it would be quite nice to use your
suggested approach, since it should give us better loss recovery behavior.

FWIW, I asked an LLM to code up your idea, and below is what it came up with,
in case that is useful for discussion or using. It also proposed 2 packetdrill
tests (one that claims "This is the case that Eric suggested for segments with
TCPCB_EVER_RETRANS."), which I can post if there is interest.

---

From 919ec4af823300734104e42e855793ebd958c401 Mon Sep 17 00:00:00 2001
From: Neal Cardwell <ncardwell@google.com>
Date: Fri, 9 Oct 2026 07:18:41 -0700
Subject: [PATCH 1/2] tcp: restore RACK-lost skbs to tsorted_sent_queue on undo

RACK unlinks each skb that it marks lost from tp->tsorted_sent_queue, so
that later scans do not walk it again. The skb only returns to the list
when it is retransmitted. If an undo clears TCPCB_LOST before that, the
skb is on no list at all: RACK can never mark it lost again,
tcp_xmit_retransmit_queue() skips it, and only an RTO repairs it. This
happens for example after a partial undo in fast recovery, when PRR has
not yet retransmitted all the skbs that RACK marked lost.

As suggested by Eric, move the skbs that RACK marks lost to a new list,
tp->tsorted_lost_queue, instead of unlinking them. RACK scans the sent
queue in send order, and the skbs that a later scan marks lost were sent
later, so the lost queue stays sorted by send time without any sorting.
Nothing else needs to change: a retransmit moves the skb to the tail of
the sent queue, a SACK or cumulative ACK unlinks it, and tcp_fragment()
links the new skb next to the old one, in whichever list that is.
(Today, for an skb that RACK unlinked, tcp_fragment() builds a two-node
ring that is on no list.)

On undo, put the lost queue back into the sent queue. Usually every lost
skb was sent before every skb that is still in the sent queue, and one
list_splice_init() at the head does it. But the skbs that
tcp_timeout_mark_lost() marks stay in the sent queue, and RACK may later
move skbs sent after them to the lost queue. In that case, merge the two
sorted lists in one pass.

Unlike skipping skbs with TCPCB_EVER_RETRANS, this also restores skbs
that a TLP probed, or whose retransmit was lost, so that they do not
have to wait for an RTO either.

The cost is one list_head in tcp_sock, outside the fast path cache line
groups.

Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
Reported-by: Neil Ramaswamy <nramaswamy@openai.com>
Closes: https://lore.kernel.org/netdev/cover.1791506907.git.nramaswamy@openai.com/
Suggested-by: Eric Dumazet <edumazet@kernel.org>
Link: https://lore.kernel.org/netdev/CAL4Wiip9RyA-2=p0SVwBcn-oe0864FqqF3QMTCX_7=+ErcJp6Q@mail.gmail.com/
---
 .../networking/net_cachelines/tcp_sock.rst    |  1 +
 include/linux/tcp.h                           |  3 ++
 net/ipv4/tcp.c                                |  2 +
 net/ipv4/tcp_input.c                          | 51 +++++++++++++++++++
 net/ipv4/tcp_minisocks.c                      |  1 +
 net/ipv4/tcp_recovery.c                       |  9 +++-
 6 files changed, 66 insertions(+), 1 deletion(-)

diff --git a/Documentation/networking/net_cachelines/tcp_sock.rst b/Documentation/networking/net_cachelines/tcp_sock.rst
index 0f6088c4ab8bb..c5a4c06a5765d 100644
--- a/Documentation/networking/net_cachelines/tcp_sock.rst
+++ b/Documentation/networking/net_cachelines/tcp_sock.rst
@@ -34,6 +34,7 @@ u32                           compressed_ack_rcv_nxt
 u32                           tsoffset                read_mostly         read_mostly         tcp_established_options(tx);tcp_fast_parse_options(rx)
 struct list_head              tsq_node
 struct list_head              tsorted_sent_queue      read_write                              tcp_update_skb_after_send
+struct list_head              tsorted_lost_queue
 u32                           snd_wl1                                     read_mostly         tcp_may_update_window
 u32                           snd_wnd                 read_mostly         read_mostly         tcp_wnd_end,tcp_tso_should_defer(tx);tcp_fast_path_on(rx)
 u32                           max_window              read_mostly                             tcp_bound_to_half_wnd,forced_push
diff --git a/include/linux/tcp.h b/include/linux/tcp.h
index 6a8c77719322f..98699d599f11e 100644
--- a/include/linux/tcp.h
+++ b/include/linux/tcp.h
@@ -377,6 +377,9 @@ struct tcp_sock {
 				 */
 	u32	compressed_ack_rcv_nxt;
 	struct list_head tsq_node; /* anchor in tsq_tasklet.head list */
+	struct list_head tsorted_lost_queue; /* time-sorted skbs that RACK
+					      * marked lost, until resent
+					      */
 
 	/* Information of the most recently (s)acked skb */
 	struct tcp_rack {
diff --git a/net/ipv4/tcp.c b/net/ipv4/tcp.c
index 562752352afe4..6cbf4d79824e2 100644
--- a/net/ipv4/tcp.c
+++ b/net/ipv4/tcp.c
@@ -428,6 +428,7 @@ void tcp_init_sock(struct sock *sk)
 	tcp_init_xmit_timers(sk);
 	INIT_LIST_HEAD(&tp->tsq_node);
 	INIT_LIST_HEAD(&tp->tsorted_sent_queue);
+	INIT_LIST_HEAD(&tp->tsorted_lost_queue);
 
 	icsk->icsk_rto = TCP_TIMEOUT_INIT;
 
@@ -3352,6 +3353,7 @@ void tcp_write_queue_purge(struct sock *sk)
 	}
 	tcp_rtx_queue_purge(sk);
 	INIT_LIST_HEAD(&tcp_sk(sk)->tsorted_sent_queue);
+	INIT_LIST_HEAD(&tcp_sk(sk)->tsorted_lost_queue);
 	tcp_clear_all_retrans_hints(tcp_sk(sk));
 	tcp_sk(sk)->packets_out = 0;
 	inet_csk(sk)->icsk_backoff = 0;
diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 92bc60716f33d..a18ee1bcf0138 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -2840,6 +2840,56 @@ static void DBGUNDO(struct sock *sk, const char *msg)
 #endif
 }
 
+/* Was @a sent after @b, in the order of tp->tsorted_sent_queue? */
+static bool tcp_tsorted_after(const struct sk_buff *a, const struct sk_buff *b)
+{
+	return tcp_skb_sent_after(a->skb_mstamp_ns, b->skb_mstamp_ns,
+				  TCP_SKB_CB(a)->end_seq,
+				  TCP_SKB_CB(b)->end_seq);
+}
+
+/* Undo cleared the lost marks, so move the skbs that RACK marked lost back
+ * to tp->tsorted_sent_queue, in send order, where RACK can detect their
+ * loss again.
+ */
+static void tcp_tsorted_restore_lost(struct tcp_sock *tp)
+{
+	struct list_head *sent = &tp->tsorted_sent_queue;
+	struct list_head *lost = &tp->tsorted_lost_queue;
+	struct sk_buff *skb, *tmp, *pos;
+
+	if (list_empty(lost))
+		return;
+
+	/* Usually every lost skb was sent before every skb that is still in
+	 * the sent queue, so the lost queue goes back at the head. But the
+	 * skbs that tcp_timeout_mark_lost() marks stay in the sent queue,
+	 * and RACK may later move skbs sent after them to the lost queue.
+	 * Then merge the two queues, which are both sorted by send time.
+	 */
+	pos = list_first_entry(sent, struct sk_buff, tcp_tsorted_anchor);
+	if (list_empty(sent) ||
+	    !tcp_tsorted_after(list_last_entry(lost, struct sk_buff,
+					       tcp_tsorted_anchor), pos)) {
+		list_splice_init(lost, sent);
+		return;
+	}
+
+	list_for_each_entry_safe(skb, tmp, lost, tcp_tsorted_anchor) {
+		/* Find the first skb in the sent queue sent after skb. */
+		list_for_each_entry_from(pos, sent, tcp_tsorted_anchor) {
+			if (tcp_tsorted_after(pos, skb))
+				break;
+		}
+		if (list_entry_is_head(pos, sent, tcp_tsorted_anchor)) {
+			list_splice_tail_init(lost, sent);
+			return;
+		}
+		list_move_tail(&skb->tcp_tsorted_anchor,
+			       &pos->tcp_tsorted_anchor);
+	}
+}
+
 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
@@ -2850,6 +2900,7 @@ static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
 		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
 			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
 		}
+		tcp_tsorted_restore_lost(tp);
 		tp->lost_out = 0;
 		tcp_clear_all_retrans_hints(tp);
 	}
diff --git a/net/ipv4/tcp_minisocks.c b/net/ipv4/tcp_minisocks.c
index 0ddfd5af6e58f..e73db6b70d079 100644
--- a/net/ipv4/tcp_minisocks.c
+++ b/net/ipv4/tcp_minisocks.c
@@ -580,6 +580,7 @@ struct sock *tcp_create_openreq_child(const struct sock *sk,
 
 	INIT_LIST_HEAD(&newtp->tsq_node);
 	INIT_LIST_HEAD(&newtp->tsorted_sent_queue);
+	INIT_LIST_HEAD(&newtp->tsorted_lost_queue);
 
 	tcp_init_wl(newtp, treq->rcv_isn);
 
diff --git a/net/ipv4/tcp_recovery.c b/net/ipv4/tcp_recovery.c
index 1396467510736..4258b00e28570 100644
--- a/net/ipv4/tcp_recovery.c
+++ b/net/ipv4/tcp_recovery.c
@@ -84,7 +84,14 @@ static void tcp_rack_detect_loss(struct sock *sk, u32 *reo_timeout)
 		remaining = tcp_rack_skb_timeout(tp, skb, reo_wnd);
 		if (remaining <= 0) {
 			tcp_mark_skb_lost(sk, skb);
-			list_del_init(&skb->tcp_tsorted_anchor);
+			/* Move the skb to the lost queue instead of just
+			 * unlinking it, so that undo can put it back. Each
+			 * scan marks skbs in send order, and the skbs a later
+			 * scan marks were sent later, so the lost queue stays
+			 * sorted by send time.
+			 */
+			list_move_tail(&skb->tcp_tsorted_anchor,
+				       &tp->tsorted_lost_queue);
 		} else {
 			/* Record maximum wait time */
 			*reo_timeout = max_t(u32, *reo_timeout, remaining);
-- 
2.56.0.385.gd3acb90ef8-goog