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

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

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

I've been investigating a bug in TCP where RACK loses track of segments
after partial undo happens. At a high-level, RACK can react to a SACK
by scanning its sorted transmission queue for segments that exceed its
RACK timeout, mark those segments as lost, and remove them from its
sorted queue. However, receiving an ACK with a TSecr less than the
first retansmission timestamp of the recovery episode can trigger
partial undo, which removes the lost flag from segments not yet
cumulatively ACK'd but does not ensure that they are in (or are added to)
the RACK transmission queue.

The symptom that I observe is that a long tail of hole segments can
"escape" RACK and then only get sent out by the retransmission timer,
which can take a long time and even be serial for many lost segments.

A conceptual example below illustrates this situation; I'm intentionally
excluding TSecrs/byte ranges/etc. when not relevant.

   TCP A                            TCP B
   
                             Assume TS.Recent = 200 to start.

    A, TSval = 210 --- <delayed>
    B, TSval = 211 --- <delayed>
    C, TSval = 212 ----------------> arrives
    D, TSval = 213 --- <lost>
    E, TSval = 214 ----------------> arrives
    
                   <---------------- SACK C + E, TSecr = 200
    A', TSval = 216 --- <delayed>
    B', TSval = 217 --------
    D marked lost           |
                            B' ----> arrives, ACK delayed
                    
                    original A ----> A fills leading gap,
                                     TS.Recent = 210
                                     
                   <---------------- ACK through C, SACK E, TSecr = 210
    retrans_out = 0
    210 < 216 permits partial undo
    D lost flag is cleared
    D remains absent from RACK list
    

A bit of commentary on this diagram:

1. The timestamps I'm using are for the purposes of showing the
   partial undo comparison; these aren't an exact schedule with the
   timeouts RACK would use. See the packetdrill for that.
2. A and B are also marked as lost and removed from the RACK list.
   However, PRR only allows A and B to be retransmitted. D
   being marked missing consists of being marked as lost and,
   critically, not being added to the RACK list.
3. I delayed the B' ACK because if it is sent back, this may let the
   sender retransmit D before partial undo happens.
4. At the end of our diagram, D can only be rescued with the
   retransmission timer.

There is also another more catastrophic situation in which partial undo
might happen when a stale TS.Recent is echo replied [1] when handling
out-of-order ACKs, and I've seen this cause the RTO to jump to over 100
seconds. But this combination should not happen if [1] is merged.

I see two options for fixing this, and I provided the first as a patch:

  1. When partial undo runs, we make sure that a segment whose lost flag
     is cleared is added back to the RACK list.
  2. RACK does not remove from the RACK transmission list until a segment
     is acknowledged; I think this is a bad approach because you would
     end up scanning already-marked-as-lost segments every time you do
     loss detection.

Without a fix as such, packet "D" in my included packetdrill takes around
400ms to be retransmitted via RTO. With the attached patch, D is
retransmitted within 50ms of the partial ACK, without an RTO.


[1] https://lore.kernel.org/all/20260921222609.50824-4-jeffjo@openai.com/

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

 net/ipv4/tcp_input.c                          | 33 ++++++++++++
 ...tcp_partial_undo-restores-to-rack-list.pkt | 54 +++++++++++++++++++
 2 files changed, 87 insertions(+)
 create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-to-rack-list.pkt

base-commit: 11536ee3d3e0b1bd35b6f3f8df55a6053eb0c71d

[PATCH net 1/2] 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 and can lead to
long retransmission delays. Restoring them to the RACK list allows them to
be reconsidered for fast retransmission in the future. To do this, we first
sort the segments whose lost flag is being cleared, and reinsert them into
the RACK list (which is sorted by transmission time).

Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
Assisted-by: LLM sparse
---
 net/ipv4/tcp_input.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 92bc60716f33..38ac07c8b38f 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -69,6 +69,7 @@
 #include <linux/module.h>
 #include <linux/sysctl.h>
 #include <linux/kernel.h>
+#include <linux/list_sort.h>
 #include <linux/prefetch.h>
 #include <linux/bitops.h>
 #include <net/dst.h>
@@ -2840,16 +2841,48 @@ static void DBGUNDO(struct sock *sk, const char *msg)
 #endif
 }
 
+static int tcp_rack_skb_cmp(void *priv, 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);
+}
+
 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 
 	if (unmark_loss) {
+		LIST_HEAD(restored);
 		struct sk_buff *skb;
 
 		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
+			if ((TCP_SKB_CB(skb)->sacked & TCPCB_LOST) == TCPCB_LOST)
+				list_move_tail(&skb->tcp_tsorted_anchor, &restored);
 			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
 		}
+		if (!list_empty(&restored)) {
+			struct list_head *pos = &tp->tsorted_sent_queue;
+
+			/* Ensure lost skbs are added in transmission order */
+			list_sort(NULL, &restored, tcp_rack_skb_cmp);
+			while (!list_empty(&restored)) {
+				struct list_head *entry = restored.next;
+
+				while (pos->next != &tp->tsorted_sent_queue &&
+				       !tcp_rack_skb_cmp(NULL, pos->next, entry))
+					pos = pos->next;
+				list_move(entry, pos);
+				pos = entry;
+			}
+		}
 		tp->lost_out = 0;
 		tcp_clear_all_retrans_hints(tp);
 	}

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

[Jiayuan Chen]

On 9/26/26 8:25 AM, 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 and can lead to
> long retransmission delays. Restoring them to the RACK list allows them to
> be reconsidered for fast retransmission in the future. To do this, we first
> sort the segments whose lost flag is being cleared, and reinsert them into
> the RACK list (which is sorted by transmission time).
>
> Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
> Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
> Assisted-by: LLM sparse
> ---
>   net/ipv4/tcp_input.c | 33 +++++++++++++++++++++++++++++++++
>   1 file changed, 33 insertions(+)
>
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index 92bc60716f33..38ac07c8b38f 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -69,6 +69,7 @@
>   #include <linux/module.h>
>   #include <linux/sysctl.h>
>   #include <linux/kernel.h>
> +#include <linux/list_sort.h>
>   #include <linux/prefetch.h>
>   #include <linux/bitops.h>
>   #include <net/dst.h>
> @@ -2840,16 +2841,48 @@ static void DBGUNDO(struct sock *sk, const char *msg)
>   #endif
>   }
>   
> +static int tcp_rack_skb_cmp(void *priv, 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);
> +}
> +
>   static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
>   {
>   	struct tcp_sock *tp = tcp_sk(sk);
>   
>   	if (unmark_loss) {
> +		LIST_HEAD(restored);
>   		struct sk_buff *skb;
>   
>   		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
> +			if ((TCP_SKB_CB(skb)->sacked & TCPCB_LOST) == TCPCB_LOST)
> +				list_move_tail(&skb->tcp_tsorted_anchor, &restored);


I think the simplest way to solve the problems is just drop 
'list_del_init(&skb->tcp_tsorted_anchor);' in tcp_rack_detect_loss(),
although it will reduce the efficiency of RACK loss detection ?

Leave it to maintainers.


>   			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
>   		}
> +		if (!list_empty(&restored)) {
> +			struct list_head *pos = &tp->tsorted_sent_queue;
> +
> +			/* Ensure lost skbs are added in transmission order */
> +			list_sort(NULL, &restored, tcp_rack_skb_cmp);
> +			while (!list_empty(&restored)) {
> +				struct list_head *entry = restored.next;
> +
> +				while (pos->next != &tp->tsorted_sent_queue &&
> +				       !tcp_rack_skb_cmp(NULL, pos->next, entry))
> +					pos = pos->next;
> +				list_move(entry, pos);
> +				pos = entry;
> +			}
> +		}
>   		tp->lost_out = 0;
>   		tcp_clear_all_retrans_hints(tp);
>   	}

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

[Kuniyuki Iwashima]

From: Jiayuan Chen <jiayuan.chen@linux.dev>
Date: Wed, 30 Sep 2026 10:13:42 +0800
> On 9/26/26 8:25 AM, 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 and can lead to
> > long retransmission delays. Restoring them to the RACK list allows them to
> > be reconsidered for fast retransmission in the future. To do this, we first
> > sort the segments whose lost flag is being cleared, and reinsert them into
> > the RACK list (which is sorted by transmission time).
> >
> > Fixes: 043b87d7599e ("tcp: more efficient RACK loss detection")
> > Signed-off-by: Neil Ramaswamy <nramaswamy@openai.com>
> > Assisted-by: LLM sparse
> > ---
> >   net/ipv4/tcp_input.c | 33 +++++++++++++++++++++++++++++++++
> >   1 file changed, 33 insertions(+)
> >
> > diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> > index 92bc60716f33..38ac07c8b38f 100644
> > --- a/net/ipv4/tcp_input.c
> > +++ b/net/ipv4/tcp_input.c
> > @@ -69,6 +69,7 @@
> >   #include <linux/module.h>
> >   #include <linux/sysctl.h>
> >   #include <linux/kernel.h>
> > +#include <linux/list_sort.h>
> >   #include <linux/prefetch.h>
> >   #include <linux/bitops.h>
> >   #include <net/dst.h>
> > @@ -2840,16 +2841,48 @@ static void DBGUNDO(struct sock *sk, const char *msg)
> >   #endif
> >   }
> >   
> > +static int tcp_rack_skb_cmp(void *priv, 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);
> > +}
> > +
> >   static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
> >   {
> >   	struct tcp_sock *tp = tcp_sk(sk);
> >   
> >   	if (unmark_loss) {
> > +		LIST_HEAD(restored);
> >   		struct sk_buff *skb;
> >   
> >   		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
> > +			if ((TCP_SKB_CB(skb)->sacked & TCPCB_LOST) == TCPCB_LOST)

nit: "== TCPCB_LOST" is redundant


> > +				list_move_tail(&skb->tcp_tsorted_anchor, &restored);
> 
> 
> I think the simplest way to solve the problems is just drop 
> 'list_del_init(&skb->tcp_tsorted_anchor);' in tcp_rack_detect_loss(),
> although it will reduce the efficiency of RACK loss detection ?

It will almost revert the optimisation done by 043b87d7599e.

One sort + merging sorted lists during undo seems better
than reintroducing costs in the fast(er) path.


> 
> Leave it to maintainers.
> 
> 
> >   			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
> >   		}
> > +		if (!list_empty(&restored)) {
> > +			struct list_head *pos = &tp->tsorted_sent_queue;
> > +
> > +			/* Ensure lost skbs are added in transmission order */
> > +			list_sort(NULL, &restored, tcp_rack_skb_cmp);
> > +			while (!list_empty(&restored)) {
> > +				struct list_head *entry = restored.next;
> > +
> > +				while (pos->next != &tp->tsorted_sent_queue &&
> > +				       !tcp_rack_skb_cmp(NULL, pos->next, entry))
> > +					pos = pos->next;
> > +				list_move(entry, pos);
> > +				pos = entry;
> > +			}
> > +		}
> >   		tp->lost_out = 0;
> >   		tcp_clear_all_retrans_hints(tp);
> >   	}

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

[Jakub Kicinski]

On Fri, 25 Sep 2026 17:25:22 -0700 nramaswamy@openai.com wrote:
> Partial undo can clear the TCPCB_LOST flag on segments already removed from
> RACK's list, which prevents subsequent RACK loss detection and can lead to
> long retransmission delays. Restoring them to the RACK list allows them to
> be reconsidered for fast retransmission in the future. To do this, we first
> sort the segments whose lost flag is being cleared, and reinsert them into
> the RACK list (which is sorted by transmission time).

Could you add to the commit msg if this was found with an LLM scan
of the source code or its been seen in prod?

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

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

On Thu, 1 Oct 2026 16:07:20 -0700, Jakub Kicinski wrote:
> Could you add to the commit msg if this was found with an LLM scan
> of the source code or its been seen in prod?

Yes, I can add that to the commit message once review settles. 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] but I can't definitively say it's
the same root cause.

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

[PATCH net 2/2] 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..c07a2f8a5cbd
--- /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 D should
+// remain eligible for fast retransmission (critically, the timeout
+// retransmission counter should be 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>

Re: [PATCH net 0/2] tcp: preserve RACK tracking across partial undo

[nramaswamy]

From: Neil Ramaswamy <nramaswamy@openai.com>

Adding the maintainers/lists I missed on the original CC. Sorry for the
omission. The cover letter and both patches are available here:

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