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

[Yoshifumi Nishida <[e-mail]>]

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 <[e-mail]>
wrote:

> 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
>
> _______________________________________________
> tcpm mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/tcpm
>