tcp: correct the skip logic in tcp_sacktag_skip()
Subsystems (3)
PATCH 1/1 tcp: correct the skip logic in tcp_sacktag_skip()
tcp_sacktag_skip() directly return the input skb only if TCP_SKB_CB(skb)->seq>skip_to_seq,
this is not right, and the logic should be TCP_SKB_CB(skb)->seq>=skip_to_seq, for example if start_seq is equal to tcp_highest_sack_seq() , the start_seq is equal to seq of skb which is from tcp_highest_sack().
and on the other side ,when tcp_highest_sack_seq() < start_seq in tcp_sacktag_write_queue(),
the skb is from tcp_highest_sack() will be ignored in tcp_sacktag_skip(), so clean the logic also.
--- net/ipv4/tcp_input.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)
net/ipv4/tcp_input.c +2 -2
@@ -1809,7 +1809,7 @@ static struct sk_buff *tcp_sacktag_bsearch(struct sock *sk, u32 seq)static struct sk_buff *tcp_sacktag_skip (struct sk_buff *skb,struct sock *sk,u32 skip_to_seq) { -if (skb &&after (TCP_SKB_CB (skb)->seq, skip_to_seq)) +if (skb && !before (TCP_SKB_CB (skb)->seq, skip_to_seq))return skb;return tcp_sacktag_bsearch (sk, skip_to_seq);
@@ -1997,7 +1997,7 @@ tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb,continue ; } -if (!before (start_seq,tcp_highest_sack_seq (tp))) { +if (tcp_highest_sack_seq (tp) == start_seq) { skb =tcp_highest_sack (sk);if (!skb)break ;
Signature · 1 line
2.43.0
Paolo Abeni
maintainerQuoted 4 lines · Xin Guo
tcp_sacktag_skip()directly return the input skb only if TCP_SKB_CB(skb)->seq>skip_to_seq,
this is not right, and the logic should be TCP_SKB_CB(skb)->seq>=skip_to_seq,
Adding Kuniyuki
I'm not sure this statement is actually true. A more clear (and slightly more descriptive) commit message could help better understanding the issue. What is the bad behaviour you are observing?
Ideally a packetdrill test case to demonstrate it would help
Quoted 11 lines
for example
ifstart_seqis equal totcp_highest_sack_seq(), thestart_seqis equal to seq of skb which is fromtcp_highest_sack().
and on the other side ,whentcp_highest_sack_seq()<start_seqintcp_sacktag_write_queue(),
the skb is fromtcp_highest_sack()will be ignored intcp_sacktag_skip(), so clean the logic also.Fixes 75c119afe14f ("tcp: implement rb-tree based retransmit queue")
At very least the fixes tag looks wrong, because AFAICS such change did not modify the behaviour tcp_sacktag_skip.
Quoted 1 line
Signed-off-by Xin Guo <[email protected]>
Thanks,
Paolo
Hi Paolo,
Thanks for your review, let me explain in the thread first.
1)let me start from tcp_sacktag_skip, the definition as below:
static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk, u32 skip_to_seq)
{
if (skb && after(TCP_SKB_CB(skb)->seq, skip_to_seq))
return skb;
return tcp_sacktag_bsearch(sk, skip_to_seq);
}
the input skb is a hint to avoid search the RTX tree, and the condition is:skb->seq > skip_to_seq(so skip_to_seq cannot be included in skb), as below:
0----------------------------------------------|------------------>+ skb->seq 0--------------------|-------------------------------------------->+ skip_to_seq
2)let me check the code snippet in tcp_sacktag_write_queue() the code try to speed up the search by using tcp_highest_sack(), the code is from the rtx queue is a list, but now the rtx queue is a tree. the mean is that if the start_seq >=tcp_highest_sack_seq(), the we use skb=tcp_highest_sack() as a hint to speed up the lookup(avoid to lookup the tree).
so we can see that the skb->seq <=start_seq.
then if we use the skb and start_seq to call tcp_sacktag_skip(), the tcp_sacktag_skip will go for rtx tree lookup, so
code snippet does not take effect.
static inttcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb, u32 prior_snd_una, struct tcp_sacktag_state *state)
{
...
while (i < used_sacks) {
if (!before(start_seq, tcp_highest_sack_seq(tp))) { skb = tcp_highest_sack(sk);
if (!skb)
break;
}
skb = tcp_sacktag_skip(skb, sk, start_seq);
walk:
skb = tcp_sacktag_walk(skb, sk, next_dup, state,start_seq, end_seq, dup_sack);
advance_sp:
i++;
}
3) on the other side, let me show the logic in tcp_sacktag_bsearch, the logic is the skb->seq should be met:
seq=<skb->seq and seq<skb->end_seq
so the seq should be included in skb, the log is not consist with tcp_sacktag_skip().
static struct sk_buff *tcp_sacktag_bsearch(struct sock *sk, u32 seq) {
struct rb_node *parent, **p = &sk->tcp_rtx_queue.rb_node; struct sk_buff *skb;
while (*p) {
parent = *p;
skb = rb_to_skb(parent);
if (before(seq, TCP_SKB_CB(skb)->seq)) {
p = &parent->rb_left;
continue;
}
//[Xin Guo] at here seq=<skb->seq
if (!before(seq, TCP_SKB_CB(skb)->end_seq)) {
p = &parent->rb_right;
continue;
}
//[Xin Guo]at here seq<skb->end_seq
return skb;
}
return NULL;
}
i hope that it is more clear now, thanks.
Regards
Guo Xin.
Quoted 7 lines · Paolo Abeni
Quoted 4 lines · Xin Guo
tcp_sacktag_skip()directly return the input skb only if TCP_SKB_CB(skb)->seq>skip_to_seq,
this is not right, and the logic should be TCP_SKB_CB(skb)->seq>=skip_to_seq,
Quoted 7 lines
Adding Kuniyuki
I'm not sure this statement is actually true. A more clear (and slightly more descriptive) commit message could help better understanding the issue. What is the bad behaviour you are observing?
Ideally a packetdrill test case to demonstrate it would help
sorry that a packetdrill script cannot show the wrong behavior.
Quoted 11 lines
Quoted 11 lines
for example
ifstart_seqis equal totcp_highest_sack_seq(), thestart_seqis equal to seq of skb which is fromtcp_highest_sack().
and on the other side ,whentcp_highest_sack_seq()<start_seqintcp_sacktag_write_queue(),
the skb is fromtcp_highest_sack()will be ignored intcp_sacktag_skip(), so clean the logic also.
Quoted 4 lines
Quoted 1 line
Fixes 75c119afe14f ("tcp: implement rb-tree based retransmit queue")At very least the fixes tag looks wrong, because AFAICS such change did not modify the behaviour
tcp_sacktag_skip.
the commit 75c119afe14f ("tcp: implement rb-tree based retransmit queue") change the tcp_sacktag_skip(), and not be changed till now. so i think it is right.
Quoted 7 lines
Quoted 2 lines
Signed-off-by Xin Guo <[email protected]>Thanks,
Paolo
Neal Cardwell
maintainerQuoted 93 lines · Xin Guo
Hi Paolo,
Thanks for your review, let me explain in the thread first.
1)let me start fromtcp_sacktag_skip, the definition as below:
static structsk_buff*tcp_sacktag_skip(structsk_buff*skb, struct sock *sk, u32skip_to_seq)
{
if (skb &&after(TCP_SKB_CB(skb)->seq, skip_to_seq))
return skb;return
tcp_sacktag_bsearch(sk, skip_to_seq);
}
the input skb is a hint to avoid search the RTX tree, and the condition is:skb->seq>skip_to_seq(so skip_to_seq cannot be included in skb), as below:
0----------------------------------------------|------------------>+skb->seq0--------------------|-------------------------------------------->+skip_to_seq2)let me check the code snippet in
tcp_sacktag_write_queue()the code try to speed up the search by usingtcp_highest_sack(), the code is from the rtx queue is a list, but now the rtx queue is a tree. the mean is that if thestart_seq>=tcp_highest_sack_seq(), the we use skb=tcp_highest_sack() as a hint to speed up the lookup(avoid to lookup the tree).
so we can see that theskb->seq<=start_seq.
then if we use the skb andstart_seqto calltcp_sacktag_skip(), thetcp_sacktag_skipwill go for rtx tree lookup, so
code snippet does not take effect.static int
tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb, u32 prior_snd_una, struct tcp_sacktag_state *state)
{
...
while (i <used_sacks) {if (!before(start_seq,
tcp_highest_sack_seq(tp))) { skb =tcp_highest_sack(sk);
if (!skb)
break;
}
skb =tcp_sacktag_skip(skb, sk, start_seq);walk:
skb = tcp_sacktag_walk(skb, sk,next_dup, state,start_seq,end_seq,dup_sack);
advance_sp:
i++;
}3) on the other side, let me show the logic in
tcp_sacktag_bsearch, the logic is theskb->seqshould be met:seq=<skb->seq and seq<skb->end_seqso the seq should be included in skb, the log is not consist with
tcp_sacktag_skip().static struct
sk_buff*tcp_sacktag_bsearch(struct sock *sk, u32 seq) {
structrb_node*parent, **p =&sk->tcp_rtx_queue.rb_node; structsk_buff*skb;while (*p) {
parent = *p;
skb =rb_to_skb(parent);
if (before(seq, TCP_SKB_CB(skb)->seq)) {
p =&parent->rb_left;
continue;
}
//[Xin Guo] at here seq=<skb->seq
if (!before(seq, TCP_SKB_CB(skb)->end_seq)) {
p =&parent->rb_right;
continue;
}
//[Xin Guo]at here seq<skb->end_seq
return skb;
}
return NULL;
}i hope that it is more clear now, thanks.
Regards
Guo Xin.Quoted 7 lines · Paolo Abeni
Quoted 4 lines · Xin Guo
tcp_sacktag_skip()directly return the input skb only if TCP_SKB_CB(skb)->seq>skip_to_seq,
this is not right, and the logic should be TCP_SKB_CB(skb)->seq>=skip_to_seq,
Quoted 8 lines
Quoted 7 lines
Adding Kuniyuki
I'm not sure this statement is actually true. A more clear (and slightly more descriptive) commit message could help better understanding the issue. What is the bad behaviour you are observing?
Ideally a packetdrill test case to demonstrate it would help
sorry that a packetdrill script cannot show the wrong behavior.
I agree with Paolo that having a packetdrill test case for this kind of issue would be best.
Can you please explain why you are saying that a packetdrill script cannot show the incorrect behavior for this issue?
Usually packetdrill is a good fit for these kinds of protocol processing issues that do not involve performance or race conditions.
Here are examples of test cases that stress SACK processing behavior, if that helps:
https://github.com/google/packetdrill/tree/master/gtests/net/tcp/sack
Thanks,
neal
thanks neal,
the input parameter skb for tcp_sacktag_skip() is just a hint to avoid rtx tree lookup,
if the hint does not take effect, the tcp_sacktag_bsearch() can also find the right skb,
that is why it is hard to show the wrong behavior by packetdrill.
static struct sk_buff *tcp_sacktag_skip(struct sk_buff *skb, struct sock *sk, u32 skip_to_seq)
{
if (skb && after(TCP_SKB_CB(skb)->seq, skip_to_seq))
return skb;
return tcp_sacktag_bsearch(sk, skip_to_seq);
}
Regards
Guo Xin.
Quoted 119 lines · Neal Cardwell
Quoted 93 lines · Xin Guo
Hi Paolo,
Thanks for your review, let me explain in the thread first.
1)let me start fromtcp_sacktag_skip, the definition as below:
static structsk_buff*tcp_sacktag_skip(structsk_buff*skb, struct sock *sk, u32skip_to_seq)
{
if (skb &&after(TCP_SKB_CB(skb)->seq, skip_to_seq))
return skb;return
tcp_sacktag_bsearch(sk, skip_to_seq);
}
the input skb is a hint to avoid search the RTX tree, and the condition is:skb->seq>skip_to_seq(so skip_to_seq cannot be included in skb), as below:
0----------------------------------------------|------------------>+skb->seq0--------------------|-------------------------------------------->+skip_to_seq2)let me check the code snippet in
tcp_sacktag_write_queue()the code try to speed up the search by usingtcp_highest_sack(), the code is from the rtx queue is a list, but now the rtx queue is a tree. the mean is that if thestart_seq>=tcp_highest_sack_seq(), the we use skb=tcp_highest_sack() as a hint to speed up the lookup(avoid to lookup the tree).
so we can see that theskb->seq<=start_seq.
then if we use the skb andstart_seqto calltcp_sacktag_skip(), thetcp_sacktag_skipwill go for rtx tree lookup, so
code snippet does not take effect.static int
tcp_sacktag_write_queue(struct sock *sk, const struct sk_buff *ack_skb, u32 prior_snd_una, struct tcp_sacktag_state *state)
{
...
while (i <used_sacks) {if (!before(start_seq,
tcp_highest_sack_seq(tp))) { skb =tcp_highest_sack(sk);
if (!skb)
break;
}
skb =tcp_sacktag_skip(skb, sk, start_seq);walk:
skb = tcp_sacktag_walk(skb, sk,next_dup, state,start_seq,end_seq,dup_sack);
advance_sp:
i++;
}3) on the other side, let me show the logic in
tcp_sacktag_bsearch, the logic is theskb->seqshould be met:seq=<skb->seq and seq<skb->end_seqso the seq should be included in skb, the log is not consist with
tcp_sacktag_skip().static struct
sk_buff*tcp_sacktag_bsearch(struct sock *sk, u32 seq) {
structrb_node*parent, **p =&sk->tcp_rtx_queue.rb_node; structsk_buff*skb;while (*p) {
parent = *p;
skb =rb_to_skb(parent);
if (before(seq, TCP_SKB_CB(skb)->seq)) {
p =&parent->rb_left;
continue;
}
//[Xin Guo] at here seq=<skb->seq
if (!before(seq, TCP_SKB_CB(skb)->end_seq)) {
p =&parent->rb_right;
continue;
}
//[Xin Guo]at here seq<skb->end_seq
return skb;
}
return NULL;
}i hope that it is more clear now, thanks.
Regards
Guo Xin.Quoted 7 lines · Paolo Abeni
Quoted 4 lines · Xin Guo
tcp_sacktag_skip()directly return the input skb only if TCP_SKB_CB(skb)->seq>skip_to_seq,
this is not right, and the logic should be TCP_SKB_CB(skb)->seq>=skip_to_seq,Quoted 8 lines
Quoted 7 lines
Adding Kuniyuki
I'm not sure this statement is actually true. A more clear (and slightly more descriptive) commit message could help better understanding the issue. What is the bad behaviour you are observing?
Ideally a packetdrill test case to demonstrate it would help
sorry that a packetdrill script cannot show the wrong behavior.
I agree with Paolo that having a packetdrill test case for this kind of issue would be best.
Can you please explain why you are saying that a packetdrill script cannot show the incorrect behavior for this issue?
Usually packetdrill is a good fit for these kinds of protocol processing issues that do not involve performance or race conditions.
Here are examples of test cases that stress SACK processing behavior, if that helps:
https://github.com/google/packetdrill/tree/master/gtests/net/tcp/sackThanks,
neal