[PATCH net-next 0/2] tcp: fix high tail latencies in DCTCP

[PATCH net-next 0/2] tcp: fix high tail latencies in DCTCP

[Lawrence Brakmo]

When have observed high tail latencies when using DCTCP for RPCs as
compared to using Cubic. For example, in one setup there are 2 hosts
sending to a 3rd one, with each sender having 3 flows (1 stream,
1 1MB back-to-back RPCs and 1 10KB back-to-back RPCs). The following
table shows the 99% and 99.9% latencies for both Cubic and dctcp:

           Cubic 99%  Cubic 99.9%   dctcp 99%    dctcp 99.9%
  1MB RPCs    2.6ms       5.5ms         43ms          208ms
 10KB RPCs    1.1ms       1.3ms         53ms          212ms

Looking at tcpdump traces showed that there are two causes for the
latency.  

  1) RTOs caused by the receiver sending a dup ACK and not ACKing
     the last (and only) packet sent.
  2) Delaying ACKs when the sender has a cwnd of 1, so everything
     pauses for the duration of the delayed ACK.

The first patch fixes the cause of the dup ACKs, not updating DCTCP
state when an ACK that was initially delayed has been sent with a
data packet.

The second patch insures that an ACK is sent immediately when a
CWR marked packet arrives.

With the patches the latencies for DCTCP now look like:

           dctcp 99%  dctcp 99.9% 
  1MB RPCs    4.8ms       6.5ms
 10KB RPCs    143us       184us

Note that while the 1MB RPCs tail latencies are higher than Cubic's,
the 10KB latencies are much smaller than Cubic's. These patches fix
issues on the receiver, but tcpdump traces indicate there is an
opportunity to also fix an issue at the sender that adds about 3ms
to the tail latencies.

The following trace shows the issue that tiggers an RTO (fixed by these patches):

   Host A sends the last packets of the request
   Host B receives them, and the last packet is marked with congestion (CE)
   Host B sends ACKs for packets not marked with congestion
   Host B sends data packet with reply and ACK for packet marked with
          congestion (TCP flag ECE)
   Host A receives ACKs with no ECE flag
   Host A receives data packet with ACK for the last packet of request
          and which has TCP ECE bit set
   Host A sends 1st data packet of the next request with TCP flag CWR
   Host B receives the packet (as seen in tcpdump at B), no CE flag
   Host B sends a dup ACK that also has the TCP ECE flag
   Host A RTO timer fires!
   Host A to send the next packet
   Host A receives an ACK for everything it has sent (i.e. Host B
          did receive 1st packet of request)
   Host A send more packets…

[PATCH net-next 1/2] tcp: notify when a delayed ack is sent
[PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

 net/ipv4/tcp_input.c  | 25 +++++++++++++++++--------
 net/ipv4/tcp_output.c |  2 ++
 2 files changed, 19 insertions(+), 8 deletions(-)

[PATCH net-next 1/2] tcp: notify when a delayed ack is sent

[Lawrence Brakmo]

DCTCP depends on the CA_EVENT_NON_DELAYED_ACK and CA_EVENT_DELAYED_ACK
notifications to keep track if it needs to send an ACK for packets that
were received with a particular ECN state but whose ACK was delayed.

Under some circumstances, for example when a delayed ACK is sent with a
data packet, DCTCP state was not being updated due to a lack of
notification that the previously delayed ACK was sent. As a result, it
would sometimes send a duplicate ACK when a new data packet arrived.

This patch insures that DCTCP's state is correctly updated so it will
not send the duplicate ACK.

Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
---
 net/ipv4/tcp_output.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
index f8f6129160dd..41f6ad7a21e4 100644
--- a/net/ipv4/tcp_output.c
+++ b/net/ipv4/tcp_output.c
@@ -172,6 +172,8 @@ static inline void tcp_event_ack_sent(struct sock *sk, unsigned int pkts)
 			__sock_put(sk);
 	}
 	tcp_dec_quickack_mode(sk, pkts);
+	if (inet_csk_ack_scheduled(sk))
+		tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
 	inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
 }
 
-- 
2.17.1

[PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

[Lawrence Brakmo]

We observed high 99 and 99.9% latencies when doing RPCs with DCTCP. The
problem is triggered when the last packet of a request arrives CE
marked. The reply will carry the ECE mark causing TCP to shrink its cwnd
to 1 (because there are no packets in flight). When the 1st packet of
the next request arrives it was sometimes delayed adding up to 40ms to
the latency.

This patch insures that CWR makred data packets arriving will be acked
immediately.

Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
---
 net/ipv4/tcp_input.c | 25 +++++++++++++++++--------
 1 file changed, 17 insertions(+), 8 deletions(-)

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 76ca88f63b70..b024d36f0d56 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -98,6 +98,8 @@ int sysctl_tcp_max_orphans __read_mostly = NR_FILE;
 #define FLAG_UPDATE_TS_RECENT	0x4000 /* tcp_replace_ts_recent() */
 #define FLAG_NO_CHALLENGE_ACK	0x8000 /* do not call tcp_send_challenge_ack()	*/
 #define FLAG_ACK_MAYBE_DELAYED	0x10000 /* Likely a delayed ACK */
+#define FLAG_OFO_POSSIBLE	0x20000 /* Possible OFO */
+#define FLAG_CWR		0x40000 /* CWR in this ACK */
 
 #define FLAG_ACKED		(FLAG_DATA_ACKED|FLAG_SYN_ACKED)
 #define FLAG_NOT_DUP		(FLAG_DATA|FLAG_WIN_UPDATE|FLAG_ACKED)
@@ -5087,7 +5089,7 @@ static inline void tcp_data_snd_check(struct sock *sk)
 /*
  * Check if sending an ack is needed.
  */
-static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible)
+static void __tcp_ack_snd_check(struct sock *sk, int flags)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 	unsigned long rtt, delay;
@@ -5102,13 +5104,16 @@ static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible)
 	    (tp->rcv_nxt - tp->copied_seq < sk->sk_rcvlowat ||
 	     __tcp_select_window(sk) >= tp->rcv_wnd)) ||
 	    /* We ACK each frame or... */
-	    tcp_in_quickack_mode(sk)) {
+	    tcp_in_quickack_mode(sk) ||
+	    /* We received CWR */
+	    flags & FLAG_CWR) {
 send_now:
 		tcp_send_ack(sk);
 		return;
 	}
 
-	if (!ofo_possible || RB_EMPTY_ROOT(&tp->out_of_order_queue)) {
+	if (!(flags & FLAG_OFO_POSSIBLE) ||
+	    RB_EMPTY_ROOT(&tp->out_of_order_queue)) {
 		tcp_send_delayed_ack(sk);
 		return;
 	}
@@ -5134,13 +5139,13 @@ static void __tcp_ack_snd_check(struct sock *sk, int ofo_possible)
 		      HRTIMER_MODE_REL_PINNED_SOFT);
 }
 
-static inline void tcp_ack_snd_check(struct sock *sk)
+static inline void tcp_ack_snd_check(struct sock *sk, int flags)
 {
 	if (!inet_csk_ack_scheduled(sk)) {
 		/* We sent a data segment already. */
 		return;
 	}
-	__tcp_ack_snd_check(sk, 1);
+	__tcp_ack_snd_check(sk, flags | FLAG_OFO_POSSIBLE);
 }
 
 /*
@@ -5489,6 +5494,7 @@ void tcp_rcv_established(struct sock *sk, struct sk_buff *skb)
 				goto discard;
 			}
 		} else {
+			int flags;
 			int eaten = 0;
 			bool fragstolen = false;
 
@@ -5525,7 +5531,9 @@ void tcp_rcv_established(struct sock *sk, struct sk_buff *skb)
 					goto no_ack;
 			}
 
-			__tcp_ack_snd_check(sk, 0);
+			flags = (tcp_flag_word(th) & TCP_FLAG_CWR) ?
+				FLAG_CWR : 0;
+			__tcp_ack_snd_check(sk, flags);
 no_ack:
 			if (eaten)
 				kfree_skb_partial(skb, fragstolen);
@@ -5561,7 +5569,8 @@ void tcp_rcv_established(struct sock *sk, struct sk_buff *skb)
 	tcp_data_queue(sk, skb);
 
 	tcp_data_snd_check(sk);
-	tcp_ack_snd_check(sk);
+	tcp_ack_snd_check(sk, (tcp_flag_word(th) & TCP_FLAG_CWR) ?
+			  FLAG_CWR : 0);
 	return;
 
 csum_error:
@@ -6150,7 +6159,7 @@ int tcp_rcv_state_process(struct sock *sk, struct sk_buff *skb)
 	/* tcp_data could move socket to TIME-WAIT */
 	if (sk->sk_state != TCP_CLOSE) {
 		tcp_data_snd_check(sk);
-		tcp_ack_snd_check(sk);
+		tcp_ack_snd_check(sk, 0);
 	}
 
 	if (!queued) {
-- 
2.17.1

Re: [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

[Neal Cardwell]

On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
>
> We observed high 99 and 99.9% latencies when doing RPCs with DCTCP. The
> problem is triggered when the last packet of a request arrives CE
> marked. The reply will carry the ECE mark causing TCP to shrink its cwnd
> to 1 (because there are no packets in flight). When the 1st packet of
> the next request arrives it was sometimes delayed adding up to 40ms to
> the latency.
>
> This patch insures that CWR makred data packets arriving will be acked
> immediately.
>
> Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
> ---

Thanks, Larry. Ensuring that CWR-marked data packets arriving will be
acked immediately sounds like a good goal to me.

I am wondering if we can have a simpler fix.

The dctcp_ce_state_0_to_1() code is setting the TCP_ECN_DEMAND_CWR
bit in ecn_flags, which disables the code in __tcp_ecn_check_ce() that
would have otherwise used the tcp_enter_quickack_mode() mechanism to
force an ACK:

__tcp_ecn_check_ce():
...
case INET_ECN_CE:
  if (tcp_ca_needs_ecn(sk))
    tcp_ca_event(sk, CA_EVENT_ECN_IS_CE);
       // -> dctcp_ce_state_0_to_1()
       //     ->  tp->ecn_flags |= TCP_ECN_DEMAND_CWR;

  if (!(tp->ecn_flags & TCP_ECN_DEMAND_CWR)) {
    /* Better not delay acks, sender can have a very low cwnd */
    tcp_enter_quickack_mode(sk, 1);
    tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
  }
  tp->ecn_flags |= TCP_ECN_SEEN;
  break;

So it seems like the bug here may be that dctcp_ce_state_0_to_1()  is
setting the TCP_ECN_DEMAND_CWR  bit in ecn_flags, when really it
should let its caller, __tcp_ecn_check_ce() set TCP_ECN_DEMAND_CWR, in
which case the code would already properly force an immediate ACK.

So, what if we use this fix instead (not compiled, not tested):

diff --git a/net/ipv4/tcp_dctcp.c b/net/ipv4/tcp_dctcp.c
index 5f5e5936760e..4fecd2824edb 100644
--- a/net/ipv4/tcp_dctcp.c
+++ b/net/ipv4/tcp_dctcp.c
@@ -152,8 +152,6 @@ static void dctcp_ce_state_0_to_1(struct sock *sk)

        ca->prior_rcv_nxt = tp->rcv_nxt;
        ca->ce_state = 1;
-
-       tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
 }

 static void dctcp_ce_state_1_to_0(struct sock *sk)

What do you think?

neal

Re: [PATCH net-next 0/2] tcp: fix high tail latencies in DCTCP

[Neal Cardwell]

On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
>
> When have observed high tail latencies when using DCTCP for RPCs as
> compared to using Cubic. For example, in one setup there are 2 hosts
> sending to a 3rd one, with each sender having 3 flows (1 stream,
> 1 1MB back-to-back RPCs and 1 10KB back-to-back RPCs). The following
> table shows the 99% and 99.9% latencies for both Cubic and dctcp:
>
>            Cubic 99%  Cubic 99.9%   dctcp 99%    dctcp 99.9%
>   1MB RPCs    2.6ms       5.5ms         43ms          208ms
>  10KB RPCs    1.1ms       1.3ms         53ms          212ms
>
> Looking at tcpdump traces showed that there are two causes for the
> latency.
>
>   1) RTOs caused by the receiver sending a dup ACK and not ACKing
>      the last (and only) packet sent.
>   2) Delaying ACKs when the sender has a cwnd of 1, so everything
>      pauses for the duration of the delayed ACK.
>
> The first patch fixes the cause of the dup ACKs, not updating DCTCP
> state when an ACK that was initially delayed has been sent with a
> data packet.
>
> The second patch insures that an ACK is sent immediately when a
> CWR marked packet arrives.
>
> With the patches the latencies for DCTCP now look like:
>
>            dctcp 99%  dctcp 99.9%
>   1MB RPCs    4.8ms       6.5ms
>  10KB RPCs    143us       184us
>
> Note that while the 1MB RPCs tail latencies are higher than Cubic's,
> the 10KB latencies are much smaller than Cubic's. These patches fix
> issues on the receiver, but tcpdump traces indicate there is an
> opportunity to also fix an issue at the sender that adds about 3ms
> to the tail latencies.
>
> The following trace shows the issue that tiggers an RTO (fixed by these patches):
>
>    Host A sends the last packets of the request
>    Host B receives them, and the last packet is marked with congestion (CE)
>    Host B sends ACKs for packets not marked with congestion
>    Host B sends data packet with reply and ACK for packet marked with
>           congestion (TCP flag ECE)
>    Host A receives ACKs with no ECE flag
>    Host A receives data packet with ACK for the last packet of request
>           and which has TCP ECE bit set
>    Host A sends 1st data packet of the next request with TCP flag CWR
>    Host B receives the packet (as seen in tcpdump at B), no CE flag
>    Host B sends a dup ACK that also has the TCP ECE flag
>    Host A RTO timer fires!
>    Host A to send the next packet
>    Host A receives an ACK for everything it has sent (i.e. Host B
>           did receive 1st packet of request)
>    Host A send more packets…
>
> [PATCH net-next 1/2] tcp: notify when a delayed ack is sent
> [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

Thanks, Larry!

I suspect there is a broader problem with "DCTCP-style precise ECE
ACKs" that this patch series does not address.

AFAICT the DCTCP "historical" ACKs for ECE precision, generated in
dctcp_ce_state_0_to_1() and dctcp_ce_state_1_to_0(), violate the
assumptions of the pre-existing delayed ACK state machine. They
violate those assumptions by rewinding tp->rcv_nxt backwards and then
calling tcp_send_ack(sk). But the existing code path to send an ACK
assumes that any ACK transmission always sends an ACK that accounts
for all received data, so that after sending an ACK we can cancel the
delayed ACK timer. So it seems with DCTCP we can have buggy sequences
where the DCTCP historical ACK causes us to forget that we need to
schedule a delayed ACK (which will force the sender to RTO, as shown
in the trace):

tcp_event_data_recv()
 inet_csk_schedule_ack()  // remember that we need an ACK
 tcp_ecn_check_ce()
  tcp_ca_event() // with CA_EVENT_ECN_IS_CE or CA_EVENT_ECN_NO_CE
    dctcp_cwnd_event()
      dctcp_ce_state_0_to_1() or dctcp_ce_state_1_to_0()
       if (... && ca->delayed_ack_reserved)
          tp->rcv_nxt = ca->prior_rcv_nxt;
          tcp_send_ack(sk);     // send an ACK, but for old data!
            tcp_transmit_skb()
              tcp_event_ack_sent()
                inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
                    // forget that we need a delayed ACK!

AFAICT the first patch in this series, to force an immediate ACK on
any packet with a CWR, papers over this issue of the forgotten delayed
ACK by forcing an immediate ack in __tcp_ack_snd_check(). This ensures
that at least for CWR packets the forgotten delayed ACK does not
matter. But for packets without CWR I believe the buggy "forgotten
delayed ACK" sequence above is still possible, and could still plague
DCTCP with high tail latencies in some cases. I suspect that after
your CWR-forces-ACK patch it may not be jumping out in performance
test results because (a) if there is no CWR involved then usually the
cwnd is high enough that missing delayed ACK does not cause a stall,
and (b) if there is a CWR involved then your patch forces an immediate
ACK. But AFAICT that forgotten delayed ACK bug is still there.

What do folks think?

neal

Re: [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

[Lawrence Brakmo]

On 6/30/18, 11:23 AM, "Neal Cardwell" <ncardwell@google.com> wrote:

    On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
    >
    > We observed high 99 and 99.9% latencies when doing RPCs with DCTCP. The
    > problem is triggered when the last packet of a request arrives CE
    > marked. The reply will carry the ECE mark causing TCP to shrink its cwnd
    > to 1 (because there are no packets in flight). When the 1st packet of
    > the next request arrives it was sometimes delayed adding up to 40ms to
    > the latency.
    >
    > This patch insures that CWR makred data packets arriving will be acked
    > immediately.
    >
    > Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
    > ---
    
    Thanks, Larry. Ensuring that CWR-marked data packets arriving will be
    acked immediately sounds like a good goal to me.
    
    I am wondering if we can have a simpler fix.
    
    The dctcp_ce_state_0_to_1() code is setting the TCP_ECN_DEMAND_CWR
    bit in ecn_flags, which disables the code in __tcp_ecn_check_ce() that
    would have otherwise used the tcp_enter_quickack_mode() mechanism to
    force an ACK:
    
    __tcp_ecn_check_ce():
    ...
    case INET_ECN_CE:
      if (tcp_ca_needs_ecn(sk))
        tcp_ca_event(sk, CA_EVENT_ECN_IS_CE);
           // -> dctcp_ce_state_0_to_1()
           //     ->  tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
    
      if (!(tp->ecn_flags & TCP_ECN_DEMAND_CWR)) {
        /* Better not delay acks, sender can have a very low cwnd */
        tcp_enter_quickack_mode(sk, 1);
        tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
      }
      tp->ecn_flags |= TCP_ECN_SEEN;
      break;
    
    So it seems like the bug here may be that dctcp_ce_state_0_to_1()  is
    setting the TCP_ECN_DEMAND_CWR  bit in ecn_flags, when really it
    should let its caller, __tcp_ecn_check_ce() set TCP_ECN_DEMAND_CWR, in
    which case the code would already properly force an immediate ACK.
    
    So, what if we use this fix instead (not compiled, not tested):
    
    diff --git a/net/ipv4/tcp_dctcp.c b/net/ipv4/tcp_dctcp.c
    index 5f5e5936760e..4fecd2824edb 100644
    --- a/net/ipv4/tcp_dctcp.c
    +++ b/net/ipv4/tcp_dctcp.c
    @@ -152,8 +152,6 @@ static void dctcp_ce_state_0_to_1(struct sock *sk)
    
            ca->prior_rcv_nxt = tp->rcv_nxt;
            ca->ce_state = 1;
    -
    -       tp->ecn_flags |= TCP_ECN_DEMAND_CWR;
     }
    
     static void dctcp_ce_state_1_to_0(struct sock *sk)
    
    What do you think?
    
    neal

I see two issues, one is that entering quickack mode as you mentioned does not insure that it will still be on when the CWR arrives. The second issue is that the problem occurs right after the receiver sends a small reply which results in entering pingpong mode right before the sender starts the new request by sending just one packet (i.e. forces delayed ack).

I compiled and tested your patch. Both 99 and 99.9 percentile latencies are around 40ms. Looking at the packet traces shows that some CWR marked packets are not being ack immediately (delayed by 40ms).

Larry

    

Re: [PATCH net-next 0/2] tcp: fix high tail latencies in DCTCP

[Lawrence Brakmo]

On 6/30/18, 5:26 PM, "netdev-owner@vger.kernel.org on behalf of Neal Cardwell" <netdev-owner@vger.kernel.org on behalf of ncardwell@google.com> wrote:

    On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
    >
    > When have observed high tail latencies when using DCTCP for RPCs as
    > compared to using Cubic. For example, in one setup there are 2 hosts
    > sending to a 3rd one, with each sender having 3 flows (1 stream,
    > 1 1MB back-to-back RPCs and 1 10KB back-to-back RPCs). The following
    > table shows the 99% and 99.9% latencies for both Cubic and dctcp:
    >
    >            Cubic 99%  Cubic 99.9%   dctcp 99%    dctcp 99.9%
    >   1MB RPCs    2.6ms       5.5ms         43ms          208ms
    >  10KB RPCs    1.1ms       1.3ms         53ms          212ms
    >
    > Looking at tcpdump traces showed that there are two causes for the
    > latency.
    >
    >   1) RTOs caused by the receiver sending a dup ACK and not ACKing
    >      the last (and only) packet sent.
    >   2) Delaying ACKs when the sender has a cwnd of 1, so everything
    >      pauses for the duration of the delayed ACK.
    >
    > The first patch fixes the cause of the dup ACKs, not updating DCTCP
    > state when an ACK that was initially delayed has been sent with a
    > data packet.
    >
    > The second patch insures that an ACK is sent immediately when a
    > CWR marked packet arrives.
    >
    > With the patches the latencies for DCTCP now look like:
    >
    >            dctcp 99%  dctcp 99.9%
    >   1MB RPCs    4.8ms       6.5ms
    >  10KB RPCs    143us       184us
    >
    > Note that while the 1MB RPCs tail latencies are higher than Cubic's,
    > the 10KB latencies are much smaller than Cubic's. These patches fix
    > issues on the receiver, but tcpdump traces indicate there is an
    > opportunity to also fix an issue at the sender that adds about 3ms
    > to the tail latencies.
    >
    > The following trace shows the issue that tiggers an RTO (fixed by these patches):
    >
    >    Host A sends the last packets of the request
    >    Host B receives them, and the last packet is marked with congestion (CE)
    >    Host B sends ACKs for packets not marked with congestion
    >    Host B sends data packet with reply and ACK for packet marked with
    >           congestion (TCP flag ECE)
    >    Host A receives ACKs with no ECE flag
    >    Host A receives data packet with ACK for the last packet of request
    >           and which has TCP ECE bit set
    >    Host A sends 1st data packet of the next request with TCP flag CWR
    >    Host B receives the packet (as seen in tcpdump at B), no CE flag
    >    Host B sends a dup ACK that also has the TCP ECE flag
    >    Host A RTO timer fires!
    >    Host A to send the next packet
    >    Host A receives an ACK for everything it has sent (i.e. Host B
    >           did receive 1st packet of request)
    >    Host A send more packets…
    >
    > [PATCH net-next 1/2] tcp: notify when a delayed ack is sent
    > [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives
    
    Thanks, Larry!
    
    I suspect there is a broader problem with "DCTCP-style precise ECE
    ACKs" that this patch series does not address.
    
    AFAICT the DCTCP "historical" ACKs for ECE precision, generated in
    dctcp_ce_state_0_to_1() and dctcp_ce_state_1_to_0(), violate the
    assumptions of the pre-existing delayed ACK state machine. They
    violate those assumptions by rewinding tp->rcv_nxt backwards and then
    calling tcp_send_ack(sk). But the existing code path to send an ACK
    assumes that any ACK transmission always sends an ACK that accounts
    for all received data, so that after sending an ACK we can cancel the
    delayed ACK timer. So it seems with DCTCP we can have buggy sequences
    where the DCTCP historical ACK causes us to forget that we need to
    schedule a delayed ACK (which will force the sender to RTO, as shown
    in the trace):
    
    tcp_event_data_recv()
     inet_csk_schedule_ack()  // remember that we need an ACK
     tcp_ecn_check_ce()
      tcp_ca_event() // with CA_EVENT_ECN_IS_CE or CA_EVENT_ECN_NO_CE
        dctcp_cwnd_event()
          dctcp_ce_state_0_to_1() or dctcp_ce_state_1_to_0()
           if (... && ca->delayed_ack_reserved)
              tp->rcv_nxt = ca->prior_rcv_nxt;
              tcp_send_ack(sk);     // send an ACK, but for old data!
                tcp_transmit_skb()
                  tcp_event_ack_sent()
                    inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
                        // forget that we need a delayed ACK!
    
    AFAICT the first patch in this series, to force an immediate ACK on
    any packet with a CWR, papers over this issue of the forgotten delayed
    ACK by forcing an immediate ack in __tcp_ack_snd_check(). This ensures
    that at least for CWR packets the forgotten delayed ACK does not
    matter. But for packets without CWR I believe the buggy "forgotten
    delayed ACK" sequence above is still possible, and could still plague
    DCTCP with high tail latencies in some cases. I suspect that after
    your CWR-forces-ACK patch it may not be jumping out in performance
    test results because (a) if there is no CWR involved then usually the
    cwnd is high enough that missing delayed ACK does not cause a stall,
    and (b) if there is a CWR involved then your patch forces an immediate
    ACK. But AFAICT that forgotten delayed ACK bug is still there.
    
    What do folks think?
    
    neal

    
Neal, just to clarify, the 2nd patch is the one that ACKs immediately after receiving a CWR marked packet. The 1st patch eliminates the problem that was causing RTOs due to DCTCP being in the wrong state (thinking there was a delayed ACK pending when there was not). With just the 1st patch I do not see any RTOs, only delays due to delayed ACKs (which are fixed with the 2nd patch).

You are correct in that the dctcp code to send old ACKs can result in missing sending an ACK. However, it is for the new packet not for the previously delayed ACK since that is the ACK that is sent when the dctcp code (dctcp_ce_state_..()) calls tcp_send_ack().

When a new data packet arrives, tcp_event_data_recv() is called. This calls inet_csk_schedule_ack(sk) which sets icsk_ack.pending to remember that an ack needs to be sent. If dctcp_ce_state_..() ends up calling tcp_send_ack(), it will ultimately clear icsk_ack.pending (it is done in inet_csk_clear_xmit_timer()). As a result, tcp_ack_snd_check(), which is called after dctcp_ce_state_..() is called, will just return after checking that icsk_ack.pending is zero. That is, not ACK will be sent.

If the cwnd is greater than 1, then missing one ACK will not have a major impact because the next packet will trigger sending an ACK (although it may be delayed). This is why my original patch of making sure the cwnd is at least 2 solved the problem (but did not fix the main causes).

This patch set fixes two issues in the current code that were causing the high percentile latencies when using DCTCP and RPCs.

The bug you pointed out does exists, but is orthogonal to the issues fixed by my current patch set. I will leave this patch set as is and do another patch for the bug you pointed out.

Thanks Neal!

Larry

Re: [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

[Neal Cardwell]

On Sat, Jun 30, 2018 at 9:47 PM Lawrence Brakmo <brakmo@fb.com> wrote:
> I see two issues, one is that entering quickack mode as you
> mentioned does not insure that it will still be on when the CWR
> arrives. The second issue is that the problem occurs right after the
> receiver sends a small reply which results in entering pingpong mode
> right before the sender starts the new request by sending just one
> packet (i.e. forces delayed ack).
>
> I compiled and tested your patch. Both 99 and 99.9 percentile
> latencies are around 40ms. Looking at the packet traces shows that
> some CWR marked packets are not being ack immediately (delayed by
> 40ms).

Thanks, Larry! So your tests provide nice, specific evidence that it
is good to force an immediate ACK when a receiver receives a packet
with CWR marked. Given that, I am wondering what the simplest way is
to achieve that goal.

What if, rather than plumbing a new specific signal into
__tcp_ack_snd_check(), we use the existing general quick-ack
mechanism, where various parts of the TCP stack (like
__tcp_ecn_check_ce())  are already using the quick-ack mechanism to
"remotely" signal to __tcp_ack_snd_check() that they want an immediate
ACK.

For example, would it work to do something like:

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index c53ae5fc834a5..8168d1938b376 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -262,6 +262,12 @@ static void __tcp_ecn_check_ce(struct sock *sk,
const struct sk_buff *skb)
 {
        struct tcp_sock *tp = tcp_sk(sk);

+       /* If the sender is telling us it has entered CWR, then its cwnd may be
+        * very low (even just 1 packet), so we should ACK immediately.
+        */
+       if (tcp_hdr(skb)->cwr)
+               tcp_enter_quickack_mode(sk, 2);
+
        switch (TCP_SKB_CB(skb)->ip_dsfield & INET_ECN_MASK) {
        case INET_ECN_NOT_ECT:
                /* Insure that GCN will not continue to mark packets. */

And then since that broadens the mission of this function beyond
checking just the ECT/CE bits, I supposed we could rename the
__tcp_ecn_check_ce() and tcp_ecn_check_ce() functions to
__tcp_ecn_check() and tcp_ecn_check(), or something like that.

Would that work for this particular issue?

neal

Re: [PATCH net-next 1/2] tcp: notify when a delayed ack is sent

[Neal Cardwell]

On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
>
> DCTCP depends on the CA_EVENT_NON_DELAYED_ACK and CA_EVENT_DELAYED_ACK
> notifications to keep track if it needs to send an ACK for packets that
> were received with a particular ECN state but whose ACK was delayed.
>
> Under some circumstances, for example when a delayed ACK is sent with a
> data packet, DCTCP state was not being updated due to a lack of
> notification that the previously delayed ACK was sent. As a result, it
> would sometimes send a duplicate ACK when a new data packet arrived.
>
> This patch insures that DCTCP's state is correctly updated so it will
> not send the duplicate ACK.
>
> Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
> ---
>  net/ipv4/tcp_output.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
> index f8f6129160dd..41f6ad7a21e4 100644
> --- a/net/ipv4/tcp_output.c
> +++ b/net/ipv4/tcp_output.c
> @@ -172,6 +172,8 @@ static inline void tcp_event_ack_sent(struct sock *sk, unsigned int pkts)
>                         __sock_put(sk);
>         }
>         tcp_dec_quickack_mode(sk, pkts);
> +       if (inet_csk_ack_scheduled(sk))
> +               tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
>         inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
>  }

Thanks for this fix! Seems like this would work, but if I am reading
this correctly then it seems like this would cause a duplicate call to
tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK) when we are sending a pure
ACK (delayed or non-delayed):

(1) once from tcp_send_ack() before we send the ACK:

tcp_send_ack(struct sock *sk)
 ->        tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);

(2) then again from tcp_event_ack_sent() after we have sent the ACK:

tcp_event_ack_sent()
    ->   if (inet_csk_ack_scheduled(sk))
                 tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);

What if we remove the original CA_EVENT_NON_DELAYED_ACK call and just
replace it with your new one? (not compiled, not tested):

diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
index 3889dcd4868d4..bddb49617d9be 100644
--- a/net/ipv4/tcp_output.c
+++ b/net/ipv4/tcp_output.c
@@ -184,6 +184,8 @@ static inline void tcp_event_ack_sent(struct sock
*sk, unsigned int pkts)
                        __sock_put(sk);
        }
        tcp_dec_quickack_mode(sk, pkts);
+       if (inet_csk_ack_scheduled(sk))
+               tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
        inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
 }

@@ -3836,8 +3838,6 @@ void tcp_send_ack(struct sock *sk)
        if (sk->sk_state == TCP_CLOSE)
                return;

-       tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
-
        /* We are not putting this on the write queue, so
         * tcp_transmit_skb() will set the ownership to this
         * sock.

Aside from lower CPU overhead, one nice benefit of that is that we
then only call tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK) in one
place, which might be a little easier to reason about.

Does that work?

neal

Re: [PATCH net-next 1/2] tcp: notify when a delayed ack is sent

[Lawrence Brakmo]

On 7/2/18, 8:18 AM, "netdev-owner@vger.kernel.org on behalf of Neal Cardwell" <netdev-owner@vger.kernel.org on behalf of ncardwell@google.com> wrote:

    On Fri, Jun 29, 2018 at 9:48 PM Lawrence Brakmo <brakmo@fb.com> wrote:
    >
    > DCTCP depends on the CA_EVENT_NON_DELAYED_ACK and CA_EVENT_DELAYED_ACK
    > notifications to keep track if it needs to send an ACK for packets that
    > were received with a particular ECN state but whose ACK was delayed.
    >
    > Under some circumstances, for example when a delayed ACK is sent with a
    > data packet, DCTCP state was not being updated due to a lack of
    > notification that the previously delayed ACK was sent. As a result, it
    > would sometimes send a duplicate ACK when a new data packet arrived.
    >
    > This patch insures that DCTCP's state is correctly updated so it will
    > not send the duplicate ACK.
    >
    > Signed-off-by: Lawrence Brakmo <brakmo@fb.com>
    > ---
    >  net/ipv4/tcp_output.c | 2 ++
    >  1 file changed, 2 insertions(+)
    >
    > diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
    > index f8f6129160dd..41f6ad7a21e4 100644
    > --- a/net/ipv4/tcp_output.c
    > +++ b/net/ipv4/tcp_output.c
    > @@ -172,6 +172,8 @@ static inline void tcp_event_ack_sent(struct sock *sk, unsigned int pkts)
    >                         __sock_put(sk);
    >         }
    >         tcp_dec_quickack_mode(sk, pkts);
    > +       if (inet_csk_ack_scheduled(sk))
    > +               tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
    >         inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
    >  }
    
    Thanks for this fix! Seems like this would work, but if I am reading
    this correctly then it seems like this would cause a duplicate call to
    tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK) when we are sending a pure
    ACK (delayed or non-delayed):
    
    (1) once from tcp_send_ack() before we send the ACK:
    
    tcp_send_ack(struct sock *sk)
     ->        tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
    
    (2) then again from tcp_event_ack_sent() after we have sent the ACK:
    
    tcp_event_ack_sent()
        ->   if (inet_csk_ack_scheduled(sk))
                     tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
    
    What if we remove the original CA_EVENT_NON_DELAYED_ACK call and just
    replace it with your new one? (not compiled, not tested):
    
    diff --git a/net/ipv4/tcp_output.c b/net/ipv4/tcp_output.c
    index 3889dcd4868d4..bddb49617d9be 100644
    --- a/net/ipv4/tcp_output.c
    +++ b/net/ipv4/tcp_output.c
    @@ -184,6 +184,8 @@ static inline void tcp_event_ack_sent(struct sock
    *sk, unsigned int pkts)
                            __sock_put(sk);
            }
            tcp_dec_quickack_mode(sk, pkts);
    +       if (inet_csk_ack_scheduled(sk))
    +               tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
            inet_csk_clear_xmit_timer(sk, ICSK_TIME_DACK);
     }
    
    @@ -3836,8 +3838,6 @@ void tcp_send_ack(struct sock *sk)
            if (sk->sk_state == TCP_CLOSE)
                    return;
    
    -       tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK);
    -
            /* We are not putting this on the write queue, so
             * tcp_transmit_skb() will set the ownership to this
             * sock.
    
    Aside from lower CPU overhead, one nice benefit of that is that we
    then only call tcp_ca_event(sk, CA_EVENT_NON_DELAYED_ACK) in one
    place, which might be a little easier to reason about.
    
    Does that work?
    
    neal

Thanks Neal, good catch!  I will resubmit the patch.
    

Re: [PATCH net-next 2/2] tcp: ack immediately when a cwr packet arrives

[Lawrence Brakmo]

On 7/2/18, 7:57 AM, "Neal Cardwell" <ncardwell@google.com> wrote:

    On Sat, Jun 30, 2018 at 9:47 PM Lawrence Brakmo <brakmo@fb.com> wrote:
    > I see two issues, one is that entering quickack mode as you
    > mentioned does not insure that it will still be on when the CWR
    > arrives. The second issue is that the problem occurs right after the
    > receiver sends a small reply which results in entering pingpong mode
    > right before the sender starts the new request by sending just one
    > packet (i.e. forces delayed ack).
    >
    > I compiled and tested your patch. Both 99 and 99.9 percentile
    > latencies are around 40ms. Looking at the packet traces shows that
    > some CWR marked packets are not being ack immediately (delayed by
    > 40ms).
    
    Thanks, Larry! So your tests provide nice, specific evidence that it
    is good to force an immediate ACK when a receiver receives a packet
    with CWR marked. Given that, I am wondering what the simplest way is
    to achieve that goal.
    
    What if, rather than plumbing a new specific signal into
    __tcp_ack_snd_check(), we use the existing general quick-ack
    mechanism, where various parts of the TCP stack (like
    __tcp_ecn_check_ce())  are already using the quick-ack mechanism to
    "remotely" signal to __tcp_ack_snd_check() that they want an immediate
    ACK.
    
    For example, would it work to do something like:
    
    diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
    index c53ae5fc834a5..8168d1938b376 100644
    --- a/net/ipv4/tcp_input.c
    +++ b/net/ipv4/tcp_input.c
    @@ -262,6 +262,12 @@ static void __tcp_ecn_check_ce(struct sock *sk,
    const struct sk_buff *skb)
     {
            struct tcp_sock *tp = tcp_sk(sk);
    
    +       /* If the sender is telling us it has entered CWR, then its cwnd may be
    +        * very low (even just 1 packet), so we should ACK immediately.
    +        */
    +       if (tcp_hdr(skb)->cwr)
    +               tcp_enter_quickack_mode(sk, 2);
    +
            switch (TCP_SKB_CB(skb)->ip_dsfield & INET_ECN_MASK) {
            case INET_ECN_NOT_ECT:
                    /* Insure that GCN will not continue to mark packets. */
    
    And then since that broadens the mission of this function beyond
    checking just the ECT/CE bits, I supposed we could rename the
    __tcp_ecn_check_ce() and tcp_ecn_check_ce() functions to
    __tcp_ecn_check() and tcp_ecn_check(), or something like that.
    
    Would that work for this particular issue?
    
    Neal

Thanks Neal, it does work and is cleaner than what I was doing. I will submit a revised patch set.