Re: fix git-pack-redundant crashing sometimes

From: Lukas Sandström <lukass@etek.chalmers.se>
Date: Nov 15, 2005, 23:13 UTC
Message-ID: <437A6B8A.8060905@etek.chalmers.se>
In-Reply-To: <20051115223340.GA3951@steel.home>

Alex Riesen wrote:

Show 36 quoted lines

> Lukas Sandström, Tue, Nov 15, 2005 22:41:34 +0100:
> 
>>>>llist_sorted_difference_inplace didn't handle the match in the first
>>>>sha1 correctly and the lists went wild everywhere.
>>>
>>>This wasn't enough. It never (>5 min on 2.4GHz PIV) finishes on
>>>my local mirror of git, which has 22 packs by now.
>>
>>If the patch I just sent out doesn't fix the problem, and you don't
> 
> 
> Sorry, it doesn't. The code loops here:
> 
> 401             /* find the permutations which contain all missing objects */
> 402             perm_all = perm = get_all_permutations(non_unique);
> 403             while (perm) {
> 404                     if (is_superset(perm->pl, missing)) {
> 405                             new_perm = xmalloc(sizeof(struct pll));
> 406                             new_perm->pl = perm->pl;
> 407                             new_perm->next = perm_ok;
> 408                             perm_ok = new_perm;
> (gdb) 
> 409                     }
> 410                     perm = perm->next;
> 411             }
> 412
> 413             if (perm_ok == NULL)
> 
> 
> 
>>want to debug it yourself, could you please publish the .idx files
>>so I could have a look at them?
> 
> 
> Of course: http://home.arcor.de/fork0/download/idx.tar.gz
>

After giving it a quick look, I don't think it locks up. It is just horribly slow. get_all_permutations returns (nice ASCII-art follows)

    ___n___
    \
     \ ____1____
n! * /  k!(n-k)!
    /______
      k=1

permutations, which for your case (22 packs) adds up to 4194303.

I'll look into an optimization so we won't have to call is_superset for every one of them.

OTOH, I might be wrong and it could very well be an infinite loop. Mind running it over the night? I won't look further into this in 20 hours or so anyway.