[PATCH net-2.6 0/2] [TCP]: Fix bidirectional brokeness

[PATCH net-2.6 0/2] [TCP]: Fix bidirectional brokeness

[Ilpo Järvinen]

Hi Dave,

While testing frto with bidirection TCP a while (months) ago, I 
encountered time-seq graphs which made absolutely no sense as if 
recoveries only completed after RTO. As a result, I noticed that 
rate-halving has problem when a flow is bidirection but testing the
patch has been on my todo list for ages.  ...Finally, here it is...
...Please think the first one a bit because there might be some
corner cases with reno.

While testing it I came across with an additional issue that can
occur with bidirectional traffic. And, even better, the second fix
seems to also solves a third issue which affects both unidirectional
and bidirectional flows, though it's a marginal case (cumulative
ACK that causes a larger number of new SACKed skbs). I've never
seen that third one to occur but it's there if you get enough ACK
losses, subsequent ACKs (if one gets them) do solve it so that's
not a very bad issue to begin with...

I've verified these from time-seq graphs on top of tcp-2.6, which
had some additional (mostly cleanup and the rebase I promised you
earlier) though I added the tp->fackets_out > tp->reordering check
afterwards as it seems necessary to avoid going to lost marker too
often (wouldn't have had any effect in my test case anyway).

...Please consider to net-2.6 and to stable too.

These will generate you some hassle when you rebase tcp-2.6. Btw, you 
forgot to push tcp-2.6 out last time though I could assume it's
state... :-) In case you're going to now push it out, could you please
drop "[TCP]: Remove num_acked>0 checks from cong.ctrl mods pkts_acked"
from it as it seems to be out of place in tcp-2.6, I can resubmit it
to net-2.6.24 when you open it (unless you want to put it to net-2.6 
directly as it's rather trivial one).


-- 
 i.

[PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[Ilpo Järvinen]

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


Actually, the ratehalving seems to work too well, as cwnd is
reduced on every second ACK even though the packets in flight
remains unchanged. Recoveries in a bidirectional flows suffer
quite badly because of this, both NewReno and SACK are affected.

After this patch, rate halving is performed for ACK only if
packets in flight was supposedly changed too.

Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
---
 net/ipv4/tcp_input.c |   23 +++++++++++++----------
 1 files changed, 13 insertions(+), 10 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 0163051..767f92c 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -1848,19 +1848,22 @@ static inline u32 tcp_cwnd_min(const struct sock *sk)
 }
 
 /* Decrease cwnd each second ack. */
-static void tcp_cwnd_down(struct sock *sk)
+static void tcp_cwnd_down(struct sock *sk, int flag)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 	int decr = tp->snd_cwnd_cnt + 1;
+	
+	if ((flag&FLAG_FORWARD_PROGRESS) ||
+	    (IsReno(tp) && !(flag&FLAG_NOT_DUP))) {
+		tp->snd_cwnd_cnt = decr&1;
+		decr >>= 1;
 
-	tp->snd_cwnd_cnt = decr&1;
-	decr >>= 1;
+		if (decr && tp->snd_cwnd > tcp_cwnd_min(sk))
+			tp->snd_cwnd -= decr;
 
-	if (decr && tp->snd_cwnd > tcp_cwnd_min(sk))
-		tp->snd_cwnd -= decr;
-
-	tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp)+1);
-	tp->snd_cwnd_stamp = tcp_time_stamp;
+		tp->snd_cwnd = min(tp->snd_cwnd, tcp_packets_in_flight(tp)+1);
+		tp->snd_cwnd_stamp = tcp_time_stamp;
+	}
 }
 
 /* Nothing was retransmitted or returned timestamp is less
@@ -2057,7 +2060,7 @@ static void tcp_try_to_open(struct sock *sk, int flag)
 		}
 		tcp_moderate_cwnd(tp);
 	} else {
-		tcp_cwnd_down(sk);
+		tcp_cwnd_down(sk, flag);
 	}
 }
 
@@ -2257,7 +2260,7 @@ tcp_fastretrans_alert(struct sock *sk, u32 prior_snd_una,
 
 	if (is_dupack || tcp_head_timedout(sk))
 		tcp_update_scoreboard(sk);
-	tcp_cwnd_down(sk);
+	tcp_cwnd_down(sk, flag);
 	tcp_xmit_retransmit_queue(sk);
 }
 
-- 
1.5.0.6

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[David Miller]

From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
Date: Mon, 30 Jul 2007 20:18:45 +0300 (EEST)

> Actually, the ratehalving seems to work too well, as cwnd is
> reduced on every second ACK even though the packets in flight
> remains unchanged. Recoveries in a bidirectional flows suffer
> quite badly because of this, both NewReno and SACK are affected.
> 
> After this patch, rate halving is performed for ACK only if
> packets in flight was supposedly changed too.
> 
> Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>

This fix looks great, and I see no potential problems with
Reno after doing a bit of auditing.

Applied and I'll push to -stable too.

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[Ilpo Järvinen]

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

On Mon, 30 Jul 2007, David Miller wrote:

> From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
> Date: Mon, 30 Jul 2007 20:18:45 +0300 (EEST)
> 
> > Actually, the ratehalving seems to work too well, as cwnd is
> > reduced on every second ACK even though the packets in flight
> > remains unchanged. Recoveries in a bidirectional flows suffer
> > quite badly because of this, both NewReno and SACK are affected.
> > 
> > After this patch, rate halving is performed for ACK only if
> > packets in flight was supposedly changed too.
> > 
> > Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
> 
> This fix looks great, and I see no potential problems with
> Reno after doing a bit of auditing.
> 
> Applied and I'll push to -stable too.

I think it's probably good to add tp->snd_una != prior_snd_una
check there too... It's not going to make a large difference,
mostly just to be conservative when skb collapse stuff got done
(and maybe to annoy cheaters too though I couldn't at this point
figure out how they could abuse it)...

...I think I can come up with that on Wednesday, so please hold
stable push until that.

-- 
 i.

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[David Miller]

From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
Date: Tue, 31 Jul 2007 07:59:10 +0300 (EEST)

> I think it's probably good to add tp->snd_una != prior_snd_una
> check there too... It's not going to make a large difference,
> mostly just to be conservative when skb collapse stuff got done
> (and maybe to annoy cheaters too though I couldn't at this point
> figure out how they could abuse it)...
> 
> ...I think I can come up with that on Wednesday, so please hold
> stable push until that.

It'll definitely need to wait at least a day as I cannot even make TCP
or UDP connections out from my machine with the current net-2.6 tree,
and this is what I'm debugging at the moment.

I'm hoping that it's just something stupid like the make not
rebuilding everything necessary after I changed the __u16's into
__u32's in skb_frag_t.

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[Stephen Hemminger]

On Mon, 30 Jul 2007 22:21:12 -0700 (PDT)
David Miller <davem@davemloft.net> wrote:

> From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
> Date: Tue, 31 Jul 2007 07:59:10 +0300 (EEST)
> 
> > I think it's probably good to add tp->snd_una != prior_snd_una
> > check there too... It's not going to make a large difference,
> > mostly just to be conservative when skb collapse stuff got done
> > (and maybe to annoy cheaters too though I couldn't at this point
> > figure out how they could abuse it)...
> > 
> > ...I think I can come up with that on Wednesday, so please hold
> > stable push until that.
> 
> It'll definitely need to wait at least a day as I cannot even make TCP
> or UDP connections out from my machine with the current net-2.6 tree,
> and this is what I'm debugging at the moment.
> 
> I'm hoping that it's just something stupid like the make not
> rebuilding everything necessary after I changed the __u16's into
> __u32's in skb_frag_t.

I running tests over emulator this morning.
Hopefully, this will fix the window collapse that occurs on startup
of large queue sizes.

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[David Miller]

From: Stephen Hemminger <shemminger@linux-foundation.org>
Date: Tue, 31 Jul 2007 10:51:13 +0100

> On Mon, 30 Jul 2007 22:21:12 -0700 (PDT)
> David Miller <davem@davemloft.net> wrote:
> 
> > From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
> > Date: Tue, 31 Jul 2007 07:59:10 +0300 (EEST)
> > 
> > > I think it's probably good to add tp->snd_una != prior_snd_una
> > > check there too... It's not going to make a large difference,
> > > mostly just to be conservative when skb collapse stuff got done
> > > (and maybe to annoy cheaters too though I couldn't at this point
> > > figure out how they could abuse it)...
> > > 
> > > ...I think I can come up with that on Wednesday, so please hold
> > > stable push until that.
> > 
> > It'll definitely need to wait at least a day as I cannot even make TCP
> > or UDP connections out from my machine with the current net-2.6 tree,
> > and this is what I'm debugging at the moment.
> > 
> > I'm hoping that it's just something stupid like the make not
> > rebuilding everything necessary after I changed the __u16's into
> > __u32's in skb_frag_t.
> 
> I running tests over emulator this morning.
> Hopefully, this will fix the window collapse that occurs on startup
> of large queue sizes.

Great.

For the record the bug I was chasing was an IPSEC issue which
Herbert fixed a few moments ago.

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[Stephen Hemminger]

[-- Attachment #1: Type: text/plain, Size: 419 bytes --]

I noticed no difference in the two flow tests.  That is not a bad thing, just
that this test doesn't hit that code.

The anomaly is that first flow does slow start then gets loss and ends up
reducing it's window size all the way to the bottom, finally it recovers.
This happens with Cubic, H-TCP and others as well; if the queue in the
network is large enough, they don't handle the initial loss well.

See the graph.


[-- Attachment #2: reno2-after.png --]
[-- Type: image/png, Size: 6773 bytes --]

Re: [PATCH net-2.6 1/2] [TCP]: Fix ratehalving with bidirectional flows

[Ilpo Järvinen]

On Tue, 31 Jul 2007, Stephen Hemminger wrote:

> I noticed no difference in the two flow tests.  That is not a bad thing, just
> that this test doesn't hit that code.

...I'm not too sure about your test setup but the bugs I fixed only cover 
cases that occur if flow is bidirectional (and obviously active in both 
directions at the same time), they won't occur in a case of unidirectional 
transfer or in request-reply style connections (well, in the latter 
case if there's some overlap, it can have effect but that's usually 
not significant)...

In case of bidirectional transfers, you *should* see some difference as 
previously the fast recovery was _very_ broken. Of course there could be 
other issue with large cwnd TCP that hides it by going to RTO still, but 
at least over 384k/200ms link (DBP sized buffers, IIRC), these change
behavior very dramatically, mainly in the initial slow-start overshoot 
recovery because in there losses per RTT is so high number compared to 
what is experienced later on. One or a few losses are usually recovered 
without RTO when congestion happens later on.

> The anomaly is that first flow does slow start then gets loss and ends up
> reducing it's window size all the way to the bottom, finally it recovers.
> This happens with Cubic, H-TCP and others as well; if the queue in the
> network is large enough, they don't handle the initial loss well.

...TCP related stuff that changed in /proc/net/netstat might shed 
some light to this if none of the given explinations please you... :-)

> See the graph.

What exactly do you mean by "RENO" in the title, I mean what's tcp_sack 
set to? There is occassionally a bit confusion in that respect in the 
terminology @ netdev, I've used to reno refering to non-SACK stuff 
elsewhere but in here that's not always the case... Usually it's possible 
to derive the correct interpretation from the context, but in this case 
I'm not too sure... :-)

What I often have often seen with non-SACK TCP is that initial slow-start 
exhausts even very large advertised window on high DBP link and then due 
to draining of ACK feedback, gets RTOed... That usually shows up as long 
lasting recovery where one segment per RTT is recovered and new data is 
being sent as duplicate ACKs arrive with nearly constant rate until the 
window limit is hit (but I cannot see such periond in the graph you 
posted, so I guess it's not the explanation in this case). And if your 
"RENO" refers to something with SACK, that's not going to explain it 
anyway.

...Another nasty one I know is RED+ECN, though I'd say it's a bit far 
fetched one, as ECN cannot be used nicely in retransmission, 
a retransmission gets dropped instead of marking if RED wanted to mark.
I guess that doesn't occur in your test case either?


-- 
 i.

[PATCH net-2.6 2/2] [TCP]: Bidir flow must not disregard SACK blocks for lost marking

[Ilpo Järvinen]

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


It's possible that new SACK blocks that should trigger new LOST
markings arrive with new data (which previously made is_dupack
false). In addition, I think this fixes a case where we get
a cumulative ACK with enough SACK blocks to trigger the fast
recovery (is_dupack would be false there too).

I'm not completely pleased with this solution because readability
of the code is somewhat questionable as 'is_dupack' in SACK case
is no longer about dupacks only but would mean something like
'lost_marker_work_todo' too... But because of Eifel stuff done
in CA_Recovery, the FLAG_DATA_SACKED check cannot be placed to
the if statement which seems attractive solution. Nevertheless,
I didn't like adding another variable just for that either... :-)

Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>
---
 net/ipv4/tcp_input.c |    5 ++++-
 1 files changed, 4 insertions(+), 1 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 767f92c..cfe6ac7 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -2109,7 +2109,10 @@ tcp_fastretrans_alert(struct sock *sk, u32 prior_snd_una,
 {
 	struct inet_connection_sock *icsk = inet_csk(sk);
 	struct tcp_sock *tp = tcp_sk(sk);
-	int is_dupack = (tp->snd_una == prior_snd_una && !(flag&FLAG_NOT_DUP));
+	int is_dupack = (tp->snd_una == prior_snd_una &&
+			 (!(flag&FLAG_NOT_DUP) ||
+			  ((flag&FLAG_DATA_SACKED) &&
+			   (tp->fackets_out > tp->reordering))));
 
 	/* Some technical things:
 	 * 1. Reno does not count dupacks (sacked_out) automatically. */
-- 
1.5.0.6

Re: [PATCH net-2.6 2/2] [TCP]: Bidir flow must not disregard SACK blocks for lost marking

[David Miller]

From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
Date: Mon, 30 Jul 2007 20:19:40 +0300 (EEST)

> It's possible that new SACK blocks that should trigger new LOST
> markings arrive with new data (which previously made is_dupack
> false). In addition, I think this fixes a case where we get
> a cumulative ACK with enough SACK blocks to trigger the fast
> recovery (is_dupack would be false there too).
> 
> I'm not completely pleased with this solution because readability
> of the code is somewhat questionable as 'is_dupack' in SACK case
> is no longer about dupacks only but would mean something like
> 'lost_marker_work_todo' too... But because of Eifel stuff done
> in CA_Recovery, the FLAG_DATA_SACKED check cannot be placed to
> the if statement which seems attractive solution. Nevertheless,
> I didn't like adding another variable just for that either... :-)
> 
> Signed-off-by: Ilpo Järvinen <ilpo.jarvinen@helsinki.fi>

I've applied this as well.

I don't mind the complex conditionals so much in loss
handling, they are almost inevitable.  However I believe
they could be simplified as a lot of pieces of code ask
similar if not identical questions.

We could ask several of these things up-front, regardless
of path we will take (reno, DSACK, reorder, FRTO, etc.)
and pass the answers along in a bitmask.  We do that to
some extent already with how we analyze the retransmit
queue at the beginning of ACK processing.

Re: [PATCH net-2.6 2/2] [TCP]: Bidir flow must not disregard SACK blocks for lost marking

[Ilpo Järvinen]

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

On Mon, 30 Jul 2007, David Miller wrote:

> From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
> Date: Mon, 30 Jul 2007 20:19:40 +0300 (EEST)
> 
> > I'm not completely pleased with this solution because readability
> > of the code is somewhat questionable as 'is_dupack' in SACK case
> > is no longer about dupacks only but would mean something like
> > 'lost_marker_work_todo' too... But because of Eifel stuff done
> > in CA_Recovery, the FLAG_DATA_SACKED check cannot be placed to
> > the if statement which seems attractive solution. Nevertheless,
> > I didn't like adding another variable just for that either... :-)
> 
> I don't mind the complex conditionals so much in loss
> handling, they are almost inevitable. However I believe
> they could be simplified as a lot of pieces of code ask
> similar if not identical questions.
>
> We could ask several of these things up-front, regardless
> of path we will take (reno, DSACK, reorder, FRTO, etc.)
> and pass the answers along in a bitmask.  We do that to
> some extent already with how we analyze the retransmit
> queue at the beginning of ACK processing.

That's true, ...and my thought too as I was thinking of
adding FLAG_SND_UNA_ADVANCED (!= FLAG_DATA_ACKED) (or it's
opposite as I haven't yet checked which way it is more
useful). That could help in many places and probably reduces
compare pressure here and there as the bitmask operation
can be done in one compare where it now has to do two
compares, one for snd_una and other for the flag.

...I'll keep an eye on other possible bits too... :-)

-- 
 i.

Re: [PATCH net-2.6 0/2] [TCP]: Fix bidirectional brokeness

[David Miller]

From: "Ilpo_Järvinen" <ilpo.jarvinen@helsinki.fi>
Date: Mon, 30 Jul 2007 20:16:54 +0300 (EEST)

> These will generate you some hassle when you rebase tcp-2.6. Btw, you 
> forgot to push tcp-2.6 out last time though I could assume it's
> state... :-) In case you're going to now push it out, could you please
> drop "[TCP]: Remove num_acked>0 checks from cong.ctrl mods pkts_acked"
> from it as it seems to be out of place in tcp-2.6, I can resubmit it
> to net-2.6.24 when you open it (unless you want to put it to net-2.6 
> directly as it's rather trivial one).

It has been in the back of my mind to take care of the tcp-2.6
tree and rebase it for you and others.

I'll take a stab at that soon hopefully.

Thanks for reminding me.