Re: [PATCH] fix diff-delta bad memory access

From: Nicolas Pitre <nico@cam.org>
Date: May 10, 2006, 17:27 UTC
Message-ID: <Pine.LNX.4.64.0605101311020.24505@localhost.localdomain>
In-Reply-To: <Pine.LNX.4.64.0605100953090.3718@g5.osdl.org>

On Wed, 10 May 2006, Linus Torvalds wrote:

Show 9 quoted lines

> On Wed, 10 May 2006, Nicolas Pitre wrote:
> >
> > It cannot be assumed that the given buffer will never be moved when 
> > shrinking the allocated memory size with realloc().  So let's ignore 
> > that optimization for now.
> 
> Yeah, that was totally bogus. It would re-allocate _part_ of an 
> allocation, but that allocation contained not just the index, but all the 
> hashes and the hash entries too!

Yep.

> This has nothing to do with moving a buffer - it has everything to do with 
> the fact that you shrunk a buffer that still contained all the other 
> buffers: you shrunk the "mem" allocation to fit just the first part of it, 
> and entirely ignored the "hash" and "entry" parts of it.

No.

The initial allocation assumes a perfectly even distribution of entries in which case the entry array would be all populated.

When there are repeated bytes then consecutive blocks will have the same hash, and in that case keeping only the first one is useful.

Which means that the entry pointer won't get to the end of the allocated space for all entries and I naively assumed that using realloc would only mark the allocated memory as smaller than it originally was without actually copying any of the remaining data, which is what happened in most cases but evidently not always.

But if the buffer moves the hash array containing _pointers_ to hash entries gets totally screwed.

> Btw, I think that whole "allocate everything in one allocation" thing is 
> potentially bogus even the way it is now, if the alignment constraints of 
> "index", "hash" and "entry" are different.

Yeah...  I might just do a separate allocation for hash entries as well.

Or maybe even drop the hash chaining altogether (now that the code does backward matching that might be worth the code simplification).

Nicolas