Fix object re-hashing

The hashed object lookup had a subtle bug in re-hashing: it did

	for (i = 0; i < count; i++)
		if (objs[i]) {
			.. rehash ..

where "count" was the old hash couny. Oon the face of it is obvious, since 
it clearly re-hashes all the old objects.

However, it's wrong.

If the last old hash entry before re-hashing was in use (or became in use 
by the re-hashing), then when re-hashing could have inserted an object 
into the hash entries with idx >= count due to overflow. When we then 
rehash the last old entry, that old entry might become empty, which means 
that the overflow entries should be re-hashed again.

In other words, the loop has to be fixed to either traverse the whole 
array, rather than just the old count.

(There's room for a slight optimization: instead of counting all the way 
up, we can break when we see the first empty slot that is above the old 
"count". At that point we know we don't have any collissions that we might 
have to fix up any more. This patch only does the trivial fix)

Signed-off-by: Linus Torvalds <torvalds@osdl.org>
---

I actually didn't see any of this trigger in real life, so maybe my 
analysis is wrong. Junio? Johannes?

diff --git a/object.c b/object.c
index 59e5e36..aeda228 100644
--- a/object.c
+++ b/object.c

@@ -65,7 +65,7 @@ void created_object(const unsigned char 
 		objs = xrealloc(objs, obj_allocs * sizeof(struct object *));
 		memset(objs + count, 0, (obj_allocs - count)
 				* sizeof(struct object *));
-		for (i = 0; i < count; i++)
+		for (i = 0; obj_allocs ; i++)
 			if (objs[i]) {
 				int j = find_object(objs[i]->sha1);
 				if (j != i) {

On Sun, 12 Feb 2006, Linus Torvalds wrote:

I actually didn't see any of this trigger in real life, so maybe my 
analysis is wrong. Junio? Johannes?

Btw, if it does trigger, the behaviour would be that a subsequent object 
lookup will fail, because the last old slot would be NULL, and a few 
entries following it (likely just a couple - never mind that the event 
triggering in the first place is probably fairly rare) wouldn't have 
gotten re-hashed down.

As a result, we'd allocate a new object, and have _two_ "struct object"s 
that describe the same real object. I don't know what would get upset, but 
git-fsck-index certainly would be (one of them would likely be marked 
unreachable, because lookup wouldn't find it, but you might have other 
issues too).

			Linus

On Sun, 12 Feb 2006, Linus Torvalds wrote:

-		for (i = 0; i < count; i++)
+		for (i = 0; obj_allocs ; i++)

GAAH. 

That should obviously be "i < obj_allocs".

That's what I get for editing the patch in-place to remove the optimized 
version that I felt wasn't worth worrying about due to being subtle. So 
instead I sent out a patch that was not-so-subtly obvious crap!

Sorry about that.

		Linus

On Sun, 12 Feb 2006, Linus Torvalds wrote:

That's what I get for editing the patch in-place to remove the optimized 
version that I felt wasn't worth worrying about due to being subtle. So 
instead I sent out a patch that was not-so-subtly obvious crap!

Btw: the reason I edited out the optimization is that it doesn't actually 
matter. Re-hashing the whole thing is a trivial thing, and has basically 
zero overhead in my testing. The costs are all elsewhere now.

		Linus