From owner-freebsd-net Mon Mar 12 5:21:40 2001 Delivered-To: freebsd-net@freebsd.org Received: from whale.sunbay.crimea.ua (whale.sunbay.crimea.ua [212.110.138.65]) by hub.freebsd.org (Postfix) with ESMTP id ED56637B719; Mon, 12 Mar 2001 05:21:07 -0800 (PST) (envelope-from ru@whale.sunbay.crimea.ua) Received: (from ru@localhost) by whale.sunbay.crimea.ua (8.11.2/8.11.2) id f2CDDJA80981; Mon, 12 Mar 2001 15:13:19 +0200 (EET) (envelope-from ru) Date: Mon, 12 Mar 2001 15:13:19 +0200 From: Ruslan Ermilov To: "Louis A. Mamakos" Cc: Jonathan Lemon , Jonathan Lemon , net@FreeBSD.ORG Subject: Re: Delayed checksums commit broke UDP checksum calculation Message-ID: <20010312151319.A75899@sunbay.com> Mail-Followup-To: "Louis A. Mamakos" , Jonathan Lemon , Jonathan Lemon , net@FreeBSD.ORG 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> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: <200103071547.f27Fl6a00528@whizzo.transsys.com>; from louie@TransSys.COM on Wed, Mar 07, 2001 at 10:47:06AM -0500 Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org 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