Broken PPC sha1.. (Re: Figured out how to get Mozilla into git)

From: Linus Torvalds <torvalds@osdl.org>
Date: Jun 18, 2006, 22:51 UTC
Message-ID: <Pine.LNX.4.64.0606181543270.5498@g5.osdl.org>
In-Reply-To: <Pine.LNX.4.64.0606181532130.5498@g5.osdl.org>

On Sun, 18 Jun 2006, Linus Torvalds wrote:

Show 14 quoted lines

> 
> On Mon, 19 Jun 2006, Martin Langhoff wrote:
> > 
> > No problems here with my latest import run. fsck-objects --full comes
> > clean, takes 14m:
> >
> > /usr/bin/time git-fsck-objects --full
> > 737.22user 38.79system 14:09.40elapsed 91%CPU (0avgtext+0avgdata 0maxresident)k
> > 0inputs+0outputs (20807major+19483471minor)pagefaults 0swaps
> 
> It takes much less than that for me: 
> 
> 	408.40user 32.56system 7:22.07elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
> 	0inputs+0outputs (145major+13455672minor)pagefaults 0swaps

Ok, re-building the thing with MOZILLA_SHA1=1 rather than my default PPC_SHA1=1 fixes the problem. I no longer get that "SHA1 mismatch with itself" on the pack-file.

Sadly, it also takes a _lot_ longer to fsck.

Paul - I think the ppc SHA1_Update() overflows in 32 bits, when the length of the memory area to be checksummed is huge.

In particular, the pack-file is 535MB in size, and the way we check the SHA1 checksum is by just mapping it all, doing a single SHA1_Update() over the whole pack-file, and comparing the end result with the internal SHA1 at the end of the pack-file.

The PPC SHA1_Update() function starts off with:

	int SHA1_Update(SHA_CTX *c, const void *ptr, unsigned long n)
	{
	...
		c->len += n << 3;

which will obviously overflow if "n" is bigger than 29 bits, ie 512MB.

So doing the length in bits (or whatever that "<<3" is there for) doesn't seem to be such a great idea.

I guess we could make the caller just always chunk it up, but wouldn't it be nice to fix the PPC SHA1 implementation instead?

That said, the _only_ thing this will ever trigger on in practice is exactly this one case: a large packfile whose checksum was _correctly_ generated - because pack-file generation does it in IO chunks using the csum-file interfaces - but that will be incorrectly checked because we check it all at once.

So as bugs go, it's a fairly benign one.

			Linus