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

[Kobby Carmona <[e-mail]>]

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:[e-mail]] 
Sent: Monday, August 08, 2016 12:35 AM
To: Kobby Carmona <[e-mail]>
Cc: [e-mail]
Subject: Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

> On Aug 7, 2016, at 3:37 AM, Kobby Carmona <[e-mail]> wrote:
> 
> 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.

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

> 
> 	Kobby
> 
> -----Original Message-----
> From: David Borman [mailto:[e-mail]]
> Sent: Thursday, August 04, 2016 10:37 PM
> To: Kobby Carmona <[e-mail]>
> Cc: [e-mail]
> Subject: Re: [tcpm] Possible deadlock scenario with retransmission on 
> both sides at the same time
> 
> 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 <[e-mail]> wrote:
>> 
>> 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
>> 
>> 
>> _______________________________________________
>> tcpm mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/tcpm
> 
> _______________________________________________
> tcpm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tcpm