[RFC][PATCH 1/2] TCP: fix lost retransmit detection

[RFC][PATCH 1/2] TCP: fix lost retransmit detection

[TAKANO Ryousei]

This patch allows to detect loss of retransmitted packets more
accurately by using the highest end sequence number among SACK 
blocks.  Before the retransmission queue is scanned, the highest
end sequence number (high_end_seq) is retrieved, and this value
is compared with the ack_seq of each packet.

Signed-off-by: Ryousei Takano <takano-ryousei@aist.go.jp>
Signed-off-by: Yuetsu Kodama <y-kodama@aist.go.jp>
---
 net/ipv4/tcp_input.c |   14 +++++++++++---
 1 files changed, 11 insertions(+), 3 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index bbad2cd..12db4b3 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -978,6 +978,7 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
 	int cached_fack_count;
 	int i;
 	int first_sack_index;
+	__u32 high_end_seq;
 
 	if (!tp->sacked_out)
 		tp->fackets_out = 0;
@@ -1012,6 +1013,14 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
 	if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
 		return 0;
 
+	/* Retrieve the highest end_seq among SACK blocks. */
+	high_end_seq = ntohl(sp[0].end_seq);
+	for (i = 1; i < num_sacks; i++) {
+		__u32 end_seq = ntohl(sp[i].end_seq);
+		if (after(end_seq, high_end_seq))
+			high_end_seq = end_seq;
+	}
+
 	/* SACK fastpath:
 	 * if the only SACK change is the increase of the end_seq of
 	 * the first block then only apply that SACK block
@@ -1161,9 +1170,8 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
 			}
 
 			if ((sacked&TCPCB_SACKED_RETRANS) &&
-			    after(end_seq, TCP_SKB_CB(skb)->ack_seq) &&
-			    (!lost_retrans || after(end_seq, lost_retrans)))
-				lost_retrans = end_seq;
+			    after(high_end_seq, TCP_SKB_CB(skb)->ack_seq))
+				lost_retrans = high_end_seq;
 
 			if (!in_sack)
 				continue;
-- 
1.5.2.4

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[Ilpo Järvinen]

On Thu, 4 Oct 2007, TAKANO Ryousei wrote:

> This patch allows to detect loss of retransmitted packets more
> accurately by using the highest end sequence number among SACK 
> blocks.  Before the retransmission queue is scanned, the highest
> end sequence number (high_end_seq) is retrieved, and this value
> is compared with the ack_seq of each packet.
> 
> Signed-off-by: Ryousei Takano <takano-ryousei@aist.go.jp>
> Signed-off-by: Yuetsu Kodama <y-kodama@aist.go.jp>
> ---
>  net/ipv4/tcp_input.c |   14 +++++++++++---
>  1 files changed, 11 insertions(+), 3 deletions(-)
> 
> diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> index bbad2cd..12db4b3 100644
> --- a/net/ipv4/tcp_input.c
> +++ b/net/ipv4/tcp_input.c
> @@ -978,6 +978,7 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
>  	int cached_fack_count;
>  	int i;
>  	int first_sack_index;
> +	__u32 high_end_seq;

No __-types when not visible to userspace please.

>
>  	if (!tp->sacked_out)
>  		tp->fackets_out = 0;
> @@ -1012,6 +1013,14 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
>  	if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
>  		return 0;
>  
> +	/* Retrieve the highest end_seq among SACK blocks. */
> +	high_end_seq = ntohl(sp[0].end_seq);
> +	for (i = 1; i < num_sacks; i++) {
> +		__u32 end_seq = ntohl(sp[i].end_seq);
> +		if (after(end_seq, high_end_seq))
> +			high_end_seq = end_seq;
> +	}
> +

There's one problem... Net-2.6.24 tree includes SACK block validator 
which is being done in the marking loop. The SACK blocks would not yet be 
validated in that position, yet this code should be protected by the 
validation! My intention is to move the validator earlier anyway (yet to 
be split into smaller logical patches), see:

http://marc.info/?l=linux-netdev&m=119062989408053&w=2

>  	/* SACK fastpath:
>  	 * if the only SACK change is the increase of the end_seq of
>  	 * the first block then only apply that SACK block
> @@ -1161,9 +1170,8 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
>  			}
>  
>  			if ((sacked&TCPCB_SACKED_RETRANS) &&
> -			    after(end_seq, TCP_SKB_CB(skb)->ack_seq) &&
> -			    (!lost_retrans || after(end_seq, lost_retrans)))
> -				lost_retrans = end_seq;
> +			    after(high_end_seq, TCP_SKB_CB(skb)->ack_seq))
> +				lost_retrans = high_end_seq;

Just couple of thoughts, not that this change itself is incorrect...

In case sacktag uses fastpath, this code won't be executed for the skb's 
that we would like to check (those with SACKED_RETRANS set, that are 
below the fastpath_skb_hint). We will eventually deal with the whole queue 
when fastpath_skb_hint gets set to NULL, with the next cumulative ACK that 
fully ACKs an skb at the latest. Maybe there's a need for a larger surgery 
than this to fix it. I think we need additional field to tcp_sock to avoid 
doing a full-walk per ACK:

Keep minimum of TCP_SKB_CB(skb)->ack_seq of rexmitted segments in 
tcp_sock, when that's exceeded by SACK block, do a full-walk in the 
lost_retrans worker loop like the old code does...


In future, please base your work to current development tree instead of 
linus' tree (net-2.6.24 at this point of time, there's also tcp-2.6 but 
it's currently a bit outdated).


-- 
 i.

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[TAKANO Ryousei]

From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
Date: Fri, 5 Oct 2007 13:02:07 +0300 (EEST)

> On Thu, 4 Oct 2007, TAKANO Ryousei wrote:
> 
> > This patch allows to detect loss of retransmitted packets more
> > accurately by using the highest end sequence number among SACK 
> > blocks.  Before the retransmission queue is scanned, the highest
> > end sequence number (high_end_seq) is retrieved, and this value
> > is compared with the ack_seq of each packet.
> > 
> > Signed-off-by: Ryousei Takano <takano-ryousei@aist.go.jp>
> > Signed-off-by: Yuetsu Kodama <y-kodama@aist.go.jp>
> > ---
> >  net/ipv4/tcp_input.c |   14 +++++++++++---
> >  1 files changed, 11 insertions(+), 3 deletions(-)
> > 
> > diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
> > index bbad2cd..12db4b3 100644
> > --- a/net/ipv4/tcp_input.c
> > +++ b/net/ipv4/tcp_input.c
> > @@ -978,6 +978,7 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
> >  	int cached_fack_count;
> >  	int i;
> >  	int first_sack_index;
> > +	__u32 high_end_seq;
> 
> No __-types when not visible to userspace please.
> 
I will fix it.

> >
> >  	if (!tp->sacked_out)
> >  		tp->fackets_out = 0;
> > @@ -1012,6 +1013,14 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
> >  	if (before(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
> >  		return 0;
> >  
> > +	/* Retrieve the highest end_seq among SACK blocks. */
> > +	high_end_seq = ntohl(sp[0].end_seq);
> > +	for (i = 1; i < num_sacks; i++) {
> > +		__u32 end_seq = ntohl(sp[i].end_seq);
> > +		if (after(end_seq, high_end_seq))
> > +			high_end_seq = end_seq;
> > +	}
> > +
> 
> There's one problem... Net-2.6.24 tree includes SACK block validator 
> which is being done in the marking loop. The SACK blocks would not yet be 
> validated in that position, yet this code should be protected by the 
> validation! My intention is to move the validator earlier anyway (yet to 
> be split into smaller logical patches), see:
> 
> http://marc.info/?l=linux-netdev&m=119062989408053&w=2
> 
I will check the net-2.6.24 tree and your patch.

> >  	/* SACK fastpath:
> >  	 * if the only SACK change is the increase of the end_seq of
> >  	 * the first block then only apply that SACK block
> > @@ -1161,9 +1170,8 @@ tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_
> >  			}
> >  
> >  			if ((sacked&TCPCB_SACKED_RETRANS) &&
> > -			    after(end_seq, TCP_SKB_CB(skb)->ack_seq) &&
> > -			    (!lost_retrans || after(end_seq, lost_retrans)))
> > -				lost_retrans = end_seq;
> > +			    after(high_end_seq, TCP_SKB_CB(skb)->ack_seq))
> > +				lost_retrans = high_end_seq;
> 
> Just couple of thoughts, not that this change itself is incorrect...
> 
> In case sacktag uses fastpath, this code won't be executed for the skb's 
> that we would like to check (those with SACKED_RETRANS set, that are 
> below the fastpath_skb_hint). We will eventually deal with the whole queue 
> when fastpath_skb_hint gets set to NULL, with the next cumulative ACK that 
> fully ACKs an skb at the latest. Maybe there's a need for a larger surgery 
> than this to fix it. I think we need additional field to tcp_sock to avoid 
> doing a full-walk per ACK:
> 
I think the problem occurs in slowpath. For example, in case when the receiver
detects and sends back a new SACK block, the sender may fail to detect loss
of a retransmitted packet.

> Keep minimum of TCP_SKB_CB(skb)->ack_seq of rexmitted segments in 
> tcp_sock, when that's exceeded by SACK block, do a full-walk in the 
> lost_retrans worker loop like the old code does...
> 
> 
> In future, please base your work to current development tree instead of 
> linus' tree (net-2.6.24 at this point of time, there's also tcp-2.6 but 
> it's currently a bit outdated).
> 
Thanks for your suggestion. SACK processing has a heavy workload and 
it is complex. I agree to make efforts toward a more generic solution. 
Your recv_sack_cache patch seems valuable. I will continue to work in 
the net-2.6.24 tree, and resend our patches. 
Anyway, first of all, I would like to share this problem with kernel 
developers.

BTW, what is difference among netdev-2.6, net-2.6 (net-2.6.24), and 
tcp-2.6? I am not familiar with linux kernel development process.

> 
> -- 
>  i.

Regards,
Ryousei Takano

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[David Miller]

From: TAKANO Ryousei <takano@axe-inc.co.jp>
Date: Sun, 07 Oct 2007 14:51:00 +0900 (JST)

> BTW, what is difference among netdev-2.6, net-2.6 (net-2.6.24), and 
> tcp-2.6? I am not familiar with linux kernel development process.

net-2.6.24 tree is current new development

net-2.6 tree is only bug fixes

tcp-2.6 is an old abandonded tree that holds lots of old
TCP work, most of which is merged already, but one part
(my RB-Tree SACK patches) are not integrated yet.

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[TAKANO Ryousei]

From: David Miller <davem@davemloft.net>
Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
Date: Sat, 06 Oct 2007 23:17:14 -0700 (PDT)

> From: TAKANO Ryousei <takano@axe-inc.co.jp>
> Date: Sun, 07 Oct 2007 14:51:00 +0900 (JST)
> 
> > BTW, what is difference among netdev-2.6, net-2.6 (net-2.6.24), and 
> > tcp-2.6? I am not familiar with linux kernel development process.
> 
> net-2.6.24 tree is current new development
> 
> net-2.6 tree is only bug fixes
> 
> tcp-2.6 is an old abandonded tree that holds lots of old
> TCP work, most of which is merged already, but one part
> (my RB-Tree SACK patches) are not integrated yet.

Thanks, and I got it.

I need to check the related recent posts (SACK block validation, sacktag 
cache usage, and RT-tree SACK) on this list.

Ryousei Takano

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[Ilpo Järvinen]

...Dropped DaveM from cc, I guess he knows the things I describe below 
already... :-)

On Sat, 6 Oct 2007, David Miller wrote:

> From: TAKANO Ryousei <takano@axe-inc.co.jp>
> Date: Sun, 07 Oct 2007 14:51:00 +0900 (JST)
> 
> > BTW, what is difference among netdev-2.6, 

netdev-2.6 is for network device drivers (stuff under drivers/net)

> net-2.6 (net-2.6.24), and 
> > tcp-2.6? I am not familiar with linux kernel development process.
> 
> net-2.6.24 tree is current new development
> 
> net-2.6 tree is only bug fixes
> 
> tcp-2.6 is an old abandonded tree that holds lots of old
> TCP work, most of which is merged already, but one part
> (my RB-Tree SACK patches) are not integrated yet.

In addition, when Linus releases a new kernel (2.6.23), the net-2.6.24 
becomes net-2.6 (the old one ceases to exist). At some point of 2.6.24-rc 
series, net-2.6.25 gets opened by DaveM, usually it's not available right 
after closure of 2.6.24 merge window. ...Then again, the trees are 
again rotated when a next official release is made...


-- 
 i.

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[Ilpo Järvinen]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2312 bytes --]

On Sun, 7 Oct 2007, TAKANO Ryousei wrote:

> From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
> Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
> Date: Fri, 5 Oct 2007 13:02:07 +0300 (EEST)
> 
> > On Thu, 4 Oct 2007, TAKANO Ryousei wrote:
> > 
> > In case sacktag uses fastpath, this code won't be executed for the skb's 
> > that we would like to check (those with SACKED_RETRANS set, that are 
> > below the fastpath_skb_hint). We will eventually deal with the whole queue 
> > when fastpath_skb_hint gets set to NULL, with the next cumulative ACK that 
> > fully ACKs an skb at the latest. Maybe there's a need for a larger surgery 
> > than this to fix it. I think we need additional field to tcp_sock to avoid 
> > doing a full-walk per ACK:
>
> I think the problem occurs in slowpath. For example, in case when the receiver
> detects and sends back a new SACK block, the sender may fail to detect loss
> of a retransmitted packet.

...No, the slow path is very likely to _correct_ the problem! The problem 
occurs because fastpath _skips_ processing of skbs below fastpath_skb_hint 
whereas slowpath starts from tcp_write_queue_head. The retransmitted skbs 
we're interested in reside exactly on that skipped range.

Currently fastpath_skb_hint is cleared rather often when it would not be 
mandatory, e.g., when a cumulative ACK arrives, thus slow-path is forced 
often enough for this problem to not show up too often in any real 
scenario, yet it's broken as is and should be fixed. ...It's actually 
something which is on a way for any solution which reduces the number of 
walked skb per ACK.

> > In future, please base your work to current development tree instead of 
> > linus' tree (net-2.6.24 at this point of time, there's also tcp-2.6 but 
> > it's currently a bit outdated).
> 
> Thanks for your suggestion. SACK processing has a heavy workload and 
> it is complex. I agree to make efforts toward a more generic solution. 
> Your recv_sack_cache patch seems valuable.

Agreed, and as is, it's getting more and more expensive to do. The current 
code is doing more and more processing compared to how much new SACK 
information was actually received. ...However, doing a large surgery like 
that and maintaining full correctness at the same time scares me a bit...


-- 
 i.

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[TAKANO Ryousei]

From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
Date: Mon, 8 Oct 2007 14:11:55 +0300 (EEST)

> On Sun, 7 Oct 2007, TAKANO Ryousei wrote:
> 
> > From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
> > Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
> > Date: Fri, 5 Oct 2007 13:02:07 +0300 (EEST)
> > 
> > > On Thu, 4 Oct 2007, TAKANO Ryousei wrote:
> > > 
> > > In case sacktag uses fastpath, this code won't be executed for the skb's 
> > > that we would like to check (those with SACKED_RETRANS set, that are 
> > > below the fastpath_skb_hint). We will eventually deal with the whole queue 
> > > when fastpath_skb_hint gets set to NULL, with the next cumulative ACK that 
> > > fully ACKs an skb at the latest. Maybe there's a need for a larger surgery 
> > > than this to fix it. I think we need additional field to tcp_sock to avoid 
> > > doing a full-walk per ACK:
> >
> > I think the problem occurs in slowpath. For example, in case when the receiver
> > detects and sends back a new SACK block, the sender may fail to detect loss
> > of a retransmitted packet.
> 
> ...No, the slow path is very likely to _correct_ the problem! The problem 
> occurs because fastpath _skips_ processing of skbs below fastpath_skb_hint 
> whereas slowpath starts from tcp_write_queue_head. The retransmitted skbs 
> we're interested in reside exactly on that skipped range.
> 
Sorry, my explanaton is insufficient.
This problem occurs even if we are in the slowpath.

For example, consider the case when the state of the retransmission queue is
as shown in Fig.1 (http://projects.gtrc.aist.go.jp/gnet/meeting/sack-bug.html).
There are 13 packets in the retransmission queue, P(0) and P(7) are 
retransmitted, and P(1) to P(9) except P(7) are already SACKed.

If only a SACK block "SACK(8,11)" is received, P(0) is re-transmitted, 
because the ack_seq of P(0) is smaller than the end sequence number (11) 
of the SACK block. However, if the ACK packet has SACK(8,11) and SACK(1,3), 
these SACK blocks are sorted, and SACK(1,3) is process from P(0) to P(2) 
first. In this case, P(0) is not detected as lost because the ack_seq of 
P(0) is not smaller than the end sequence number (3) of this SACK block. 
Next, SACK(8,11) is scanned from P(3) to P(10). P(0) is not checked here, 
and the loss is not detected.

Is it corrent?

Ryousei Takano

Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection

[Ilpo Järvinen]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2629 bytes --]

On Tue, 9 Oct 2007, TAKANO Ryousei wrote:

> From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
> Subject: Re: [RFC][PATCH 1/2] TCP: fix lost retransmit detection
> Date: Mon, 8 Oct 2007 14:11:55 +0300 (EEST)
> 
> > On Sun, 7 Oct 2007, TAKANO Ryousei wrote:
> > 
> > > From: "Ilpo Järvinen" <ilpo.jarvinen@helsinki.fi>
> > > 
> > > > Just couple of thoughts, not that this change itself is incorrect...

...Added this line back, it's important. :-)

> > > > In case sacktag uses fastpath, this code won't be executed for the skb's 
> > > > that we would like to check (those with SACKED_RETRANS set, that are 
> > > > below the fastpath_skb_hint). We will eventually deal with the whole queue 
> > > > when fastpath_skb_hint gets set to NULL, with the next cumulative ACK that 
> > > > fully ACKs an skb at the latest. Maybe there's a need for a larger surgery 
> > > > than this to fix it. I think we need additional field to tcp_sock to avoid 
> > > > doing a full-walk per ACK:
> > >
> > > I think the problem occurs in slowpath. For example, in case when the receiver
> > > detects and sends back a new SACK block, the sender may fail to detect loss
> > > of a retransmitted packet.
> > 
> > ...No, the slow path is very likely to _correct_ the problem! The problem 
> > occurs because fastpath _skips_ processing of skbs below fastpath_skb_hint 
> > whereas slowpath starts from tcp_write_queue_head. The retransmitted skbs 
> > we're interested in reside exactly on that skipped range.
> > 
> Sorry, my explanaton is insufficient.
> This problem occurs even if we are in the slowpath.
>
> [...long explination snip...]
>
> Is it corrent?

Yes, we're dealing with two related, but different problems here. I 
understood well what you're trying to fix, and even acknowledged your 
change (see what I added back from my original reply above). The far
worse problem which I describe, however, occurs with fastpath only (well, 
very unlikely to occur with slow-path but it could in theory), has been 
like this since the hints were added. And it's preventing the execution
of this portion you fixed (until slowpath is taken).

...What makes the other problem even nastier is the fact that it
becomes more and more significant when fastpath (or it's equivalent)
skips more and more skb processing. It's good that we noticed it
now...

I tried to do a fix to that other problem, it seems that the solution
will be intertwined with the problem you're describing so that I in
fact ended removing the code block where your key modification is and
placing  somewhat similar sequence gathering elsewhere... Posting it 
shortly.

-- 
 i.