[PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Yuchung Cheng]

The recent extension of F-RTO 89fe18e44 ("tcp: extend F-RTO
to catch more spurious timeouts") interacts badly with certain
broken middle-boxes.  These broken boxes modify and falsely raise
the receive window on the ACKs. During a timeout induced recovery,
F-RTO would send new data packets to probe if the timeout is false
or not. Since the receive window is falsely raised, the receiver
would silently drop these F-RTO packets. The recovery would take N
(exponentially backoff) timeouts to repair N packet losses.  A TCP
performance killer.

Due to this unfortunate situation, this patch removes this extension
to revert F-RTO back to the RFC specification.

Fixes: 89fe18e44f7e ("tcp: extend F-RTO to catch more spurious timeouts")
Signed-off-by: Yuchung Cheng <ycheng@google.com>
Signed-off-by: Neal Cardwell <ncardwell@google.com>
Signed-off-by: Soheil Hassas Yeganeh <soheil@google.com>
Signed-off-by: Eric Dumazet <edumazet@google.com>
---
 net/ipv4/tcp_input.c | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 2c1f59386a7b..659d1baefb2b 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -1935,6 +1935,7 @@ void tcp_enter_loss(struct sock *sk)
 	struct tcp_sock *tp = tcp_sk(sk);
 	struct net *net = sock_net(sk);
 	struct sk_buff *skb;
+	bool new_recovery = icsk->icsk_ca_state < TCP_CA_Recovery;
 	bool is_reneg;			/* is receiver reneging on SACKs? */
 	bool mark_lost;
 
@@ -1994,15 +1995,18 @@ void tcp_enter_loss(struct sock *sk)
 	tp->high_seq = tp->snd_nxt;
 	tcp_ecn_queue_cwr(tp);
 
-	/* F-RTO RFC5682 sec 3.1 step 1 mandates to disable F-RTO
-	 * if a previous recovery is underway, otherwise it may incorrectly
-	 * call a timeout spurious if some previously retransmitted packets
-	 * are s/acked (sec 3.2). We do not apply that retriction since
-	 * retransmitted skbs are permanently tagged with TCPCB_EVER_RETRANS
-	 * so FLAG_ORIG_SACK_ACKED is always correct. But we do disable F-RTO
-	 * on PTMU discovery to avoid sending new data.
+	/* F-RTO RFC5682 sec 3.1 step 1: retransmit SND.UNA if no previous
+	 * loss recovery is underway except recurring timeout(s) on
+	 * the same SND.UNA (sec 3.2). Disable F-RTO on path MTU probing
+	 *
+	 * In theory F-RTO can be used repeatedly during loss recovery.
+	 * In practice this interacts badly with broken middle-boxes that
+	 * falsely raise the receive window, which results in repeated
+	 * timeouts and stop-and-go behavior.
 	 */
-	tp->frto = sysctl_tcp_frto && !inet_csk(sk)->icsk_mtup.probe_size;
+	tp->frto = sysctl_tcp_frto &&
+		   (new_recovery || icsk->icsk_retransmits) &&
+		   !inet_csk(sk)->icsk_mtup.probe_size;
 }
 
 /* If ACK arrived pointing to a remembered SACK, it means that our
-- 
2.12.2.715.g7642488e1d-goog

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[David Miller]

From: Yuchung Cheng <ycheng@google.com>
Date: Fri,  7 Apr 2017 11:42:05 -0700

> The recent extension of F-RTO 89fe18e44 ("tcp: extend F-RTO
> to catch more spurious timeouts") interacts badly with certain
> broken middle-boxes.  These broken boxes modify and falsely raise
> the receive window on the ACKs. During a timeout induced recovery,
> F-RTO would send new data packets to probe if the timeout is false
> or not. Since the receive window is falsely raised, the receiver
> would silently drop these F-RTO packets. The recovery would take N
> (exponentially backoff) timeouts to repair N packet losses.  A TCP
> performance killer.
> 
> Due to this unfortunate situation, this patch removes this extension
> to revert F-RTO back to the RFC specification.
> 
> Fixes: 89fe18e44f7e ("tcp: extend F-RTO to catch more spurious timeouts")
> Signed-off-by: Yuchung Cheng <ycheng@google.com>
> Signed-off-by: Neal Cardwell <ncardwell@google.com>
> Signed-off-by: Soheil Hassas Yeganeh <soheil@google.com>
> Signed-off-by: Eric Dumazet <edumazet@google.com>

Applied, thank you.

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Teodor Milkov]

Hello,

I've numerous reports from Windows users that after kernel upgrade from 4.9 to 4.14 they experienced major slow downs and transfer stalls.

After some digging, I found that the slowness starts with this commit:

  tcp: extend F-RTO to catch more spurious timeouts (89fe18e44)
  https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=89fe18e44f7ee5ab1c90d0dff5835acee7751427

Which is partially reverted later with this one:

  tcp: restrict F-RTO to work-around broken middle-boxes (cc663f4d4)
  https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=cc663f4d4c97b7297fb45135ab23cfd508b35a77

But, still, we had stalls until I fully reverted 89fe18e44.


  
---

The recent extension of F-RTO 89fe18e44 ("tcp: extend F-RTO
to catch more spurious timeouts") interacts badly with certain
broken middle-boxes.  These broken boxes modify and falsely raise
the receive window on the ACKs. During a timeout induced recovery,
F-RTO would send new data packets to probe if the timeout is false
or not. Since the receive window is falsely raised, the receiver
would silently drop these F-RTO packets. The recovery would take N
(exponentially backoff) timeouts to repair N packet losses.  A TCP
performance killer.

Due to this unfortunate situation, this patch removes this extension
to revert F-RTO back to the RFC specification.

Fixes: 89fe18e44f7e ("tcp: extend F-RTO to catch more spurious timeouts")
Signed-off-by: Yuchung Cheng <ycheng@google.com>
Signed-off-by: Neal Cardwell <ncardwell@google.com>
Signed-off-by: Soheil Hassas Yeganeh <soheil@google.com>
Signed-off-by: Eric Dumazet <edumazet@google.com>
---
  net/ipv4/tcp_input.c | 20 ++++++++++++--------
  1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 2c1f59386a7b..659d1baefb2b 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -1935,6 +1935,7 @@ void tcp_enter_loss(struct sock *sk)
  	struct tcp_sock *tp = tcp_sk(sk);
  	struct net *net = sock_net(sk);
  	struct sk_buff *skb;
+	bool new_recovery = icsk->icsk_ca_state < TCP_CA_Recovery;
  	bool is_reneg;			/* is receiver reneging on SACKs? */
  	bool mark_lost;
  
@@ -1994,15 +1995,18 @@ void tcp_enter_loss(struct sock *sk)
  	tp->high_seq = tp->snd_nxt;
  	tcp_ecn_queue_cwr(tp);
  
-	/* F-RTO RFC5682 sec 3.1 step 1 mandates to disable F-RTO
-	 * if a previous recovery is underway, otherwise it may incorrectly
-	 * call a timeout spurious if some previously retransmitted packets
-	 * are s/acked (sec 3.2). We do not apply that retriction since
-	 * retransmitted skbs are permanently tagged with TCPCB_EVER_RETRANS
-	 * so FLAG_ORIG_SACK_ACKED is always correct. But we do disable F-RTO
-	 * on PTMU discovery to avoid sending new data.
+	/* F-RTO RFC5682 sec 3.1 step 1: retransmit SND.UNA if no previous
+	 * loss recovery is underway except recurring timeout(s) on
+	 * the same SND.UNA (sec 3.2). Disable F-RTO on path MTU probing
+	 *
+	 * In theory F-RTO can be used repeatedly during loss recovery.
+	 * In practice this interacts badly with broken middle-boxes that
+	 * falsely raise the receive window, which results in repeated
+	 * timeouts and stop-and-go behavior.
  	 */
-	tp->frto = sysctl_tcp_frto && !inet_csk(sk)->icsk_mtup.probe_size;
+	tp->frto = sysctl_tcp_frto &&
+		   (new_recovery || icsk->icsk_retransmits) &&
+		   !inet_csk(sk)->icsk_mtup.probe_size;
  }
  
  /* If ACK arrived pointing to a remembered SACK, it means that our
-- 
2.12.2.715.g7642488e1d-goog

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Neal Cardwell]

On Sun, Feb 18, 2018 at 4:02 PM, Teodor Milkov <tm@del.bg> wrote:
> Hello,
>
> I've numerous reports from Windows users that after kernel upgrade from 4.9
> to 4.14 they experienced major slow downs and transfer stalls.
>
> After some digging, I found that the slowness starts with this commit:
>
>  tcp: extend F-RTO to catch more spurious timeouts (89fe18e44)
>
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=89fe18e44f7ee5ab1c90d0dff5835acee7751427
>
> Which is partially reverted later with this one:
>
>  tcp: restrict F-RTO to work-around broken middle-boxes (cc663f4d4)
>
> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=cc663f4d4c97b7297fb45135ab23cfd508b35a77
>
> But, still, we had stalls until I fully reverted 89fe18e44.

Thanks for the report. Do you have any other details that might help
evaluate this issue? Any packet traces, by any chance? Were the
affected connections web browsing, videos, file transfer, etc? Were
there non-Windows users in this population that did not seem to be
affected by the stalls? Was the bottleneck primarily Ethernet, wifi,
cellular, cable modem, etc? Any middleboxes (firewall, NAT, etc)
between the servers and users? Does "stall" mean that the connection
permanently froze, or temporarily slowed down but eventually
recovered?

Thanks!

neal

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Teodor Milkov]

On 19.02.2018 15:38, Neal Cardwell wrote:
> On Sun, Feb 18, 2018 at 4:02 PM, Teodor Milkov <tm@del.bg> wrote:
>> Hello,
>>
>> I've numerous reports from Windows users that after kernel upgrade from 4.9
>> to 4.14 they experienced major slow downs and transfer stalls.
>>
>> After some digging, I found that the slowness starts with this commit:
>>
>>   tcp: extend F-RTO to catch more spurious timeouts (89fe18e44)
>>
>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=89fe18e44f7ee5ab1c90d0dff5835acee7751427
>>
>> Which is partially reverted later with this one:
>>
>>   tcp: restrict F-RTO to work-around broken middle-boxes (cc663f4d4)
>>
>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=cc663f4d4c97b7297fb45135ab23cfd508b35a77
>>
>> But, still, we had stalls until I fully reverted 89fe18e44.
> Thanks for the report. Do you have any other details that might help
> evaluate this issue?

I'm sorry I didn't provide more info. It was long session.

> Any packet traces, by any chance?

I'll try and obtain one.

> Were the affected connections web browsing, videos, file transfer, etc?

First reports were from pop3 users. When we asked them to try file 
transfer, the problem persisted.

It seems the slow down/stalls aren't severe enough to frustrate web 
browsers.

> Were there non-Windows users in this population that did not seem to be
> affected by the stalls?

All reports were from Windows users. I was able to partially reproduce 
the problem only using Windows as well. Linux & Mac OS X are apparently 
immune.

> Was the bottleneck primarily Ethernet, wifi, cellular, cable modem, etc?

In my test case it is 100 Mbit/s long haul MAN (Ethernet, 1 ms) and 
there's 75 Mbit/s shaper on top of it set up by one of out ISPs. Not 
sure what kind of shaper/policer this is.

With 4.4 and 4.9 kernels as well as patched 4.14 I get very steady ~6 
MB/s. Otherwise it's up to 3 MB/s with frequent slow downs bellow 500 
KB/s and an average speed of about 1 MB/s.

Reporting customers were on all kinds of connectivity from cellular to 
cable, reporting regressions as low as 1 MByte/s (with good kernel) down 
to 50 KB/s. I suspect that the higher the rtt, the lower the speed.

> Any middleboxes (firewall, NAT, etc) between the servers and users?

In my test there's Linux statefull firewall, yes. Not sure about other 
reporters.

> Does "stall" mean that the connection permanently froze, or temporarily slowed down but eventually
> recovered?
In most cases it is severe slow down, which eventually recovers. 
Occasionally there were complete freezes, but these are rather rare.

I've deployed 4.14.20 with 89fe18e44 completely reverted and so far 
feedback from customers is positive.

Thank you very much for your attention to this.

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Neal Cardwell]

On Mon, Feb 19, 2018 at 11:17 AM, Teodor Milkov <tm@del.bg> wrote:
> On 19.02.2018 15:38, Neal Cardwell wrote:
>>
>> On Sun, Feb 18, 2018 at 4:02 PM, Teodor Milkov <tm@del.bg> wrote:
>>>
>>> Hello,
>>>
>>> I've numerous reports from Windows users that after kernel upgrade from
>>> 4.9
>>> to 4.14 they experienced major slow downs and transfer stalls.
>>>
>>> After some digging, I found that the slowness starts with this commit:
>>>
>>>   tcp: extend F-RTO to catch more spurious timeouts (89fe18e44)
>>>
>>>
>>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=89fe18e44f7ee5ab1c90d0dff5835acee7751427
>>>
>>> Which is partially reverted later with this one:
>>>
>>>   tcp: restrict F-RTO to work-around broken middle-boxes (cc663f4d4)
>>>
>>>
>>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=cc663f4d4c97b7297fb45135ab23cfd508b35a77
>>>
>>> But, still, we had stalls until I fully reverted 89fe18e44.
>>
>> Thanks for the report. Do you have any other details that might help
>> evaluate this issue?
>
>
> I'm sorry I didn't provide more info. It was long session.
>
>> Any packet traces, by any chance?
>
>
> I'll try and obtain one.

Great! Yes, if you could obtain a sender-side tcpdump that captured
one of these slow-down/stalls, that would be fantastic. It would be
great to be able to understand what's going on.

We only need headers, so something like the following would be fine:

   tcpdump -c2000000 -w /tmp/test.pcap -s 120 -i $ETH_DEVICE port $PORT

Then if you could post on a web server or Google drive, etc, that'd be great.

Thanks for all the additional details!

neal

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Teodor Milkov]

On 19.02.2018 20:05, Neal Cardwell wrote:
> On Mon, Feb 19, 2018 at 11:17 AM, Teodor Milkov <tm@del.bg> wrote:
>> On 19.02.2018 15:38, Neal Cardwell wrote:
>>> On Sun, Feb 18, 2018 at 4:02 PM, Teodor Milkov <tm@del.bg> wrote:
>>>> Hello,
>>>>
>>>> I've numerous reports from Windows users that after kernel upgrade from
>>>> 4.9
>>>> to 4.14 they experienced major slow downs and transfer stalls.
>>>>
>>>> After some digging, I found that the slowness starts with this commit:
>>>>
>>>>    tcp: extend F-RTO to catch more spurious timeouts (89fe18e44)
>>>>
>>>>
>>>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=89fe18e44f7ee5ab1c90d0dff5835acee7751427
>>>>
>>>> Which is partially reverted later with this one:
>>>>
>>>>    tcp: restrict F-RTO to work-around broken middle-boxes (cc663f4d4)
>>>>
>>>>
>>>> https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=cc663f4d4c97b7297fb45135ab23cfd508b35a77
>>>>
>>>> But, still, we had stalls until I fully reverted 89fe18e44.
>>> Thanks for the report. Do you have any other details that might help
>>> evaluate this issue?
>>
>> I'm sorry I didn't provide more info. It was long session.
>>
>>> Any packet traces, by any chance?
>>
>> I'll try and obtain one.
> Great! Yes, if you could obtain a sender-side tcpdump that captured
> one of these slow-down/stalls, that would be fantastic. It would be
> great to be able to understand what's going on.
>
> We only need headers, so something like the following would be fine:
>
>     tcpdump -c2000000 -w /tmp/test.pcap -s 120 -i $ETH_DEVICE port $PORT
>
> Then if you could post on a web server or Google drive, etc, that'd be great.

Here they are:


  http://vps3.avodz.org/tmp/frto-4.14.11-linux.pcap.xz - 3.3 MB/s

  http://vps3.avodz.org/tmp/frto-4.14.11-windows.pcap.xz - connection 
completely froze and eventually timed out

  http://vps3.avodz.org/tmp/frto-4.14.20+revert-windows.pcap.xz - 5+ 
MB/s, which almost saturated the link

Re: [PATCH net] tcp: restrict F-RTO to work-around broken middle-boxes

[Neal Cardwell]

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

On Wed, Feb 21, 2018 at 7:38 AM, Teodor Milkov <tm@del.bg> wrote:
> Here they are:
>
>
>  http://vps3.avodz.org/tmp/frto-4.14.11-linux.pcap.xz - 3.3 MB/s
>
>  http://vps3.avodz.org/tmp/frto-4.14.11-windows.pcap.xz - connection
> completely froze and eventually timed out
>
>  http://vps3.avodz.org/tmp/frto-4.14.20+revert-windows.pcap.xz - 5+ MB/s,
> which almost saturated the link
>

Thanks for the detailed traces! This is hugely helpful, and nails down
what is happening here.

As the first screen shot shows, an excerpt from your
frto-4.14.11-windows.pcap.xz trace (windows receiver suffers stall),
there is a painful interaction between:

(a) A very broken middlebox in the path of this traffic that is
stripping *all* SACK options, so that receivers advertise SACK
capability but are thereafter unable to communicate to the sender all
the packets they have received.

(b) The F-RTO change you mention above: 89fe18e44 ("tcp: extend F-RTO
to catch more spurious timeouts"), which causes more undo operations,
which are implicitly optimized for the case where more packets will be
SACKed, which does not happen because of (a), so that there are
repeated RTO timeouts.

(c) A Windows receiver that does not implement TCP timestamps. This
means that, per the TCP standard, the sender is supposed to keep
exponentially backing off for each of these RTOs.

The combination of these 3 factors causes very long stalls.

But please note that even with this F-RTO patch fully reverted, the
middlebox that drops SACKs is causing horrendous and unnecessarily
slow recoveries (see the second screen shot, from your
frto-4.14.20+revert-windows.pcap.xz trace). It would be nice to report
this SACK-stripping issue to the middlebox vendor, if possible. Or
maybe there is a config option that can disable this feature.

It seems we will indeed need to revert 89fe18e44. We have a Google TCP
team member out of the office on vacation. When he's back we'll
consult and follow up with our consensus.

Thanks again for the report and the traces! This was hugely helpful.

neal

[-- Attachment #2: windows-zoom0.png --]
[-- Type: image/png, Size: 44194 bytes --]

[-- Attachment #3: windows-full.png --]
[-- Type: image/png, Size: 53564 bytes --]