Re: [PATCH net v3 3/3] selftests: net: packetdrill: test RTO fallback after partial undo
From: Neal Cardwell
Date: Wed Oct 21 2026 - 09:50:49 EST
On Sun, Oct 11, 2026 at 9:26 PM <nramaswamy@xxxxxxxxxx> wrote:
> Did it propose 2 different packetdrill tests? If I understand Eric's
> suggestion correctly, he's proposing to just take the test from 3/3 and
> modify its final lines to ensure prompt retransmission without an RTO. Are
> your LLM's proposed tests covering cases beyond this?
Yes, the LLM suggested 2 tests. I've attached the kernel patch and the
test patch it proposed, which included two packetdrill tests.
I'm looking at your other observations and will follow up on those
when I get a sec. In the meantime I wanted to forward those 2 patches,
to answer your question and help provide context for the conversation.
:-)
Thanks,
neal
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/
Assisted-by: LLM
---
.../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
From 53cf6d91e2572e6673bf189b94c2bf0e772d57ef Mon Sep 17 00:00:00 2001
From: Neal Cardwell <ncardwell@google.com>
Date: Fri, 9 Oct 2026 07:40:56 -0700
Subject: [PATCH 2/2] selftests/net: packetdrill: test that undo restores
RACK-lost skbs
Add two tests for "tcp: restore RACK-lost skbs to tsorted_sent_queue on
undo":
tcp_partial_undo-restores-retransmitted-to-rack-list.pkt: a TLP probes
the tail segment, RACK then marks it lost, and a partial undo clears its
lost mark. The segment must go back on RACK's list, so that RACK marks
it lost again on the same ACK and it is retransmitted at once, rather
than after an RTO. This is the case that Eric suggested for segments
with TCPCB_EVER_RETRANS.
tcp_rto_undo-restores-to-rack-list.pkt: an RTO marks only the head of
the flight lost, RACK then marks later segments lost, and F-RTO undoes
the RTO. The segments that RACK marked lost must be merged back into
the sent queue between the rest of the head, which the RTO left there,
and the new data sent after the RTO, so that RACK can mark them lost
again and fast recovery repairs them without an RTO.
Both tests fail on kernels without the fix, where these segments are
repaired only by an RTO.
Assisted-by: LLM
---
...do-restores-retransmitted-to-rack-list.pkt | 64 ++++++++++++++
.../tcp_rto_undo-restores-to-rack-list.pkt | 86 +++++++++++++++++++
2 files changed, 150 insertions(+)
create mode 100644 tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-retransmitted-to-rack-list.pkt
create mode 100644 tools/testing/selftests/net/packetdrill/tcp_rto_undo-restores-to-rack-list.pkt
diff --git a/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-retransmitted-to-rack-list.pkt b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-retransmitted-to-rack-list.pkt
new file mode 100644
index 0000000000000..a42d07dbe271e
--- /dev/null
+++ b/tools/testing/selftests/net/packetdrill/tcp_partial_undo-restores-retransmitted-to-rack-list.pkt
@@ -0,0 +1,64 @@
+// SPDX-License-Identifier: GPL-2.0
+//
+// Test that undo puts a segment back on RACK's list even if it was
+// retransmitted before (here by a TLP probe), so that RACK can mark it
+// lost again and it is retransmitted at once, without waiting for an RTO.
+
+`./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, which sets TCPCB_EVER_RETRANS.
+ .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 after A and the TLP of B, and is SACKed with a 40 ms RTT.
+// RACK marks A and B lost, and A is retransmitted.
+ .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, so
+// we do a partial undo, which clears B's lost mark. B must be back on
+// RACK's list: RACK marks it lost again at once (it was sent before C),
+// and B is retransmitted in a new fast recovery, without an RTO.
+ .490 < . 1:1(0) ack 1001 win 20000 <TS val 1390 ecr 210,sack 2001:3001>
+ +0 > P. 1001:2001(1000) ack 1 <nop,nop,TS val 490 ecr 1390>
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Recovery, tcpi_ca_state
+assert tcpi_retransmits == 0, tcpi_retransmits
+assert tcpi_total_retrans == 3, tcpi_total_retrans
+}%
+
+// The retransmit of B fills the hole.
+ .530 < . 1:1(0) ack 3001 win 20000 <nop,nop,TS val 1430 ecr 490>
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Open, tcpi_ca_state
+assert tcpi_unacked == 0, tcpi_unacked
+assert tcpi_retransmits == 0, tcpi_retransmits
+}%
+ +0 `nstat -s | grep -q TcpExtTCPPartialUndo`
diff --git a/tools/testing/selftests/net/packetdrill/tcp_rto_undo-restores-to-rack-list.pkt b/tools/testing/selftests/net/packetdrill/tcp_rto_undo-restores-to-rack-list.pkt
new file mode 100644
index 0000000000000..2d8022041a384
--- /dev/null
+++ b/tools/testing/selftests/net/packetdrill/tcp_rto_undo-restores-to-rack-list.pkt
@@ -0,0 +1,86 @@
+// SPDX-License-Identifier: GPL-2.0
+//
+// Test that undo of an RTO puts the segments that RACK marked lost back
+// on RACK's list, in send order, although segments that the RTO marked
+// lost, which stay on the list, were sent before them.
+
+`./defaults.sh
+sysctl -q net.ipv4.tcp_early_retrans=0`
+
+ 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
+
+ +0 < S 0:0(0) win 32792 <mss 1000,sackOK,nop,nop,nop,wscale 7>
+ +0 > S. 0:0(0) ack 1 <mss 1460,nop,nop,sackOK,nop,wscale 8>
+ +.1 < . 1:1(0) ack 1 win 257
+ +0 accept(3, ..., ...) = 4
+
+// One round trip of data gives RACK an RTT of 100 ms, so that the RTO
+// below does not mark recently sent segments lost.
+ +0 write(4, ..., 1000) = 1000
+ +0 > P. 1:1001(1000) ack 1
+ +.1 < . 1:1(0) ack 1001 win 257
+
+// Send A (1001:5001), then B (5001:8001) 250 ms later, and C (8001:9001)
+// 30 ms after B.
+ +0 write(4, ..., 4000) = 4000
+ +0 > P. 1001:5001(4000) ack 1
+ +.25 write(4, ..., 3000) = 3000
+ +0 > P. 5001:8001(3000) ack 1
+ +.03 write(4, ..., 1000) = 1000
+ +0 > P. 8001:9001(1000) ack 1
+
+// The RTO fires 300 ms after A was sent. It marks only A lost, since B
+// and C were sent less than an RTT ago. It retransmits the head of A.
+ +.02~+.08 > . 1001:2001(1000) ack 1
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Loss, tcpi_ca_state
+assert tcpi_lost == 4, tcpi_lost
+}%
+
+// New data, held back by cwnd.
+ +.01 write(4, ..., 2000) = 2000
+
+// The head of A is ACKed. F-RTO sends the new data, D (9001:11001).
+// RACK marks B and C lost: they were sent before the retransmit of the
+// head of A, which was just delivered.
+ +.11 < . 1:1(0) ack 2001 win 257
+ +0 > P. 9001:11001(2000) ack 1
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Loss, tcpi_ca_state
+assert tcpi_lost == 7, tcpi_lost
+}%
+
+// C is SACKed. It was never retransmitted, so F-RTO undoes the RTO,
+// which clears all lost marks. B must go back on RACK's list between the
+// rest of A, which the RTO left there, and D. Then RACK at once marks
+// both the rest of A and B lost again, since both were sent before C,
+// and fast recovery starts. Without B back on RACK's list, only the rest
+// of A would be marked, and B would wait for an RTO.
+ +.02 < . 1:1(0) ack 2001 win 257 <sack 8001:9001,nop,nop>
+ +0 > . 2001:3001(1000) ack 1
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Recovery, tcpi_ca_state
+assert tcpi_lost == 6, tcpi_lost
+}%
+
+// D is SACKed. PRR retransmits the rest of A, and then B as more
+// packets are delivered.
+ +.08 < . 1:1(0) ack 2001 win 257 <sack 8001:11001,nop,nop>
+ +0 > P. 3001:5001(2000) ack 1
+ +.02 < . 1:1(0) ack 3001 win 257 <sack 8001:11001,nop,nop>
+ +0 > P. 5001:7001(2000) ack 1
+ +.02 < . 1:1(0) ack 5001 win 257 <sack 8001:11001,nop,nop>
+ +0 > P. 7001:8001(1000) ack 1
+
+// All retransmits are delivered. Recovery ends without an RTO.
+ +.05 < . 1:1(0) ack 11001 win 257
+ +0 %{
+assert tcpi_ca_state == TCP_CA_Open, tcpi_ca_state
+assert tcpi_unacked == 0, tcpi_unacked
+assert tcpi_retransmits == 0, tcpi_retransmits
+assert tcpi_total_retrans == 7, tcpi_total_retrans
+}%
+ +0 `nstat -s | grep -q TcpExtTCPSpuriousRTOs`
--
2.56.0.385.gd3acb90ef8-goog