Re: [IPX]: Fix checksum computation.

Re: [IPX]: Fix checksum computation.

[David S. Miller]

On Fri, 31 Oct 2003 13:24:06 -0800
Joe Perches <joe@perches.com> wrote:

> Why is this a "fix"?  Performance?
> It seems more like someone's idea of code neatening.

IPC checksums were being miscomputed in the original code,
we're as mystified as you are as to why it is that:

	if (sum & 0x10000) {
		sum++;
		sum &= 0xffff;
	}

works while:

	sum = ((sym >> 16) + sum) & 0xffff;

does not.  The theory was that it might be some x86 gcc bug,
but looking at the assembler diff Arnaldo Carvalho de Melo
(the appletalk maintainer) showed me between the before and
after:

 	xorl	%eax, %eax
-	decl	%ecx
 	movb	(%ebx), %al
-	incl	%ebx
 	addl	%eax, %edx
 	addl	%edx, %edx
-	movl	%edx, %eax
-	shrl	$16, %eax
-	addl	%edx, %eax
-	movzwl	%ax,%edx
+	testl	$65536, %edx
+	je	.L982
+	incl	%edx
+	andl	$65535, %edx
+.L982:
+	decl	%ecx
+	incl	%ebx
 	cmpl	$-1, %ecx

we still can't see what's wrong.

He did confirm that the change in question makes IPX compute checksums
correctly.

Re: [IPX]: Fix checksum computation.

[Joe Perches]

On Thu, 2003-10-30 at 19:43, Linux Kernel Mailing List wrote:
> ChangeSet 1.1399, 2003/10/30 19:43:04-08:00, davem@nuts.ninka.net
> 	[IPX]: Fix checksum computation.
> diff -Nru a/net/appletalk/ddp.c b/net/appletalk/ddp.c
> --- a/net/appletalk/ddp.c	Fri Oct 31 12:06:06 2003
> +++ b/net/appletalk/ddp.c	Fri Oct 31 12:06:06 2003
> @@ -937,9 +937,13 @@
>  {
>  	/* This ought to be unwrapped neatly. I'll trust gcc for now */
>  	while (len--) {
> -		sum += *data++;
> +		sum += *data;
>  		sum <<= 1;
> -		sum = ((sum >> 16) + sum) & 0xFFFF;
> +		if (sum & 0x10000) {
> +			sum++;
> +			sum &= 0xffff;
> +		}
> +		data++;
>  	}
>  	return sum;
>  }

This change didn't appear on this list for comment,
it just appeared in the source.

Why is this a "fix"?  Performance?
It seems more like someone's idea of code neatening.

If this is done, why not if (unlikely())

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 01:24:06PM -0800, Joe Perches escreveu:
> On Thu, 2003-10-30 at 19:43, Linux Kernel Mailing List wrote:
> > ChangeSet 1.1399, 2003/10/30 19:43:04-08:00, davem@nuts.ninka.net
> > 	[IPX]: Fix checksum computation.
> > diff -Nru a/net/appletalk/ddp.c b/net/appletalk/ddp.c
> > --- a/net/appletalk/ddp.c	Fri Oct 31 12:06:06 2003
> > +++ b/net/appletalk/ddp.c	Fri Oct 31 12:06:06 2003
> > @@ -937,9 +937,13 @@
> >  {
> >  	/* This ought to be unwrapped neatly. I'll trust gcc for now */
> >  	while (len--) {
> > -		sum += *data++;
> > +		sum += *data;
> >  		sum <<= 1;
> > -		sum = ((sum >> 16) + sum) & 0xFFFF;
> > +		if (sum & 0x10000) {
> > +			sum++;
> > +			sum &= 0xffff;
> > +		}
> > +		data++;
> >  	}
> >  	return sum;
> >  }
> 
> This change didn't appear on this list for comment,
> it just appeared in the source.
> 
> Why is this a "fix"?  Performance?
> It seems more like someone's idea of code neatening.
> 
> If this is done, why not if (unlikely())

No, the reverse is true, with the patch it is the same as in 2.4, when Stephen
did the conversion to handle paged skbs it did what you called "neatening"
(i.e.  without the patch above), now, if you care, go try to use this with
recent gcc, and get back with your results.

Mine were: reversing this patch makes the checksum calculations sometimes
wrong, preventing Appletalk from working.

Mind boggling? Yes, did it fixed a problem? Yes.

- Arnaldo

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 01:23:31PM -0800, David S. Miller escreveu:
> On Fri, 31 Oct 2003 13:24:06 -0800
> He did confirm that the change in question makes IPX compute checksums
> correctly.

s/IPX/Appletalk/g

8)

- Arnaldo

Re: [IPX]: Fix checksum computation.

[Joe Perches]

On Fri, 2003-10-31 at 13:23, David S. Miller wrote:
> we're as mystified as you are as to why it is that:
> 	if (sum & 0x10000) {
> 		sum++;
> 		sum &= 0xffff;
> 	}
> works while:
> 	sum = ((sym >> 16) + sum) & 0xffff;
> does not.  The theory was that it might be some x86 gcc bug,
> but looking at the assembler diff Arnaldo Carvalho de Melo
> (the appletalk maintainer) showed me between the before and
> after:
>  	xorl	%eax, %eax
> -	decl	%ecx
>  	movb	(%ebx), %al
> -	incl	%ebx
>  	addl	%eax, %edx
>  	addl	%edx, %edx
> -	movl	%edx, %eax
> -	shrl	$16, %eax
> -	addl	%edx, %eax
> -	movzwl	%ax,%edx
> +	testl	$65536, %edx
> +	je	.L982
> +	incl	%edx
> +	andl	$65535, %edx
> +.L982:
> +	decl	%ecx
> +	incl	%ebx
>  	cmpl	$-1, %ecx
> 
> we still can't see what's wrong.
> He did confirm that the change in question makes IPX compute checksums
> correctly.

If so, something major is WRONG.
Code all over the place would need this "fix".

Was an old NG Sniffer being used to verify this?
Sniffer had a long term problem with IPX checksums.

Has the gcc team been contacted?

Re: [IPX]: Fix checksum computation.

[David S. Miller]

On Fri, 31 Oct 2003 13:50:04 -0800
Joe Perches <joe@perches.com> wrote:

> Was an old NG Sniffer being used to verify this?
> Sniffer had a long term problem with IPX checksums.

No, Arnaldo would verify the checksum by running the
old code and the new code, they produced different
checksums on every sendmsg() call.

He then tested it further by making sure he could use
netatalk successfully between a 2.4.x Linux appletalk
box and a 2.6.x system with the checksum patch applied.
Without the patch the 2.4.x system would reject all packets
sent by the 2.6.x box.

Don't assume that we're a bunch of fucknuts and didn't
verify things to the best of our abilities ok?  Thanks.

> Has the gcc team been contacted?

Why would we contact them before we even know if it's
a gcc bug or not?  It could be a sign extension issue or
something else that our brains are not grokking at the
moment.  Contacting the gcc team would be utterly premature.

Here is something you could do for us instead of your current
blabbering.  Why don't you take a look at the assembler diff I posted
and try to figure out how the before code produces a different
checksum than the after code?

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 01:50:04PM -0800, Joe Perches escreveu:
> On Fri, 2003-10-31 at 13:23, David S. Miller wrote:
> > we're as mystified as you are as to why it is that:
> > 	if (sum & 0x10000) {
> > 		sum++;
> > 		sum &= 0xffff;
> > 	}
> > works while:
> > 	sum = ((sym >> 16) + sum) & 0xffff;
> > does not.  The theory was that it might be some x86 gcc bug,
> > but looking at the assembler diff Arnaldo Carvalho de Melo
> > (the appletalk maintainer) showed me between the before and
> > after:
> >  	xorl	%eax, %eax
> > -	decl	%ecx
> >  	movb	(%ebx), %al
> > -	incl	%ebx
> >  	addl	%eax, %edx
> >  	addl	%edx, %edx
> > -	movl	%edx, %eax
> > -	shrl	$16, %eax
> > -	addl	%edx, %eax
> > -	movzwl	%ax,%edx
> > +	testl	$65536, %edx
> > +	je	.L982
> > +	incl	%edx
> > +	andl	$65535, %edx
> > +.L982:
> > +	decl	%ecx
> > +	incl	%ebx
> >  	cmpl	$-1, %ecx
> > 
> > we still can't see what's wrong.
> > He did confirm that the change in question makes IPX compute checksums
> > correctly.
> 
> If so, something major is WRONG.

I guess so. If people with an Appletalk testbed could try with and without
the patch, that would be great.

> Code all over the place would need this "fix".

Haven't noticed any other place with this problem, but yes, this is something
that may well happen in other code.

> Was an old NG Sniffer being used to verify this?

Nope, MacOS 7.5.5 and 9 just hang when communicating with the machine without
this patch, gcc 3.3.1/2 was used.

> Sniffer had a long term problem with IPX checksums.

I added back the old atalk_checksum from 2.4 and compared the results, not
all were wrong, but some were.
 
> Has the gcc team been contacted?

Nope, feel free to forward this message.

- Arnaldo

Re: [IPX]: Fix checksum computation.

[Stephen Hemminger]

On Fri, 31 Oct 2003 13:53:28 -0800
"David S. Miller" <davem@redhat.com> wrote:

> On Fri, 31 Oct 2003 13:50:04 -0800
> Joe Perches <joe@perches.com> wrote:
> 
> > Was an old NG Sniffer being used to verify this?
> > Sniffer had a long term problem with IPX checksums.
> 
> No, Arnaldo would verify the checksum by running the
> old code and the new code, they produced different
> checksums on every sendmsg() call.
> 
> He then tested it further by making sure he could use
> netatalk successfully between a 2.4.x Linux appletalk
> box and a 2.6.x system with the checksum patch applied.
> Without the patch the 2.4.x system would reject all packets
> sent by the 2.6.x box.
>

Actually, the before the "optimization" went in I did testing between
old 2.4.x and 2.6.x as well as standalone comparisons.  The problem is
a compiler screwup, that probably isn't worth investigating further.

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 02:21:31PM -0800, Stephen Hemminger escreveu:
> On Fri, 31 Oct 2003 13:53:28 -0800
> "David S. Miller" <davem@redhat.com> wrote:
> 
> > On Fri, 31 Oct 2003 13:50:04 -0800
> > Joe Perches <joe@perches.com> wrote:
> > 
> > > Was an old NG Sniffer being used to verify this?
> > > Sniffer had a long term problem with IPX checksums.
> > 
> > No, Arnaldo would verify the checksum by running the
> > old code and the new code, they produced different
> > checksums on every sendmsg() call.
> > 
> > He then tested it further by making sure he could use
> > netatalk successfully between a 2.4.x Linux appletalk
> > box and a 2.6.x system with the checksum patch applied.
> > Without the patch the 2.4.x system would reject all packets
> > sent by the 2.6.x box.
> >
> 
> Actually, the before the "optimization" went in I did testing between
> old 2.4.x and 2.6.x as well as standalone comparisons.  The problem is
> a compiler screwup, that probably isn't worth investigating further.

But if someone wants to I'd be glad to receive test reports with and without
the patch.

Hey, that way we can get more testers for Appletalk in 2.6 8)

- Arnaldo

Re: [IPX]: Fix checksum computation.

[Mark Huth]

David S. Miller wrote:

>On Fri, 31 Oct 2003 13:24:06 -0800
>Joe Perches <joe@perches.com> wrote:
>
>  
>
>>Why is this a "fix"?  Performance?
>>It seems more like someone's idea of code neatening.
>>    
>>
>
>IPC checksums were being miscomputed in the original code,
>we're as mystified as you are as to why it is that:
>
>	if (sum & 0x10000) {
>		sum++;
>		sum &= 0xffff;
>	}
>
>works while:
>
>	sum = ((sym >> 16) + sum) & 0xffff;
>
>does not.  The theory was that it might be some x86 gcc bug,
>but looking at the assembler diff Arnaldo Carvalho de Melo
>(the appletalk maintainer) showed me between the before and
>after:
>
Nah, they are different algorithms, as the assembler code clearly 
demonstrates.  The above snippet is incomplete, with the crucial 
multiply by 2 or the shift left omitted.  The assembler code reveals 
this crucial piece of information.

>
> 	xorl	%eax, %eax
>-	decl	%ecx
> 	movb	(%ebx), %al
>-	incl	%ebx
> 	addl	%eax, %edx
> 	addl	%edx, %edx
>-	movl	%edx, %eax
>-	shrl	$16, %eax
>-	addl	%edx, %eax
>
The previous instruction adds 0, 1, or 2 to the checksum accumulation. 
 That's because in the case where
the byte added to the accumulation (addl %eax, %edx) causes the 16 bit 
to set, then when multiplied by 2 (addl %edx, %edx) the 17 bit is set 
and the 16 bit is clear.

>-	movzwl	%ax,%edx
>+	testl	$65536, %edx
>+	je	.L982
>
This version adds one to the accumulation iff bit 16 is set following 
the multiply.  The results are clearly different. This latter version 
would be a correct implementation of  feedback shiftregister algorithm, 
assuming that is what is being computed instead of a simple checksum. 
 Not knowing the specification for the algorithm offhand, I can't say 
which is correct.

They will, however, _sometimes_ give the same results.  That probably 
explains the rest of the comments in this thread.

>+	incl	%edx
>+	andl	$65535, %edx
>+.L982:
>+	decl	%ecx
>+	incl	%ebx
> 	cmpl	$-1, %ecx
>
>we still can't see what's wrong.
>
>He did confirm that the change in question makes IPX compute checksums
>correctly.
>
>
>
>  
>

Re: [IPX]: Fix checksum computation.

[David S. Miller]

On Fri, 31 Oct 2003 14:21:31 -0800
Stephen Hemminger <shemminger@osdl.org> wrote:

> Actually, the before the "optimization" went in I did testing between
> old 2.4.x and 2.6.x as well as standalone comparisons.  The problem is
> a compiler screwup, that probably isn't worth investigating further.

See Mark Huth's email, I think his analysis is correct and
that the two pieces of C code are really doing different
things.

Re: [IPX]: Fix checksum computation.

[David S. Miller]

On Fri, 31 Oct 2003 16:31:29 -0800
Joe Perches <joe@perches.com> wrote:

> Right.  My mistake.  Clear upon explanation, thanks.
> I think I misread based on expectation rather than code.

Good thing we didn't report this to the gcc developers.
ROFL...

Re: [IPX]: Fix checksum computation.

[Joe Perches]

On Fri, 2003-10-31 at 15:29, Mark Huth wrote:
> Nah, they are different algorithms, as the assembler code clearly 
> demonstrates.  The above snippet is incomplete, with the crucial 
> multiply by 2 or the shift left omitted.  The assembler code reveals 
> this crucial piece of information.

Right.  My mistake.  Clear upon explanation, thanks.
I think I misread based on expectation rather than code.

Re: [IPX]: Fix checksum computation.

[Stephen Hemminger]

Okay, here is the standard: (Inside Appletalk)

> The DDP checksum is provided to detect errors caused by faulty operation (such as memor
> data bus errors) within routers on the internet. Implementers of DDP should treat generati
> the checksum as an optional feature. The 16-bit DDP checksum is computed as follows:
> CkSum := 0 ;
> FOR each datagram byte starting with the byte immediately following th
> Checksum field
> REPEAT the following algorithm:
>           CkSum := CkSum + byte; (unsigned addition)
>           Rotate CkSum left one bit, rotating the most significant bit in
>                               least significant bit;
> IF, at the end, CkSum = 0 THEN
>           CkSum := $FFFF (all ones).
> Reception of a datagram with CkSum equal to 0 implies that a checksum is not performed.


Here is the old loop:

	while (len--) {
		sum += *data;
		sum <<=1;
		if (sum & 0x10000) {
			sum++;
			sum &= 0xffff;
		}
		data++;
	}

My buggy loop is:

	while (len--) {
		sum += *data++;
		sum <<= 1;
		sum = ((sum >> 16) + sum) & 0xFFFF;
	}

The problem is the carry from the first addition needs to be dropped
not folded back (like IP).  

Corrected fast code is:

	while (len--) {
		sum += *data++;
		sum <<= 1;
		sum = (((sum & 0x10000) >> 16) + sum) & 0xffff;
	}

At least it is correct on the standalone random data test, and the
new code is 30% faster for the cached memory case (13.7 clks/byte vs 18 clks/byte).

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 04:38:43PM -0800, Stephen Hemminger escreveu:
> 
> Okay, here is the standard: (Inside Appletalk)
> 
> > The DDP checksum is provided to detect errors caused by faulty operation (such as memor
> > data bus errors) within routers on the internet. Implementers of DDP should treat generati
> > the checksum as an optional feature. The 16-bit DDP checksum is computed as follows:
> > CkSum := 0 ;
> > FOR each datagram byte starting with the byte immediately following th
> > Checksum field
> > REPEAT the following algorithm:
> >           CkSum := CkSum + byte; (unsigned addition)
> >           Rotate CkSum left one bit, rotating the most significant bit in
> >                               least significant bit;
> > IF, at the end, CkSum = 0 THEN
> >           CkSum := $FFFF (all ones).
> > Reception of a datagram with CkSum equal to 0 implies that a checksum is not performed.
> 
> 
> Here is the old loop:
> 
> 	while (len--) {
> 		sum += *data;
> 		sum <<=1;
> 		if (sum & 0x10000) {
> 			sum++;
> 			sum &= 0xffff;
> 		}
> 		data++;
> 	}
> 
> My buggy loop is:
> 
> 	while (len--) {
> 		sum += *data++;
> 		sum <<= 1;
> 		sum = ((sum >> 16) + sum) & 0xFFFF;
> 	}
> 
> The problem is the carry from the first addition needs to be dropped
> not folded back (like IP).  
> 
> Corrected fast code is:
> 
> 	while (len--) {
> 		sum += *data++;
> 		sum <<= 1;
> 		sum = (((sum & 0x10000) >> 16) + sum) & 0xffff;
> 	}
> 
> At least it is correct on the standalone random data test, and the
> new code is 30% faster for the cached memory case (13.7 clks/byte vs 18 clks/byte).

Testing...

Re: [IPX]: Fix checksum computation.

[Arnaldo Carvalho de Melo]

Em Fri, Oct 31, 2003 at 11:13:01PM -0200, Arnaldo C. Melo escreveu:
> Em Fri, Oct 31, 2003 at 04:38:43PM -0800, Stephen Hemminger escreveu:
> > 
> > Okay, here is the standard: (Inside Appletalk)
> > 
> > > The DDP checksum is provided to detect errors caused by faulty operation (such as memor
> > > data bus errors) within routers on the internet. Implementers of DDP should treat generati
> > > the checksum as an optional feature. The 16-bit DDP checksum is computed as follows:
> > > CkSum := 0 ;
> > > FOR each datagram byte starting with the byte immediately following th
> > > Checksum field
> > > REPEAT the following algorithm:
> > >           CkSum := CkSum + byte; (unsigned addition)
> > >           Rotate CkSum left one bit, rotating the most significant bit in
> > >                               least significant bit;
> > > IF, at the end, CkSum = 0 THEN
> > >           CkSum := $FFFF (all ones).
> > > Reception of a datagram with CkSum equal to 0 implies that a checksum is not performed.
> > 
> > 
> > Here is the old loop:
> > 
> > 	while (len--) {
> > 		sum += *data;
> > 		sum <<=1;
> > 		if (sum & 0x10000) {
> > 			sum++;
> > 			sum &= 0xffff;
> > 		}
> > 		data++;
> > 	}
> > 
> > My buggy loop is:
> > 
> > 	while (len--) {
> > 		sum += *data++;
> > 		sum <<= 1;
> > 		sum = ((sum >> 16) + sum) & 0xFFFF;
> > 	}
> > 
> > The problem is the carry from the first addition needs to be dropped
> > not folded back (like IP).  
> > 
> > Corrected fast code is:
> > 
> > 	while (len--) {
> > 		sum += *data++;
> > 		sum <<= 1;
> > 		sum = (((sum & 0x10000) >> 16) + sum) & 0xffff;
> > 	}
> > 
> > At least it is correct on the standalone random data test, and the
> > new code is 30% faster for the cached memory case (13.7 clks/byte vs 18 clks/byte).
> 
> Testing...

[root@lolo apple]# md5sum b/kernel-2.4.21-32898cl.i586.rpm kernel-2.4.21-32898cl.i586.rpm
79adde6c4dd97fb214d30009e100a835  b/kernel-2.4.21-32898cl.i586.rpm
79adde6c4dd97fb214d30009e100a835  kernel-2.4.21-32898cl.i586.rpm
[root@lolo apple]#

Perfect, it works as well, but as this is not bugfixing, but an improvement,
I'd say this can well wait for 2.6.1 :-)

Case closed.

- Arnaldo