Bug in tcp_output?

[Chris Harrer]

Bruce and Rui,

I owe you an apology, sorry.  As I was reading Bruce's response, I was
saying to myself that something isn't adding up and sure enough I went back
and looked and noticed that I was running with a locally modified tcp_var.h
(which changed the snd_cwnd container).

The "clean" version does indeed work as expected.

Again, sorry for the "noise".

Thanks.

Chris
-----Original Message-----
From: Rui Paulo [mailto:rpaulo at gmail.com] On Behalf Of Rui Paulo
Sent: Sunday, March 21, 2010 9:15 AM
To: Bruce Evans
Cc: Chris Harrer; freebsd-net at freebsd.org
Subject: Re: Bug in tcp_output?


On 21 Mar 2010, at 07:17, Bruce Evans wrote:

> On Sat, 20 Mar 2010, Rui Paulo wrote:
> 
>> On 18 Mar 2010, at 20:19, Chris Harrer wrote:
>>> 
>>> In the following block of code, running on a x86_64 platform, I believe
that
>>> cwin should be declared as an int:
>>> ...
>>>              else {
>>> 
>>>                      long cwin;  ß-- Should be an int
>>> ...
>>>                      if (len > 0) {
>>> 
>>>                              cwin = tp->snd_cwnd -
>>> 
>>>                                     (tp->snd_nxt - tp->sack_newdata) -
>>> 
>>>                                     sack_bytes_rxmt;
>>> 
>>>                              if (cwin < 0)
>>> 
>>>                                     cwin = 0;
>>> 
>>>                              len = lmin(len, cwin);
>>> 
>>>                      }
>>> 
>>>              }
>>> 
>>>       }
>>> 
>>> 
>>> 
>>> Consider the case where:
>>> 
>>> sack_rxmit = 0
>>> 
>>> sack_bytes_rxmt = 0x2238
>>> 
>>> off = 0
>>> 
>>> len =0xa19c
>>> 
>>> tp->snd_cwnd = 0x2238
>>> 
>>> tp->snd_nxt = 0xdd6d7974
>>> 
>>> tp->sack_newdata = 0xdd6d6858
>>> 
>>> In this case cwin evaluates to 0x00000000ffffe37c, which is not <0, but
>>> instead huge.  This causes the remaining data on the socket’s so->so_snd
>>> buffer to be sent to the network causing more problems at the receiver
which
>>> is already dropping frames.
>> 
>> I see. This is most likely a bug. Can you send-pr so this doesn't get
lost?
> 
> What bug do you see?  This is most likely not a bug.  I only see the
> following bugs
> - the suggestion to increase the fragility of the code by changing cwin to
>  int
> - lots of whitespace lossage
> - the style bug in the declaration of cwin (nested declaration)
> - lots fragile but working code.  It depends on the machine being a normal
>  2's complement one.  It would fail on normal 1's complement machines and
>  on abnormal 2's complement ones, but so would many other things in the
>  kernel.
> - type and arithmetic errors that are not made at runtime resulting in a
>  value that wouldn't work, though the runtime value would.
> 
> Relevant code quoted again, with the whitespace fixed:
> 
>>>                              cwin = tp->snd_cwnd -
>>>                                     (tp->snd_nxt - tp->sack_newdata) -
>>>                                     sack_bytes_rxmt;
> 
> On 64-bit machines, with the above values, this is:
> 
> 				rhs = (u_long)0x2238UL -
> 				      ((tcp_seq)0xdd6d7974 -
> 				       (tcp_seq)0xdd6d6858) -
> 				      (int)0x2238;
> 				    = (u_long)0x2238UL -
> 				      ((uint32_t)0xdd6d7974 -
> 				       (uint32_t)0xdd6d6858) -
> 				      (int)0x2238;
> 				    = (u_long)0x2238UL -
> 				      (u_int)0x111c -
> 				      (int)0x2238;
> 				    = (u_long)0x111c -
> 				      (int)0x2238;
> 				    = (u_long)0x111c -
> 				      (u_long)0x2238;
> 				    = (u_long)0xffffffffffffeee4;
> 				cwin = (long)rhs;
> 				     = -(long)0x111c;
> 
> I might have made arithmetic errors too, but I'm sure that I got the
> conversions essentially correct.  On machines with 64-bit u_longs,
> almost everything is evaluated modulo 2^64.  This gives a large positive
> value, but not one with the top bits set up to only the 31st as would
> happen on machines with 32-bit u_longs.  Then the final conversion to
> long gives a negative value.

Right. I made some bad calculations.

> 
> This is fragile, but it is a standard 2's complement hack.  It would
> fail mainly on normal ones complement machines when the rhs is
> (u_long)0xFF...FF.  Then the lhs is probably negative 0, which is
> not less than 0.
> 
> The fragility is essentially the same on machines with 32-bit u_longs.
> Almost everything is evaluated modulo 2^32...
> 
> Using 64-bit u_longs for tp->snd_cwnd (and thus for almost the entire
> calculation) is exessive but doesn't cause any problems.
> 
> Using a signed type for sack_bytes_rxmt asks for sign extension bugs but
> doesn't get them.  Here it is promoted to a u_long so there are no
> sign extension bugs for it here.
> 
> Using a signed type for cwin is essential for the comparison of cwin
> with 0 to work.

Right.

>  This signed type should have the same size as the rhs
> to avoid even more fragility (if it were int, then you would have to
> worry about the value being changed to a non-working value by the
> implementation-defined conversion of the rhs to cwin not just for
> values larger than LONG_MAX but also for ones larger than INT_MAX.
> `int' should work in practice.  This and other things depend on the
> difference of the tcp_seq's not being anywhere near as large as
> 0x7fffffff).

I assumed that Chris saw a problem with this code after being hit by some
TCP/IP interop issue. Was this the case?

--
Rui Paulo