On Wed, 10 May 2006, Linus Torvalds wrote:

quoted text
> 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.

quoted text
> 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.

quoted text
> 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
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html