Subject: Window probe deadlock writeup

From: Vern Paxson <[email-masked]>
Date: Tue, 10 Nov 1998 09:44:18 PST

3.12.

Name of Problem
     Window probe deadlock

Classification
     Reliability

Description
     When an application reads a single byte from a full window, the
     window should not be updated, in order to avoid Silly Window
     Syndrome (SWS; see [RFC813]).  If the remote peer uses a single
     byte of data to probe the window, that byte can be accepted into
     the buffer.  In some implementations, at this point a negative
     argument to a signed comparison causes all further new data to be
     considered outside the window; consequently, it is discarded (after
     sending an ACK to resynchronize).  These discards include the ACKs
     for the data packets sent by the local TCP, so the TCP will
     consider the data unacknowledged.

     Consequently, the application may be unable to complete sending new
     data to the remote peer, because it has exhausted the transmit
     buffer available to its local TCP, and buffer space is never being
     freed because incoming ACKs that would do so are being discarded.
     If the application does not read any more data, which may happen
     due to its failure to complete such sends, then deadlock results.

Significance
     It's relatively rare for applications to use TCP in a manner that
     can exercise this problem.  Most applications only transmit bulk
     data if they know the other end is prepared to receive the data.
     However, if a client fails to consume data, putting the server in

Paxson, Editor                                                 [Page 38]

ID                 Known TCP Implementation Problems       November 1998

     persist mode, and then consumes a small amount of data, it can
     mistakenly compute a negative window.  At this point the client
     will discard all further packets from the server, including ACKs of
     the client's own data, since they are not inside the (impossibly-
     sized) window.  If subsequently the client consumes enough data to
     then send a window update to the server, the situation will be
     rectified.  That is, this situation can only happen if the client
     consumes 1 < N < MSS bytes, so as not to cause a window update, and
     then starts its own transmission towards the server of more than a
     window's worth of data.

Implications
     TCP connections will hang and eventually time out.

Relevant RFCs
     RFC 793 describes zero window probing.  RFC 813 describes Silly
     Window Syndrome.

Trace file demonstrating it
     Trace made from a version of tcpdump modified to print out the
     sequence number attached to an ACK even if it's dataless.  An
     unmodified tcpdump would not print seq:seq(0); however, for this
     bug, the sequence number in the ACK is important for unambiguously
     determining how the TCP is behaving.

     [ Normal connection startup and data transmission from B to A.
       Options, including MSS of 16344 in both directions, omitted
       for clarity. ]
     16:07:32.327616 A > B: S 65360807:65360807(0) win 8192
     16:07:32.327304 B > A: S 65488807:65488807(0) ack 65360808 win 57344
     16:07:32.327425 A > B: . 1:1(0) ack 1 win 57344
     16:07:32.345732 B > A: P 1:2049(2048) ack 1 win 57344
     16:07:32.347013 B > A: P 2049:16385(14336) ack 1 win 57344
     16:07:32.347550 B > A: P 16385:30721(14336) ack 1 win 57344
     16:07:32.348683 B > A: P 30721:45057(14336) ack 1 win 57344
     16:07:32.467286 A > B: . 1:1(0) ack 45057 win 12288
     16:07:32.467854 B > A: P 45057:57345(12288) ack 1 win 57344

     [ B fills up A's offered window ]
     16:07:32.667276 A > B: . 1:1(0) ack 57345 win 0

     [ B probes A's window with a single byte ]
     16:07:37.467438 B > A: . 57345:57346(1) ack 1 win 57344

     [ A resynchronizes without accepting the byte ]

Paxson, Editor                                                 [Page 39]

ID                 Known TCP Implementation Problems       November 1998

     16:07:37.467678 A > B: . 1:1(0) ack 57345 win 0

     [ B probes A's window again ]
     16:07:45.467438 B > A: . 57345:57346(1) ack 1 win 57344

     [ A resynchronizes and accepts the byte (per the ack field) ]
     16:07:45.667250 A > B: . 1:1(0) ack 57346 win 0

     [ The application on A has started generating data.  The first
       packet A sends is small due to a memory allocation bug. ]
     16:07:51.358459 A > B: P 1:2049(2048) ack 57346 win 0

     [ B acks A's first packet ]
     16:07:51.467239 B > A: . 57346:57346(0) ack 2049 win 57344

     [ This looks as though A accepted B's ACK and is sending
       another packet in response to it.  In fact, A is trying
       to resynchronize with B, and happens to have data to send
       and can send it because the first small packet didn't use
       up cwnd. ]
     16:07:51.467698 A > B: . 2049:14337(12288) ack 57346 win 0

     [ B acks all of the data that A has sent ]
     16:07:51.667283 B > A: . 57346:57346(0) ack 14337 win 57344

     [ A tries to resynchronize.  Notice that by the packets
       seen on the network, A and B *are* in fact synchronized;
       A only thinks that they aren't. ]
     16:07:51.667477 A > B: . 14337:14337(0) ack 57346 win 0

     [ A's retransmit timer fires, and B acks all of the data.
       A once again tries to resynchronize. ]
     16:07:52.467682 A > B: . 1:14337(14336) ack 57346 win 0
     16:07:52.468166 B > A: . 57346:57346(0) ack 14337 win 57344
     16:07:52.468248 A > B: . 14337:14337(0) ack 57346 win 0

     [ A's retransmit timer fires again, and B acks all of the data.
       A once again tries to resynchronize. ]
     16:07:55.467684 A > B: . 1:14337(14336) ack 57346 win 0
     16:07:55.468172 B > A: . 57346:57346(0) ack 14337 win 57344
     16:07:55.468254 A > B: . 14337:14337(0) ack 57346 win 0

Trace file demonstrating correct behavior
     Made between the same two hosts after applying the bug fix
     mentioned below (and using the same modified tcpdump).

     [ Connection starts up with data transmission from B to A.

Paxson, Editor                                                 [Page 40]

ID                 Known TCP Implementation Problems       November 1998

       Note that due to a separate bug (the fact that A and B
       are communicating over a loopback driver), B erroneously
       skips slow start. ]
     17:38:09.510854 A > B: S 3110066585:3110066585(0) win 16384
     17:38:09.510926 B > A: S 3110174850:3110174850(0) ack 3110066586 win 57344
     17:38:09.510953 A > B: . 1:1(0) ack 1 win 57344
     17:38:09.512956 B > A: P 1:2049(2048) ack 1 win 57344
     17:38:09.513222 B > A: P 2049:16385(14336) ack 1 win 57344
     17:38:09.513428 B > A: P 16385:30721(14336) ack 1 win 57344
     17:38:09.513638 B > A: P 30721:45057(14336) ack 1 win 57344
     17:38:09.519531 A > B: . 1:1(0) ack 45057 win 12288
     17:38:09.519638 B > A: P 45057:57345(12288) ack 1 win 57344

     [ B fills up A's offered window ]
     17:38:09.719526 A > B: . 1:1(0) ack 57345 win 0

     [ B probes A's window with a single byte.  A resynchronizes
       without accepting the byte ]
     17:38:14.499661 B > A: . 57345:57346(1) ack 1 win 57344
     17:38:14.499724 A > B: . 1:1(0) ack 57345 win 0

     [ B probes A's window again.  A resynchronizes and accepts
       the byte, as indicated by the ack field ]
     17:38:19.499764 B > A: . 57345:57346(1) ack 1 win 57344
     17:38:19.519731 A > B: . 1:1(0) ack 57346 win 0

     [ B probes A's window with a single byte.  A resynchronizes
       without accepting the byte ]
     17:38:24.499865 B > A: . 57346:57347(1) ack 1 win 57344
     17:38:24.499934 A > B: . 1:1(0) ack 57346 win 0

     [ The application on A has started generating data.
       B acks A's data and A accepts the ACKs and the
       data transfer continues ]
     17:38:28.530265 A > B: P 1:2049(2048) ack 57346 win 0
     17:38:28.719914 B > A: . 57346:57346(0) ack 2049 win 57344

     17:38:28.720023 A > B: . 2049:16385(14336) ack 57346 win 0
     17:38:28.720089 A > B: . 16385:30721(14336) ack 57346 win 0
     17:38:28.720370 B > A: . 57346:57346(0) ack 30721 win 57344

     17:38:28.720462 A > B: . 30721:45057(14336) ack 57346 win 0
     17:38:28.720526 A > B: P 45057:59393(14336) ack 57346 win 0
     17:38:28.720824 A > B: P 59393:73729(14336) ack 57346 win 0
     17:38:28.721124 B > A: . 57346:57346(0) ack 73729 win 47104

     17:38:28.721198 A > B: P 73729:88065(14336) ack 57346 win 0
     17:38:28.721379 A > B: P 88065:102401(14336) ack 57346 win 0

Paxson, Editor                                                 [Page 41]

ID                 Known TCP Implementation Problems       November 1998

     17:38:28.721557 A > B: P 102401:116737(14336) ack 57346 win 0
     17:38:28.721863 B > A: . 57346:57346(0) ack 116737 win 36864

References
     None known.

How to detect
     Initiate a connection from a client to a server.  Have the server
     continuously send data until its buffers have been full for long
     enough to exhaust the window.  Next, have the client read 1 byte
     and then delay for long enough that the server TCP sends a window
     probe.  Now have the client start sending data.  At this point, if
     it ignores the server's ACKs, then the client's TCP suffers from
     the problem.

How to fix
     In one implementation known to exhibit the problem (derived from
     4.3-Reno), the problem was introduced when the macro MAX() was
     replaced by the function call max() for computing the amount of
     space in the receive window:

         tp->rcv_wnd = max(win, (int)(tp->rcv_adv - tp->rcv_nxt));

     When data has been received into a window beyond what has been
     advertised to the other side, rcv_nxt > rcv_adv, making this
     negative.  It's clear from the (int) cast that this is intended,
     but the unsigned max() function sign-extends so the negative number
     is "larger".  The fix is to change max() to imax():

         tp->rcv_wnd = imax(win, (int)(tp->rcv_adv - tp->rcv_nxt));

     4.3-Tahoe and before did not have this bug, since it used the macro
     MAX() for this calculation.