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

From
Jeff King <hidden>
Date
2016-06-15 22:53:54
Reply to
Martin Fick, 2016-06-15
On Thu, May 24, 2012 at 07:32:36PM -0600, Martin Fick wrote:
quoted
quoted
quoted
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
Thread (33 messages) 33 messages, 5 authors, last reply 2016-06-15
Keyboard shortcuts
hback out one level
jnext message in thread / next series-diff position
kprevious message in thread / previous series-diff position
ldrill in
Escclose help / fold thread tree
?toggle this help