Skip site navigation (1)Skip section navigation (2)
Date:      Mon, 12 Mar 2001 15:13:19 +0200
From:      Ruslan Ermilov <ru@FreeBSD.ORG>
To:        "Louis A. Mamakos" <louie@TransSys.COM>
Cc:        Jonathan Lemon <jlemon@flugsvamp.com>, Jonathan Lemon <jlemon@FreeBSD.ORG>, net@FreeBSD.ORG
Subject:   Re: Delayed checksums commit broke UDP checksum calculation
Message-ID:  <20010312151319.A75899@sunbay.com>
In-Reply-To: <200103071547.f27Fl6a00528@whizzo.transsys.com>; from louie@TransSys.COM on Wed, Mar 07, 2001 at 10:47:06AM -0500
References:  <20001116120936.A45755@sunbay.com> <20001116091954.A19895@prism.flugsvamp.com> <20010307123156.A19829@sunbay.com> <200103071440.f27EeYa99809@whizzo.transsys.com> <20010307164822.E97252@sunbay.com> <200103071458.f27EwWa99960@whizzo.transsys.com> <20010307171956.B36537@sunbay.com> <200103071547.f27Fl6a00528@whizzo.transsys.com>

next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, Mar 07, 2001 at 10:47:06AM -0500, Louis A. Mamakos wrote:
> 
> > To be CONSERVATIVE, the implementation MUST NOT transmit all-zero
> > computed TCP checksum as all-ones; while they are certainly equivalent
> > in one's complement arithmetics, but RFC 793 does not grant us to do
> > this conversion (as opposed to RFC 768), and there may an implementation
> > exist that computes checksums from scratch using the "shift-and-add-carry"
> > algorithm to compute the one's complement sum on a non-one's-complement
> > hardware, and compare the result with what stored in the checksum field.
> > In this case, +0 and -0 will differ.
> 
> I disagree on your conservative interpretation of the spec.  Here's
> the text from RFC 793, on TCP, and what it has to say about the
> checksum computation:
> 
>   Checksum:  16 bits
> 
>     The checksum field is the 16 bit one's complement of the one's
>     complement sum of all 16 bit words in the header and text.  If a
>     segment contains an odd number of header and text octets to be
>     checksummed, the last octet is padded on the right with zeros to
>     form a 16 bit word for checksum purposes.  The pad is not
>     transmitted as part of the segment.  While computing the checksum,
>     the checksum field itself is replaced with zeros.
> 
>     The checksum also covers a 96 bit pseudo header conceptually
>     prefixed to the TCP header.  This pseudo header contains the Source
>     Address, the Destination Address, the Protocol, and TCP length.
>     This gives the TCP protection against misrouted segments.  This
>     information is carried in the Internet Protocol and is transferred
>     across the TCP/Network interface in the arguments or results of
>     calls by the TCP on the IP.
> 
>                      +--------+--------+--------+--------+
>                      |           Source Address          |
>                      +--------+--------+--------+--------+
>                      |         Destination Address       |
>                      +--------+--------+--------+--------+
>                      |  zero  |  PTCL  |    TCP Length   |
>                      +--------+--------+--------+--------+
> 
>       The TCP Length is the TCP header length plus the data length in
>       octets (this is not an explicitly transmitted quantity, but is
>       computed), and it does not count the 12 octets of the pseudo
>       header.
> 
> For the sake of illustration, assume that you're computing a checksum
> over segment which contains all zeros.  This will produce a sum with
> a value of zero.  When you take the 16 bit one's complement of this
> value, you end up with 0xFFFF which is supposed to be put into the
> checksum field. 
> 
Not possible.  For IP, UDP, and TCP checksums, there is always a
non-zero member in the sum (protocol).

> For other segments which you're computing the checksum over, a
> properly implemented 1's complement arithemetic sum will produce
> a normalized +0 (0x0000) rather than a negative zero (0xFFFF).  So
> when you get to the step of taking the 1's complement (the logical
> NOT operation), you'll never start with 0xFFFF to produce a 0x0000
> result.  Of course the problem is that all these modern systems
> apparently don't have high-fidelity emulation of 1's complement
> add operations and are computing a -0 value along the way.
> 
Hmm, from where did you take this?  You seem to be constantly using
the term "normalized", where the -0 in one's complement representation
is replaced by +0, while the common definition of the one's complement
sum sounds like this:

: Addition of signed numbers in one's complement is performed using
: binary addition with end-around carry.  If there is a carry out of
: the most significant bit of the sum, this bit must be added to the
: least significant bit of the sum.

References:
  http://www.cs.uaf.edu/~cs301/notes/Chapter4/node4.html

  Mano, M.M. 1993.  Computer System Architecture, Third Edition
  ISBN: 0-13-175563-3.

And the IP checksum is defined as follows:

: The checksum field is the 16 bit one's complement of the one's
: complement sum of all 16 bit words in the header.  For purposes of
: computing the checksum, the value of the checksum field is zero.

From these definitions it follows that one's complement sum can never
be all zeroes except when all items are zeroes, which is not the
case for IP, UDP, and TCP.  Hereby, the checksum can never be 0xFFFF
except for UDP, which reserves 0 for "no checksum", and thus the
computed checksum value of 0 is stored as 0xFFFF.

> > To be LIBERAL, the implementation SHOULD verify checksums by computing
> > the checksum using the value stored in the checksum field, and comparing
> > the result with zero, as opposed to computing the checksum from scratch
> > and comparing with the value stored in the checksum field.
> 
> But computing a checksum with either 0xffff or 0x0000 WILL produce
> the same result if you are implementing the Internet 1's complement
> checksum algorithm correctly. 
> 
Let's assume (theoretically) that we are computing internet checksum for
"all zeroes" fragment.  Then one's complement sum for it will be 0x0000.
The checksum, which is the one's complement of the latter, is 0xFFFF.
If +0 and -0 were equivalent, then we could transmit 0x0000 as the
checksum.  The receiver then verifies the checksum: it computes one's
complement sum which is all zeroes, and one's complement of the latter,
which is 0xFFFF.  But the receiver expects zero.

> I can assure you that the stack I wrote in 1981, which ran on a
> 1's complement-based CPU sent TCP checksums with value 0xFFFF in
> the packet header, and it works Just Fine.  I don't see how
> reading that section of the TCP protocol spec would lead you to
> believe otherwise.
> 
I think then that your implementation is wrong WRT this.

Yes, +0 and -0 are equivalent for the purposes of arithmetic
operations in one's complement arithmetic, and +0 == -0 in one's
complement arithmetics, but they are represented differently, and
what matters here is the REPRESENTATION.  If the computed checksum
is +0, noone grants you (except UDP) to store -0 in place of it.

If the sender follows this closely, the "normalization" is not
needed.  I.e., the receiver operating on a two's complement ALU
can safely assume that it will receive all-ones after performing
a two's complement sum over payload.


Cheers,
-- 
Ruslan Ermilov		Oracle Developer/DBA,
ru@sunbay.com		Sunbay Software AG,
ru@FreeBSD.org		FreeBSD committer,
+380.652.512.251	Simferopol, Ukraine

http://www.FreeBSD.org	The Power To Serve
http://www.oracle.com	Enabling The Information Age

To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe freebsd-net" in the body of the message




Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20010312151319.A75899>