Re: remove_duplicates() in builtin/fetch-pack.c is O(N^2)

From: Jeff King <peff@peff.net>
Date: May 25, 2012, 06:50 UTC
Message-ID: <20120525065038.GA12249@sigill.intra.peff.net>
In-Reply-To: <201205241932.37045.mfick@codeaurora.org>

On Thu, May 24, 2012 at 07:32:36PM -0600, Martin Fick wrote:

Show 17 quoted lines

> > > > Yes, exclusively warm. And all of the refs were
> > We'd have to give some thought to potential race
> > conditions, though. Usually pack-refs isn't modifying
> > the ref, so it can just write out the value to the
> > packed-refs file, then delete the loose ref if nobody
> > has touched it since we wrote. But here we're combining
> > it with a modification, so I suspect there would be a
> > race with another process trying to modify it.
> 
> Yeah, I thought about that.  Could you just right the new 
> packed-ref file with the new refs and the old refs which 
> were in the file already, then just delete any loose refs 
> which were ones which were just added by this operation, 
> only if they have not changed?
> 
> This way, if someone else modifies one of the same refs, 
> they could just win?

I spent a bit of time thinking on this and trying to come up with an exact sequence where we could lose the race, but I don't think we can lose data. Either:

  1. The loose ref is not changed afterwards, and we delete it, making
     our packed version the official one.

  2. The loose ref is changed, and we leave it, which means our packed
     version is not interesting to anybody (the loose version takes
     precedence). We have lost the race, and must consider our write a
     failure.

It's OK to fail in (2); that is no different than the regular loose case. And likewise, it's worth it to look at the other writer.

They might see our packed-refs file in place before we have a chance to modify the loose ref. But that's OK, because they must double-check the existence of the loose ref, and it will still be there. So they will take that as the real value and ignore the packed value.

All of that is more or less the same set of rules that make "git pack-refs" work at all. The only novel situation we are introducing here is that we might be writing a packed-ref without having an existing loose ref at all (whereas usually we would be packing an existing ref, either loose or packed). But I don't think it makes a difference.

I might be wrong, though. In the course of writing this email, I kept thinking "wait, but here's a race", and then when I worked out the details, it was OK. So either I was not clever enough to find a race, or I am not clever enough to realize that there is not one. :)

-Peff