Skip to contentSkip to conversation

tcp: Fix highest_sack and highest_sack_seq

PATCH In review Cambda Zhu 3 participants 7 messages Dec 27, 2019 – Dec 31, 2019

Subsystems (3)
lore
Share & tools
lore

Cambda Zhu

author
#0 lore raw

PATCH 1/1 tcp: Fix highest_sack and highest_sack_seq

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")
---
 net/ipv4/tcp_output.c | 3 +++
 1 file changed, 3 insertions(+)
net/ipv4/tcp_output.c +3 -0
index 1f7735ca8f22..58c92a7d671c 100644
@@ -72,6 +72,9 @@ static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
 	__skb_unlink(skb, &sk->sk_write_queue);
 	tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
 
+	if (tp->highest_sack == NULL)
+		tp->highest_sack = skb;
+
 	tp->packets_out += tcp_skb_pcount(skb);
 	if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
 		tcp_rearm_rto(sk);
Signature · 1 line
2.16.5
#1 lore raw
Quoted 27 lines · Cambda Zhu

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")
---
 net/ipv4/tcp_output.c | 3 +++
 1 file changed, 3 insertions(+)
net/ipv4/tcp_output.c +0 -0
index 1f7735ca8f22..58c92a7d671c 100644

net/ipv4/tcp_output.c static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb) · line 80

Quoted 9 lines
net/ipv4/tcp_output.c +3 -0
@@ -72,6 +72,9 @@ static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
 	__skb_unlink(skb, &sk->sk_write_queue);
 	tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
 
+	if (tp->highest_sack == NULL)
+		tp->highest_sack = skb;
+
 	tp->packets_out += tcp_skb_pcount(skb);
 	if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
 		tcp_rearm_rto(sk);

This patch seems to keep something in the fast path, even for flows never experiencing sacks.

Why would we always painfully maintain tp->highest_sack to the left most skb in the rtx queue ?

Given that tcp_highest_sack_seq() has an explicit check about tp->highest_sack being NULL, there is something I do not quite understand yet.

Why keeping this piece of code ?

    if (tp->highest_sack == NULL)
            return tp->snd_nxt;

Defensive programming should be replaced by better knowledge.

Can you provide more explanations, or maybe a packetdrill test ?

Maybe some other path (in slow path this time) misses a !tp->highest_sack test.

Thanks.

#2 lore raw
Quoted 54 lines · Eric Dumazet
Quoted 27 lines · Cambda Zhu

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")
---
 net/ipv4/tcp_output.c | 3 +++
 1 file changed, 3 insertions(+)
net/ipv4/tcp_output.c +0 -0
index 1f7735ca8f22..58c92a7d671c 100644

net/ipv4/tcp_output.c static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb) · line 80

Quoted 9 lines
net/ipv4/tcp_output.c +3 -0
@@ -72,6 +72,9 @@ static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
 	__skb_unlink(skb, &sk->sk_write_queue);
 	tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
 
+	if (tp->highest_sack == NULL)
+		tp->highest_sack = skb;
+
 	tp->packets_out += tcp_skb_pcount(skb);
 	if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
 		tcp_rearm_rto(sk);

This patch seems to keep something in the fast path, even for flows never experiencing sacks.

Why would we always painfully maintain tp->highest_sack to the left most skb in the rtx queue ?

Given that tcp_highest_sack_seq() has an explicit check about tp->highest_sack being NULL, there is something I do not quite understand yet.

Why keeping this piece of code ?

    if (tp->highest_sack == NULL)
            return tp->snd_nxt;
Quoted 8 lines

Defensive programming should be replaced by better knowledge.

Can you provide more explanations, or maybe a packetdrill test ?

Maybe some other path (in slow path this time) misses a !tp->highest_sack test.

Thanks.

Or maybe the real bug has been latent for years.

(added in commit 6859d49475d4 "[TCP]: Abstract tp->highest_sack accessing & point to next skb" )

include/net/tcp.h +1 -4
index e460ea7f767ba627972a63a974cae80357808366..32781fb5cf3a7aa1158c98cb87754b59dc922b1f 100644
@@ -1843,12 +1843,9 @@ static inline void tcp_push_pending_frames(struct sock *sk)
  */
 static inline u32 tcp_highest_sack_seq(struct tcp_sock *tp)
 {
-       if (!tp->sacked_out)
+       if (!tp->sacked_out || !tp->highest_sack)
                return tp->snd_una;
 
-       if (tp->highest_sack == NULL)
-               return tp->snd_nxt;
-
        return TCP_SKB_CB(tp->highest_sack)->seq;
 }
 
author
#4 lore raw
In reply to Eric Dumazet
Quoted 36 lines · Eric Dumazet
Quoted 29 lines · Cambda Zhu

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")

---
net/ipv4/tcp_output.c | 3 +++

1 file changed, 3 insertions(+)
net/ipv4/tcp_output.c +0 -0
index 1f7735ca8f22..58c92a7d671c 100644
@@ -72,6 +72,9 @@ static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
 	__skb_unlink(skb, &sk->sk_write_queue);
 	tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
 
Quoted 12 lines

net/ipv4/tcp_output.c static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb) · line 80

Quoted 7 lines
net/ipv4/tcp_output.c +3 -0
+	if (tp->highest_sack == NULL)
+		tp->highest_sack = skb;
+
 	tp->packets_out += tcp_skb_pcount(skb);
 	if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
 		tcp_rearm_rto(sk);

This patch seems to keep something in the fast path, even for flows never experiencing sacks.

I’ll update the patch to check tcp_is_sack(). It’s a good idea, thank you.

Quoted 10 lines

Why would we always painfully maintain tp->highest_sack to the left most skb in the rtx queue ?

Given that tcp_highest_sack_seq() has an explicit check about tp->highest_sack being NULL, there is something I do not quite understand yet.

Why keeping this piece of code ?

   if (tp->highest_sack == NULL)
           return tp->snd_nxt;

Before we replace tp->highest_sack with tp->highest_sack_seq, the highest_sack_seq is always gotten from the highest_sack skb. Unfortunately if the skb before tp->snd_nxt is sacked, we have no choice but to set tp->highest_sack to a special skb or value yet, such as the send head in the past and the NULL now.

In the past, if there’s no skb after the last sacked skb in the write queue, tp->highest_sack will be set to NULL and tcp_highest_sack_seq() will return tp->snd_nxt, which is equal to TCP_SKB_CB(skb_after_last_sack)->seq. And then if new data is sent, the tp->highest_sack must be replaced by the new skb, otherwise the tcp_highest_sack_seq() will return a higher seq and result in increasing tp->reordering when the skb which is after the last sack and before the last sent new skb.

Now we have the same issue. If the skb_rb_last() skb is sacked, tp->highest_sack is set to NULL. If new data is sent, tcp_highest_sack_seq() will return a higher seq than what we expect.

Here is my UGLY example:
Low High
#1 #2 #3(last sacked)

			       ^
			       |highest_sack_seq(NULL)
#1	#2	#3(last sacked)		#4		#5	#6
								  ^
								  |highest_sack_seq(NULL)
#1	#2	#3			#4(last sacked)	#5	#6
					{	reordering	  }
Quoted 7 lines

Defensive programming should be replaced by better knowledge.

Can you provide more explanations, or maybe a packetdrill test ?

Maybe some other path (in slow path this time) misses a !tp->highest_sack test.

Thanks.

I don’t know how to use a packetdrill test to reproduce this case, sorry. But I can reproduce it via network emulator with these parameters:

Server:
rack off, metric no saving, congestion control bbr

Client:
random loss 8%, fixed rtt 20 ms, 60 Mbps bandwidth with 100 packets queue and tail drop.

Thanks.

author
#3 lore raw
In reply to Eric Dumazet
Quoted 82 lines · Eric Dumazet
Quoted 54 lines · Eric Dumazet
Quoted 27 lines · Cambda Zhu

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")

---
net/ipv4/tcp_output.c | 3 +++

1 file changed, 3 insertions(+)
net/ipv4/tcp_output.c +0 -0
index 1f7735ca8f22..58c92a7d671c 100644

net/ipv4/tcp_output.c static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb) · line 80

Quoted 9 lines
net/ipv4/tcp_output.c +3 -0
@@ -72,6 +72,9 @@ static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
 	__skb_unlink(skb, &sk->sk_write_queue);
 	tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
 
+	if (tp->highest_sack == NULL)
+		tp->highest_sack = skb;
+
 	tp->packets_out += tcp_skb_pcount(skb);
 	if (!prior_packets || icsk->icsk_pending == ICSK_TIME_LOSS_PROBE)
 		tcp_rearm_rto(sk);

This patch seems to keep something in the fast path, even for flows never experiencing sacks.

Why would we always painfully maintain tp->highest_sack to the left most skb in the rtx queue ?

Given that tcp_highest_sack_seq() has an explicit check about tp->highest_sack being NULL, there is something I do not quite understand yet.

Why keeping this piece of code ?

   if (tp->highest_sack == NULL)
           return tp->snd_nxt;
Quoted 8 lines

Defensive programming should be replaced by better knowledge.

Can you provide more explanations, or maybe a packetdrill test ?

Maybe some other path (in slow path this time) misses a !tp->highest_sack test.

Thanks.

Or maybe the real bug has been latent for years.

(added in commit 6859d49475d4 "[TCP]: Abstract tp->highest_sack accessing & point to next skb" )

include/net/tcp.h +0 -0
index e460ea7f767ba627972a63a974cae80357808366..32781fb5cf3a7aa1158c98cb87754b59dc922b1f 100644
@@ -1843,12 +1843,9 @@ static inline void tcp_push_pending_frames(struct sock *sk)
 */
 static inline u32 tcp_highest_sack_seq(struct tcp_sock *tp)

include/net/tcp.h static inline void tcp_push_pending_frames(struct sock *sk) · line 1850

Quoted 10 lines
include/net/tcp.h +1 -4
 {
-       if (!tp->sacked_out)
+       if (!tp->sacked_out || !tp->highest_sack)
               return tp->snd_una;
 
-       if (tp->highest_sack == NULL)
-               return tp->snd_nxt;
-
       return TCP_SKB_CB(tp->highest_sack)->seq;
 }

The key is that we use skb but not seq to save the highest sack yet. I think it should be done in a better way. If we replace the next skb with the last sacked skb or seq after it, we need to change all of the sack processing about highest sack, which is worth to do in my opinion.

Thanks.

#5 lore raw
In reply to Cambda Zhu
Quoted 10 lines · Cambda Zhu

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

Quoted 7 lines

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")

Sadly I could not come to an alternative solution.

Thanks !

maintainer
#6 lore raw
In reply to Cambda Zhu

From: Cambda Zhu <[email protected]>
Date: Fri, 27 Dec 2019 16:52:37 +0800

Quoted 10 lines

From commit 50895b9de1d3 ("tcp: highest_sack fix"), the logic about setting tp->highest_sack to the head of the send queue was removed. Of course the logic is error prone, but it is logical. Before we remove the pointer to the highest sack skb and use the seq instead, we need to set tp->highest_sack to NULL when there is no skb after the last sack, and then replace NULL with the real skb when new skb inserted into the rtx queue, because the NULL means the highest sack seq is tp->snd_nxt. If tp->highest_sack is NULL and new data sent, the next ACK with sack option will increase tp->reordering unexpectedly.

Quoted 7 lines

This patch sets tp->highest_sack to the tail of the rtx queue if it's NULL and new data is sent. The patch keeps the rule that the highest_sack can only be maintained by sack processing, except for this only case.

Fixes 50895b9de1d3 ("tcp: highest_sack fix")

Applied and queued up for -stable, thanks.