Re: Fix object re-hashing

From: Junio C Hamano <junkio@cox.net>
Date: Feb 12, 2006, 19:13 UTC
Message-ID: <7vpsls9yq0.fsf@assigned-by-dhcp.cox.net>
In-Reply-To: <Pine.LNX.4.64.0602121037460.3691@g5.osdl.org>

Linus Torvalds <torvalds@osdl.org> writes:

Show 13 quoted lines

> On Sun, 12 Feb 2006, Junio C Hamano wrote:
>> 
>> This "fix" makes the symptom that me fire two (maybe three)
>> Grrrrr messages earlier this morning disappear.
>
> Goodie. I assume that was the fixed fix, not my original "edit out the 
> useless optimization and then break it totally" fix ;)
>
>> I haven't had my caffeine nor nicotine yet after my short sleep, so I 
>> need to take some time understanding your explanation first, but I am 
>> reasonably sure this must be it (not that I do not trust you, not at all 
>> -- it is that I do not trust *me* applying a patch without understanding 
>> when I have a bug reproducible).

Your explanation finally made sense to me, without caffeine nor nicotine yet, but when I tried to do an illustration.

If the initial obj_allocs were 4 instead of 32, we may have something lie this before rehashing.

slot    value
 0        3
 1        -
 2        -
 3        7

Rehash to double the hash goes like this:

        step1    step2    step3         fixup rehash
       enlarge  rehash   rehash         missing from
        array    "3%8"    "7%8"         the original
 0        3        -        -                -
 1        -        -        -                -
 2        -        -        -                -
 3        7        7        -                3
 4        -        3        3                -
 5        -        -        -                -
 6        -        -        -                -
 7        -        -        7                7

We cannot find "3%8" without the fix.

Thanks for the fix.  Will do an updated "master" soon.