Subject: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

From: Kobby Carmona <[email-masked]>
Date: Thu, 4 Aug 2016 09:08:58 +0000

Hi all,
While running a bidirectional scenario with random drops in a network simulator of our (QLogic's NIC) TCP stack we found a case where it seems there is deadlock in the TCP protocol (the connection will keep sending pure acks from both sides until RTO will expire multiple times and a RST will sent to close the connection).
The scenario is as follows (there is an example with numbers for each stage assuming the MSS and each packet is 1000B):
1. Both sides are transmitting data and a single packet is dropped on either side and the next two packets are received properly
	Side A - SND.MAX=3000, SND.NXT=3000, SND.UNA=1000, RCV.NXT=11000, out-of-order block 12000-13000
	Side B - SND.MAX =13000, SND.NXT =13000, SND.UNA=11000, RCV.NXT=1000, out-of-order block 2000-3000
2. RTO timer expires on both sides
	Side A - SND.MAX=3000, SND.NXT=1000, SND.UNA=1000, RCV.NXT=11000, out-of-order block 12000-13000
	Side B - SND.MAX =13000, SND.NXT=11000, SND.UNA=11000, RCV.NXT=1000, out-of-order block 2000-3000
3. Both sides transmit a single packet to the peer:
	A->B - pkt.seq=1000, pkt.ack=11000, len=1000
	B->A - pkt.seq=11000, pkt.ack=1000, len=1000
3. Both sides receive the packets and update the receive context:
	Side A - SND.MAX=3000, SND.NXT=2000, SND.UNA=1000, RCV.NXT=13000
	Side B - SND.MAX=13000, SND.NXT=12000, SND.UNA=11000, RCV.NXT=3000
4. Both sides send another segment:
	A->B - pkt.seq=2000, pkt.ack=13000, len=1000
	B->A - pkt.seq=12000, pkt.ack=3000, len=1000
5. Both sides don't accept the packet (and don't update SND.UNA) since the sequence on the packet is less than RCV.NXT (sequence number check in page 69 of RFC793) and send a pure ACK instead
	A->B - pkt.seq=2000, pkt.ack=13000, len=0 (pure ACK)
	B->A - pkt.seq=12000, pkt.ack=3000, len=0 (pure ACK)
6. This will continue forever (until the connection will be terminated by RST) since every packet that ends before RCV.NXT (even a retransmit from SND.UNA) will be dropped.

Did anyone encountered this issue before? Is the anything we missed on this sequence?
If this is indeed a real deadlock, there might be several solutions to this which will require a modification in receive processing of RFC793. But I would like to know if you think this is a real issue before dealing with solutions.
Thanks,

	Kobby

---

From: David Borman <[email-masked]>
Date: Thu, 4 Aug 2016 14:36:37 -0500

After you pull back SND.NXT and do the retransmission, you should then restore SND.NXT back to where it was, not leave it at the backed off value; then the ACKs wouldn’t be dropped, since they wouldn’t have old seq values.  For example, in the 4.4BSD fast retransmit code it had:

			tcp_seq onxt = tp->snd_nxt;
			...
			tp->snd_nxt = th->th_ack;
			...
			(void) tcp_output(tp);
			...
			if (SEQ_GT(onxt, tp->snd_nxt))  
				tp->snd_nxt = onxt;

			-David Borman

> On Aug 4, 2016, at 4:08 AM, Kobby Carmona <[email-masked]> wrote:
> 
> Hi all,
> _______________________________________________
> tcpm mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tcpm

---

From: Kobby Carmona <[email-masked]>
Date: Sun, 7 Aug 2016 08:37:28 +0000

Hi David,
The code below is true for fast-retransmit.
But in case of retransmit timer expiration (TCPT_REXMT) snd_nxt is set to snd_una. And in this case CQND will be set to 1MSS so in the example below the transmitters can send only a single segment from sequence 2000/12000.

	Kobby

-----Original Message-----
From: David Borman [mailto:[email-masked]] 
Sent: Thursday, August 04, 2016 10:37 PM
To: Kobby Carmona <[email-masked]>
Cc: [email-masked]
Subject: Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

			-David Borman

> 	Side B - SND.MAX =13000, SND.NXT =13000, SND.UNA=11000, RCV.NXT=1000, 
> out-of-order block 2000-3000 2. RTO timer expires on both sides
> 	Side B - SND.MAX =13000, SND.NXT=11000, SND.UNA=11000, RCV.NXT=1000, 
> out-of-order block 2000-3000 3. Both sides transmit a single packet to the peer:
> 	B->A - pkt.seq=11000, pkt.ack=1000, len=1000 3. Both sides receive 
> the packets and update the receive context:
> 	Side B - SND.MAX=13000, SND.NXT=12000, SND.UNA=11000, RCV.NXT=3000 4. 
> Both sides send another segment:
> 	B->A - pkt.seq=12000, pkt.ack=3000, len=1000 5. Both sides don't 
> accept the packet (and don't update SND.UNA) since the sequence on the packet is less than RCV.NXT (sequence number check in page 69 of RFC793) and send a pure ACK instead
> 	B->A - pkt.seq=12000, pkt.ack=3000, len=0 (pure ACK) 6. This will 
> continue forever (until the connection will be terminated by RST) since every packet that ends before RCV.NXT (even a retransmit from SND.UNA) will be dropped.
>

---

From: David Borman <[email-masked]>
Date: Sun, 7 Aug 2016 16:35:04 -0500

> On Aug 7, 2016, at 3:37 AM, Kobby Carmona <[email-masked]> wrote:
> 
> Hi David,

Your underlying problem is that the ACK-only packets are being sent with the wrong sequence number, and that is what is causing them to be dropped.  One way to fix that is to put SND.NXT back to its previous value after do the the retransmit.  But you are correct, in the BSD code it only does that in the fast retransmit code; when the timer based retransmit code fires, it just pulls back SND.NXT to SND.UNA.  However, in the BSD code that I’m looking at, it keeps track of the largest sequence number sent in SND.MAX, and in the tcp_output() path there is this bit of code: 

       /*
        * If we are doing retransmissions, then snd_nxt will
        * not reflect the first unsent octet.  For ACK only
        * packets, we do not want the sequence number of the 
        * retransmitted packet, we want the sequence number
        * of the next unsent octet.  So, if there is no data
        * (and no SYN or FIN), use snd_max instead of snd_nxt
        * when filling in th_seq.  But if we are in persist
        * state, snd_max might reflect one byte beyond the
        * right edge of the window, so use snd_nxt in that
        * case, since we know we aren't doing a retransmission.
        * (retransmit and persist are mutually exclusive...)
        */
       if (len || (flags & (TH_SYN|TH_FIN)) || tp->t_timer[TCPT_PERSIST])
               th->th_seq = htonl(tp->snd_nxt);
       else
               th->th_seq = htonl(tp->snd_max);

That is what your implementation appears to be missing, and what is causing your ACK storm.  So yes, some variant of your problem has been seen before, and this is how the BSD code fixed it.

			-David Borman

---

From: Kobby Carmona <[email-masked]>
Date: Thu, 11 Aug 2016 20:46:20 +0000

Hi David,
This makes a lot of sense. We will fix our code.
Thanks for your help on this,

BTW,
Is this issue of mentioned in any RFC? If not do you see a point in adding explicit note on the SEQ of pure ACK in case of retransmission?

	Kobby

-----Original Message-----
From: David Borman [mailto:[email-masked]] 
Sent: Monday, August 08, 2016 12:35 AM
To: Kobby Carmona <[email-masked]>
Cc: [email-masked]
Subject: Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

       /*

			-David Borman

>> 	Side B - SND.MAX =13000, SND.NXT =13000, SND.UNA=11000, 
>> RCV.NXT=1000, out-of-order block 2000-3000 2. RTO timer expires on both sides

---

From: Yoshifumi Nishida <[email-masked]>
Date: Mon, 15 Aug 2016 15:39:15 -0700

Hello,
I personally think this is an interesting corner case for discussion.
It looks a minor one, but I'm not not very sure if we can leave it for each
implementation.
I also guess a question would be if the BSD's fix is the best way for the
issue.

Thanks,
--
Yoshi

On Thu, Aug 11, 2016 at 1:46 PM, Kobby Carmona <[email-masked]>
wrote:

> Is this issue of mentioned in any RFC? If not do you see a point in adding
> explicit note on the SEQ of pure ACK in case of retransmission?
>
>         Kobby
>
> > But in case of retransmit timer expiration (TCPT_REXMT) snd_nxt is set
> to snd_una. And in this case CQND will be set to 1MSS so in the example
> below the transmitters can send only a single segment from sequence
> 2000/12000.
>
> Your underlying problem is that the ACK-only packets are being sent with
> the wrong sequence number, and that is what is causing them to be dropped.
> One way to fix that is to put SND.NXT back to its previous value after do
> the the retransmit.  But you are correct, in the BSD code it only does that
> in the fast retransmit code; when the timer based retransmit code fires, it
> just pulls back SND.NXT to SND.UNA.  However, in the BSD code that I’m
> looking at, it keeps track of the largest sequence number sent in SND.MAX,
> and in the tcp_output() path there is this bit of code:
>
>        /*
> That is what your implementation appears to be missing, and what is
> causing your ACK storm.  So yes, some variant of your problem has been seen
> before, and this is how the BSD code fixed it.
>
>                         -David Borman
>
> >
> >       Kobby
> >
> > After you pull back SND.NXT and do the retransmission, you should then
> restore SND.NXT back to where it was, not leave it at the backed off value;
> then the ACKs wouldn’t be dropped, since they wouldn’t have old seq
> values.  For example, in the 4.4BSD fast retransmit code it had:
> >
> >> While running a bidirectional scenario with random drops in a network
> simulator of our (QLogic's NIC) TCP stack we found a case where it seems
> there is deadlock in the TCP protocol (the connection will keep sending
> pure acks from both sides until RTO will expire multiple times and a RST
> will sent to close the connection).
> >> The scenario is as follows (there is an example with numbers for each
> stage assuming the MSS and each packet is 1000B):
> >> 1. Both sides are transmitting data and a single packet is dropped on
> either side and the next two packets are received properly
> >> accept the packet (and don't update SND.UNA) since the sequence on the
> packet is less than RCV.NXT (sequence number check in page 69 of RFC793)
> and send a pure ACK instead
> >> continue forever (until the connection will be terminated by RST) since
> every packet that ends before RCV.NXT (even a retransmit from SND.UNA) will
> be dropped.
> >>
> >> If this is indeed a real deadlock, there might be several solutions to
> this which will require a modification in receive processing of RFC793. But
> I would like to know if you think this is a real issue before dealing with
> solutions.
> >> Thanks,
> >>
> >>      Kobby
> >>
> >>

---

From: Neal Cardwell <[email-masked]>
Date: Mon, 15 Aug 2016 21:18:47 -0400

> I also guess a question would be if the BSD's fix is the best way for the

Yes, I agree this is an interesting case for discussion.

FWIW, as a point of comparison for discussion, Linux's approach is a
little different: in Linux, the sender does not rewind SND.NXT on
retransmissions (RTO or Fast Recovery). Then the sender usually uses
SND.NXT for the seq field of outgoing pure ACKs. I say "usually"
because the Linux code has some code to deal with the case where the
receiver has withdrawn the receive window, so that SND.NXT is now
beyond the receive window. The code tcp_send_ack() uses to pick a seq
for outgoing pure ACKs looks like:

/* SND.NXT, if window was not shrunk.
 * If window has been shrunk, what should we make? It is not clear at
all.
 * Using SND.UNA we will fail to open window, SND.NXT is out of
window. :-(
 * Anything in between SND.UNA...SND.UNA+SND.WND also can be already
 * invalid. OK, let's make this for now:
 */
static inline __u32 tcp_acceptable_seq(const struct sock *sk)
{
        const struct tcp_sock *tp = tcp_sk(sk);

        if (!before(tcp_wnd_end(tp), tp->snd_nxt))
                return tp->snd_nxt;
        else
                return tcp_wnd_end(tp);
}

neal

---

From: David Borman <[email-masked]>
Date: Tue, 16 Aug 2016 00:09:36 -0500

Probably the more correct way of stating it is that ACK-only packets should be sent with the largest in-window sequence number that has ever been sent.  It is the only way to guarantee that the sequence number of the ACK will be within the window at the receiving side.

That being said, probe packets can be out of window.  And if the window is truly closed, you don’t want to send and ACK-only packet with that sequence number, as it will also be out of window.  Hence, send ACK-only packets with the largest in window sequence number.  In the BSD code probes are only one byte, and in persist state SND.NXT will be the largest in-window that has ever been sent.  But if we are in persist state because the ACK was lost or the window just opened and the probe data is accepted, the ACK will be to the left of the window by the size of the probe packet.  Hence the receiver needs to accept ACK packets one byte to the left of the window to prevent an ACK war.  The more general case is that you need to accept ACKs of at least N bytes to the left of the window, where N represents the largest size of probe that you will ever send.  That, along with sending ACKs with the largest in-window sequence number, will guarantee that you don’t get into an ACK war, even the two sides have different values for N  (only one side needs to accept the ACK to stop the ACK-war, and that will happen on the side with the larger value for N).

			-David Borman

> On Aug 15, 2016, at 5:39 PM, Yoshifumi Nishida <[email-masked]> wrote:
> 
> Hello,
> It looks a minor one, but I'm not not very sure if we can leave it for each implementation. 
> I also guess a question would be if the BSD's fix is the best way for the issue.
> 
> Thanks,
> --
> Yoshi
> 
> On Thu, Aug 11, 2016 at 1:46 PM, Kobby Carmona <[email-masked]> wrote:
> Hi David,

---

From: Yoshifumi Nishida <[email-masked]>
Date: Sun, 21 Aug 2016 10:25:04 -0700

Hi Neal,

Thanks for the info.
So, it seems to me that the linux code has the issue Kobby pointed out.
Or, am I missing something?
--
Yoshi

---

From: Neal Cardwell <[email-masked]>
Date: Sun, 21 Aug 2016 15:44:54 -0400

I am pretty sure Linux does not have the issue Kobby pointed out in this thread.

At a high level Linux should be OK because it follows the principle
David Borman laid out in his August 16 email: "ACK-only packets should
be sent with the largest in-window sequence number that has ever been
sent."

Linux obeys that principle by using tp->snd_nxt to store the largest
sequence number that has ever been sent, and having
tcp_acceptable_seq() use tp->snd_nxt but clamp the outgoing sequence
number to make sure it is in-window. To be able to do this, in Linux,
the sender does not rewind tp->snd_nxt on retransmissions.

neal

---

From: Yoshifumi Nishida <[email-masked]>
Date: Tue, 23 Aug 2016 00:06:48 -0700

Hi Neal,

Oh. I see. Thanks for the explanation.
I'd like to think about it a bit more.
Thanks,
--
Yoshi