From: Lukas Sandström Date: Tue, 15 Nov 2005 23:13:14 GMT Subject: Re: fix git-pack-redundant crashing sometimes Message-ID: <437A6B8A.8060905@etek.chalmers.se> In-Reply-To: <20051115223340.GA3951@steel.home> Alex Riesen wrote: > 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.