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

[Yoshifumi Nishida <[e-mail]>]

Hello,

I'm not very sure how many folks are interested in this, but anyway...
I have tested this with packetdrill on linux, netbsd, freebsd and openbsd.

As far as I tested, linux works just like Neal described.
On the other hand, I found a minor issue in others' behavior.
In their tcp input functions, they haven't checked sequence number when
they update ack value while it is checked later in the code. Because of
this, it behaves like the followings.

00:42:58.395100 192.0.2.1.54613 > 192.168.0.1.8080: Flags [S],  seq 0, win
20000, options [mss 1000], length 0
00:42:58.395120 192.168.0.1.8080 > 192.0.2.1.54613: Flags [S.], seq
4183682776, ack 1, win 65535, length 0
00:43:01.422728 192.168.0.1.8080 > 192.0.2.1.54613: Flags [S.], seq
4183682776, ack 1, win 65535, length 0
00:43:01.422801 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq 1, ack
1, win 20000, length 0
00:43:02.443166 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq
2001:3001, ack 1, win 20000, length 1000
00:43:02.468148 192.168.0.1.8080 > 192.0.2.1.54613: Flags [.],  seq 1, ack
1, win 65535, length 0
00:43:04.471409 192.168.0.1.8080 > 192.0.2.1.54613: Flags [P.], seq 1:1001,
ack 1, win 65535, length 1000
00:43:06.531462 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq 1:1001,
ack 1001, win 20000, length 1000
00:43:06.555492 192.168.0.1.8080 > 192.0.2.1.54613: Flags [.],  seq
1001:2001, ack 1001, win 65000, length 1000
00:43:06.555973 192.168.0.1.8080 > 192.0.2.1.54613: Flags [P.], seq
2001:3001, ack 1001, win 65000, length 1000
00:43:07.056276 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq
1001:2001, ack 1001, win 20000, length 1000
00:43:07.084910 192.168.0.1.8080 > 192.0.2.1.54613: Flags [.],  seq 3001,
ack 3001, win 63000, length 0
00:43:07.585918 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq
1001:2001, ack 2001, win 20000, length 1000
00:43:07.607117 192.168.0.1.8080 > 192.0.2.1.54613: Flags [.],  seq 3001,
ack 3001, win 63000, length 0
00:43:08.109788 192.0.2.1.54613 > 192.168.0.1.8080: Flags [.],  seq 2001,
ack 2001, win 20000, length 0
00:43:13.908734 192.168.0.1.8080 > 192.0.2.1.54613: Flags [P.], seq
2001:3001, ack 3001, win 63000, length 1000

In this dump file, src addr 192.0.2.1 are the packets generated by
packetdrill and src addr 192.168.0.1 are the packets from OSes. While the
ack values in packets at 00:43:07.585918 and 00:43:13.908734 should be
ignored, it is actually used to update snd_nxt.
As the result, we saw seq 2001:3001 was retransmited after timeout instead
of 1001:2001.
(But, it also means this logic won't create the deadlock situation Kobby
mentioned)

When I added seq num check in updating ack value in FreeBSD code, it works
just like expected.
--
Yoshi


On Tue, Aug 23, 2016 at 12:06 AM, Yoshifumi Nishida <[e-mail]>
wrote:

> Hi Neal,
>
> Oh. I see. Thanks for the explanation.
> I'd like to think about it a bit more.
> Thanks,
> --
> Yoshi
>
>
> On Sun, Aug 21, 2016 at 12:44 PM, Neal Cardwell <[e-mail]>
> wrote:
>
>> 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
>>
>> On Sun, Aug 21, 2016 at 1:25 PM, Yoshifumi Nishida
>> <[e-mail]> wrote:
>> > 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
>> >
>> >
>> > On Mon, Aug 15, 2016 at 6:18 PM, Neal Cardwell <[e-mail]>
>> wrote:
>> >>
>> >> On Mon, Aug 15, 2016 at 6:39 PM, Yoshifumi Nishida
>> >> <[e-mail]> wrote:
>> >> > 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.
>> >>
>> >> 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
>> >
>> >
>>
>
>