another packed-refs race

another packed-refs race

[Jeff King]

I found another race related to the packed-refs code. Consider for a
moment what happens when we are looking at refs and another process does
a simultaneous "git pack-refs --all --prune", updating packed-refs and
deleting the loose refs.

If we are resolving a single ref, then we will either find its loose
form or not. If we do, we're done. If not, we can fall back on what was
in the packed-refs file. If we read the packed-refs file at that point,
we're OK. If the loose ref existed before but was pruned before we could
read it, then we know the packed-refs file is already in place, because
pack-refs would not have deleted the loose ref until it had finished
writing the new file. But imagine that we already loaded the packed-refs
file into memory earlier. We may be looking at an _old_ version of it
that has an irrelevant sha1 from the older packed-refs file. Or it might
not even exist in the packed-refs file at all, and we think the ref does
not resolve.

We could fix this by making sure our packed-refs file is up to date
before using it. E.g., resolving a ref with the following sequence:

  1. Look for loose ref. If found, OK.

  2. Compare inode/size/mtime/etc of on-disk packed-refs to their values
     from the last time we loaded it. If they're not the same, reload
     packed-refs from disk. Otherwise, continue.

  3. Look for ref in in-memory packed-refs.

Not too bad. We introduce one extra stat() for a ref that has been
packed, and the scheme isn't very complicated.

But what about enumerating refs via for_each_ref? It's possible to have
the same problem there, and the packed-refs file may be moved into place
midway through the process of enumerating the loose refs. So we may see
refs/heads/master, but when we get to refs/remotes/origin/master, it has
now been packed and pruned. I _think_ we can get by with:

  1. Generate the complete sorted list of loose refs.

  2. Check that packed-refs is stat-clean, and reload if necessary, as
     above.

  3. Merge the sorted loose and packed lists, letting loose override
     packed (so even if we get repacked halfway through our loose
     traversal and get half of the refs there, it's OK to see duplicates
     in packed-refs, which we will ignore).

This is not very far off of what we do now. Obviously we don't do the
stat-clean check in step 2. But we also don't generate the complete list
of loose refs before hitting the packed-refs file. Instead we lazily
load the loose directories as needed. And of course we cache that
information in memory, even though it may go out of date. I think the
best we could do is keep a stat() for each individual directory we see,
and check it before using the in-memory contents. That may be a lot of
stats, but it's still better than actually opening each loose ref
separately.

So I think it's possible to fix, but I thought you might have some
insight on the simplest way to fit it into the current ref code.

Did I explain the problem well enough to understand? Can you think of
any simpler or better solutions (or is there a case where my proposed
solutions don't work?).

For reference, here's a script that demonstrates the problem during
enumeration (sometimes for-each-ref fails to realize that
refs/heads/master exists at all):

  # run this in one terminal
  git init repo &&
  cd repo &&
  git commit --allow-empty -m foo &&
  base=`git rev-parse HEAD` &&
  while true; do
    # this re-creates the loose ref in .git/refs/heads/master
    git update-ref refs/heads/master $base &&

    # we can remove packed-refs safely, as we know that
    # its only value is now stale. Real git would not do
    # this, but we are simulating the case that "master"
    # simply wasn't included in the last packed-refs file.
    rm -f .git/packed-refs &&

    # and now we repack, which will create an up-to-date
    # packed-refs file, and then delete the loose ref
    git pack-refs --all --prune
  done

  # then simultaneously run this in another
  cd repo &&
  while true; do
    refs=`git for-each-ref`
    echo "==> $refs"
    test -z "$refs" && break
  done

Obviously the "rm -f packed-refs" above is contrived, but it does
simulate a real possible state. You could also do it with a packed-refs
file that has an outdated value for refs/heads/master, and demonstrate
that for-each-ref sees the outdated value.

-Peff

Re: another packed-refs race

[Johan Herland]

On Fri, May 3, 2013 at 10:38 AM, Jeff King <peff@peff.net> wrote:
> I found another race related to the packed-refs code. Consider for a
> moment what happens when we are looking at refs and another process does
> a simultaneous "git pack-refs --all --prune", updating packed-refs and
> deleting the loose refs.
>
> [...]
>
> We could fix this by making sure our packed-refs file is up to date
> before using it. E.g., resolving a ref with the following sequence:
>
>   1. Look for loose ref. If found, OK.
>
>   2. Compare inode/size/mtime/etc of on-disk packed-refs to their values
>      from the last time we loaded it. If they're not the same, reload
>      packed-refs from disk. Otherwise, continue.
>
>   3. Look for ref in in-memory packed-refs.
>
> Not too bad. We introduce one extra stat() for a ref that has been
> packed, and the scheme isn't very complicated.
>
> But what about enumerating refs via for_each_ref? It's possible to have
> the same problem there, and the packed-refs file may be moved into place
> midway through the process of enumerating the loose refs. So we may see
> refs/heads/master, but when we get to refs/remotes/origin/master, it has
> now been packed and pruned. I _think_ we can get by with:
>
>   1. Generate the complete sorted list of loose refs.
>
>   2. Check that packed-refs is stat-clean, and reload if necessary, as
>      above.
>
>   3. Merge the sorted loose and packed lists, letting loose override
>      packed (so even if we get repacked halfway through our loose
>      traversal and get half of the refs there, it's OK to see duplicates
>      in packed-refs, which we will ignore).
>
> This is not very far off of what we do now. Obviously we don't do the
> stat-clean check in step 2. But we also don't generate the complete list
> of loose refs before hitting the packed-refs file. Instead we lazily
> load the loose directories as needed. And of course we cache that
> information in memory, even though it may go out of date. I think the
> best we could do is keep a stat() for each individual directory we see,
> and check it before using the in-memory contents. That may be a lot of
> stats, but it's still better than actually opening each loose ref
> separately.
>
> So I think it's possible to fix, but I thought you might have some
> insight on the simplest way to fit it into the current ref code.
>
> Did I explain the problem well enough to understand? Can you think of
> any simpler or better solutions (or is there a case where my proposed
> solutions don't work?).

You don't really need to be sure that packed-refs is up-to-date. You
only need to make sure that don't rely on lazily loading loose refs
_after_ you have loaded packed-refs.

The following solution might work in both the resolve-a-single-ref and
enumerating-refs case:

0. Look for ref already cached in memory. If found, OK.

1. Look for loose ref. If found, OK.

2. If not found, load all loose refs and packed-refs from disk (in
that order), and store in memory for remainder of this process. Never
reload packed-refs from disk (unless you also reload all loose refs
first).

My rationale for this approach is that if you have a packed-refs file,
you will likely have fewer loose refs, so loading all of them in
addition to the pack-refs file won't be that expensive. (Conversely,
if you do have a lot of loose refs, you're more likely to hit #1, and
not have to load all refs.)

That said, my intuition on the number of loose vs. packed refs, or the
relative cost of reading all loose refs might be off here...


...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net

Re: another packed-refs race

[Jeff King]

On Fri, May 03, 2013 at 11:26:11AM +0200, Johan Herland wrote:

> You don't really need to be sure that packed-refs is up-to-date. You
> only need to make sure that don't rely on lazily loading loose refs
> _after_ you have loaded packed-refs.

True. As long as you load them both together, and always make sure you
do loose first, you'd be fine. But I think there will be corner cases
where you have loaded _part_ of the loose ref namespace. I think part of
the point of Michael's ref work is that if you call "for_each_tag_ref",
we would not waste time loading refs/remotes/ at all. If you then follow
that with a call to "for_each_ref", you would want to re-use the cached
work from traversing refs/tags/, and then traverse refs/remotes/. You
know that your cached packed-refs is good with respect to refs/tags/,
but you don't with respect to refs/remotes.

> The following solution might work in both the resolve-a-single-ref and
> enumerating-refs case:
> 
> 0. Look for ref already cached in memory. If found, OK.
> 
> 1. Look for loose ref. If found, OK.
> 
> 2. If not found, load all loose refs and packed-refs from disk (in
> that order), and store in memory for remainder of this process. Never
> reload packed-refs from disk (unless you also reload all loose refs
> first).

I think that would be correct (modulo that step 1 cannot happen for
enumeration). But we would like to avoid loading all loose refs if we
can. Especially on a cold cache, it can be quite slow, and you may not
even care about those refs for the current operation (I do not recall
the exact original motivation for the lazy loading, but it was something
along those lines).

> My rationale for this approach is that if you have a packed-refs file,
> you will likely have fewer loose refs, so loading all of them in
> addition to the pack-refs file won't be that expensive. (Conversely,
> if you do have a lot of loose refs, you're more likely to hit #1, and
> not have to load all refs.)
> 
> That said, my intuition on the number of loose vs. packed refs, or the
> relative cost of reading all loose refs might be off here...

I don't think that is necessarily true about the number of loose refs.
In a busy repository, you may have many loose refs that have been
updated.

-Peff

Re: another packed-refs race

[Jeff King]

On Fri, May 03, 2013 at 01:28:53PM -0400, Jeff King wrote:

> > The following solution might work in both the resolve-a-single-ref and
> > enumerating-refs case:
> > 
> > 0. Look for ref already cached in memory. If found, OK.
> > 
> > 1. Look for loose ref. If found, OK.
> > 
> > 2. If not found, load all loose refs and packed-refs from disk (in
> > that order), and store in memory for remainder of this process. Never
> > reload packed-refs from disk (unless you also reload all loose refs
> > first).
> 
> I think that would be correct (modulo that step 1 cannot happen for
> enumeration). But we would like to avoid loading all loose refs if we
> can. Especially on a cold cache, it can be quite slow, and you may not
> even care about those refs for the current operation (I do not recall
> the exact original motivation for the lazy loading, but it was something
> along those lines).

Actually, forgetting about enumeration for a minute, that would make
single-ref lookup quite painful. Running "git rev-parse foo" shouldn't
have to even look at most loose refs in the first place. It should be a
couple of open() calls looking for the right spot, and then fall back to
loading packed-refs.

-Peff

Re: another packed-refs race

[Johan Herland]

On Fri, May 3, 2013 at 8:26 PM, Jeff King <peff@peff.net> wrote:
> On Fri, May 03, 2013 at 01:28:53PM -0400, Jeff King wrote:
>> > The following solution might work in both the resolve-a-single-ref and
>> > enumerating-refs case:
>> >
>> > 0. Look for ref already cached in memory. If found, OK.
>> >
>> > 1. Look for loose ref. If found, OK.
>> >
>> > 2. If not found, load all loose refs and packed-refs from disk (in
>> > that order), and store in memory for remainder of this process. Never
>> > reload packed-refs from disk (unless you also reload all loose refs
>> > first).
>>
>> I think that would be correct (modulo that step 1 cannot happen for
>> enumeration). But we would like to avoid loading all loose refs if we
>> can. Especially on a cold cache, it can be quite slow, and you may not
>> even care about those refs for the current operation (I do not recall
>> the exact original motivation for the lazy loading, but it was something
>> along those lines).
>
> Actually, forgetting about enumeration for a minute, that would make
> single-ref lookup quite painful. Running "git rev-parse foo" shouldn't
> have to even look at most loose refs in the first place. It should be a
> couple of open() calls looking for the right spot, and then fall back to
> loading packed-refs.

True. I was overemphasizing the case where we start looking up one
ref, and later look up more refs from the same process (in which case
the load-everything step would be amortized across the other lookups),
but this is probably not the ref access pattern for most Git commands,
and definitely not for "git rev-parse foo". I think your approach is
better.


...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net

Re: another packed-refs race

[Jeff King]

On Fri, May 03, 2013 at 04:38:47AM -0400, Jeff King wrote:

> For reference, here's a script that demonstrates the problem during
> enumeration (sometimes for-each-ref fails to realize that
> refs/heads/master exists at all):
> 
>   # run this in one terminal
>   git init repo &&
>   cd repo &&
>   git commit --allow-empty -m foo &&
>   base=`git rev-parse HEAD` &&
>   while true; do
>     # this re-creates the loose ref in .git/refs/heads/master
>     git update-ref refs/heads/master $base &&

It turns out this is wrong. Git is smart enough not to bother writing
out the loose ref if it isn't changing. So the script as I showed it
actually ends up in a state with _neither_ the packed-refs file nor the
loose ref for an instant.

The correct script looks like this (it just flips between two objects):

  git init -q repo &&
  cd repo &&
  git commit -q --allow-empty -m one &&
  one=`git rev-parse HEAD` &&
  git commit -q --allow-empty -m two &&
  two=`git rev-parse HEAD` &&
  sha1=$one &&
  while true; do
    # this re-creates the loose ref in .git/refs/heads/master
    if test "$sha1" = "$one"; then
      sha1=$two
    else
      sha1=$one
    fi &&
    git update-ref refs/heads/master $sha1 &&

    # we can remove packed-refs safely, as we know that
    # its only value is now stale. Real git would not do
    # this, but we are simulating the case that "master"
    # simply wasn't included in the last packed-refs file.
    rm -f .git/packed-refs &&

    # and now we repack, which will create an up-to-date
    # packed-refs file, and then delete the loose ref
    git pack-refs --all --prune
  done

And a racy lookup check could look like this:

  cd repo &&
  while true; do
    ref=`git rev-parse --verify master`
    echo "==> $ref"
    test -z "$ref" && break
  done

it doesn't know which of the two flipping refs it will get on any given
invocation, but it should never see nothing. It should get one or the
other. With stock git, running these two looks for me simultaneously
typically causes a failure in the second one within about 15 seconds.
The (messy, not ready for application) patch below fixes it (at least I
let it run for 30 minutes without a problem).

The fix is actually two-fold:

  1. Re-load the packed-refs file after each loose object lookup
     failure. This is made more palatable by using stat() to avoid
     re-reading the file in the common case that it wasn't updated.

  2. The loose ref reading itself is actually not atomic. We call
     lstat() on the ref to find out whether it exists (and whether it is
     a symlink). If we get ENOENT, we fall back to finding the loose
     ref.  If it does exist and is a regular file, we proceed to open()
     it. But if the ref gets packed and pruned in the interim, our open
     will fail and we just return NULL to say "oops, I guess it doesn't
     exist". We want the same fallback-to-packed behavior we would get
     if the lstat failed.

     We could potentially do the same when we readlink() a symbolic
     link, but I don't think it is necessary. We do not pack symbolic
     refs, so if readlink gets ENOENT, it's OK to say "nope, the ref
     does not exist".

This doesn't cover the for_each_ref enumeration case at all, which
should still fail.  I'll try to look at that next.

---
diff --git a/refs.c b/refs.c
index de2d8eb..45a7ee6 100644
--- a/refs.c
+++ b/refs.c
@@ -708,6 +708,7 @@ static struct ref_cache {
 	struct ref_cache *next;
 	struct ref_entry *loose;
 	struct ref_entry *packed;
+	struct stat packed_validity;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
@@ -717,6 +718,7 @@ static void clear_packed_ref_cache(struct ref_cache *refs)
 	if (refs->packed) {
 		free_ref_entry(refs->packed);
 		refs->packed = NULL;
+		memset(&refs->packed_validity, 0, sizeof(refs->packed_validity));
 	}
 }
 
@@ -876,19 +878,57 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 	}
 }
 
+/*
+ * Returns 1 if the cached stat information matches the
+ * current state of the file, and 0 otherwise. This should
+ * probably be refactored to share code with ce_match_stat_basic,
+ * which has platform-specific knobs for which fields to respect.
+ */
+static int check_stat_validity(const struct stat *old, const char *fn)
+{
+	static struct stat null;
+	struct stat cur;
+
+	if (stat(fn, &cur))
+		return errno == ENOENT && !memcmp(old, &null, sizeof(null));
+	return cur.st_ino == old->st_ino &&
+	       cur.st_size == old->st_size &&
+	       cur.st_mtime == old->st_mtime;
+}
+
+/*
+ * Call fstat, but zero out the stat structure if for whatever
+ * reason we can't get an answer.
+ */
+static int safe_fstat(int fd, struct stat *out)
+{
+	int r = fstat(fd, out);
+	if (r)
+		memset(out, 0, sizeof(*out));
+	return r;
+}
+
 static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
+	const char *packed_refs_file;
+
+	if (*refs->name)
+		packed_refs_file = git_path_submodule(refs->name, "packed-refs");
+	else
+		packed_refs_file = git_path("packed-refs");
+
+	if (refs->packed &&
+	    !check_stat_validity(&refs->packed_validity, packed_refs_file))
+		clear_packed_ref_cache(refs);
+
 	if (!refs->packed) {
-		const char *packed_refs_file;
 		FILE *f;
 
 		refs->packed = create_dir_entry(refs, "", 0, 0);
-		if (*refs->name)
-			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
-		else
-			packed_refs_file = git_path("packed-refs");
+
 		f = fopen(packed_refs_file, "r");
 		if (f) {
+			safe_fstat(fileno(f), &refs->packed_validity);
 			read_packed_refs(f, get_ref_dir(refs->packed));
 			fclose(f);
 		}
@@ -1108,6 +1148,13 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		git_snpath(path, sizeof(path), "%s", refname);
 
 		if (lstat(path, &st) < 0) {
+			/*
+			 * this lets us reuse this code path
+			 * for later syscall failures; it should
+			 * almost certainly just get factored out into a
+			 * function though
+			 */
+fallback_to_packed:
 			if (errno != ENOENT)
 				return NULL;
 			/*
@@ -1156,7 +1203,7 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		 */
 		fd = open(path, O_RDONLY);
 		if (fd < 0)
-			return NULL;
+			goto fallback_to_packed;
 		len = read_in_full(fd, buffer, sizeof(buffer)-1);
 		close(fd);
 		if (len < 0)

Re: another packed-refs race

[Michael Haggerty]

On 05/03/2013 10:38 AM, Jeff King wrote:
> I found another race related to the packed-refs code. Consider for a
> moment what happens when we are looking at refs and another process does
> a simultaneous "git pack-refs --all --prune", updating packed-refs and
> deleting the loose refs.
> 
> If we are resolving a single ref, then we will either find its loose
> form or not. If we do, we're done. If not, we can fall back on what was
> in the packed-refs file. If we read the packed-refs file at that point,
> we're OK. If the loose ref existed before but was pruned before we could
> read it, then we know the packed-refs file is already in place, because
> pack-refs would not have deleted the loose ref until it had finished
> writing the new file. But imagine that we already loaded the packed-refs
> file into memory earlier. We may be looking at an _old_ version of it
> that has an irrelevant sha1 from the older packed-refs file. Or it might
> not even exist in the packed-refs file at all, and we think the ref does
> not resolve.
>
> We could fix this by making sure our packed-refs file is up to date

s/file/cache/

> before using it. E.g., resolving a ref with the following sequence:
> 
>   1. Look for loose ref. If found, OK.
> 
>   2. Compare inode/size/mtime/etc of on-disk packed-refs to their values
>      from the last time we loaded it. If they're not the same, reload
>      packed-refs from disk. Otherwise, continue.
> 
>   3. Look for ref in in-memory packed-refs.
> 
> Not too bad. We introduce one extra stat() for a ref that has been
> packed, and the scheme isn't very complicated.

Let me think out loud alongside your analysis...

By this mechanism the reader can ensure that it never uses a version of
the packed-refs file that is older than its information that the
corresponding loose ref is absent from the filesystem.

This is all assuming that the filesystem accesses have a defined order;
how is that guaranteed?  pack_refs() and commit_ref() both rely on
commit_lock_file(), which calls

    close(fd) on the lockfile
    rename(lk->filename, result_file)

prune_ref() locks the ref, verifies that its SHA-1 is unchanged, then
calls unlink(), then rollback_lock_file().

The atomicity of rename() guarantees that a reader sees either the old
or the new version of the file in question.  But what guarantees are
there about accesses across two files?  Suppose we start with ref "foo"
that exists only as a loose ref, and we have a pack-refs process doing

    write packed-refs with "foo"
    commit_lock_file() for packed-refs
    read loose ref "foo" and verify that its SHA-1 is unchanged
    unlink() loose ref "foo"

while another process is trying to read the reference:

    look for loose ref "foo"
    read packed-refs

Is there any guarantee that the second process can't see the loose ref
"foo" as being missing but nevertheless read the old version of
packed-refs?  I'm not strong enough on filesystem semantics to answer
that question.

> But what about enumerating refs via for_each_ref? It's possible to have
> the same problem there, and the packed-refs file may be moved into place
> midway through the process of enumerating the loose refs. So we may see
> refs/heads/master, but when we get to refs/remotes/origin/master, it has
> now been packed and pruned.

Yes.

> I _think_ we can get by with:
> 
>   1. Generate the complete sorted list of loose refs.
> 
>   2. Check that packed-refs is stat-clean, and reload if necessary, as
>      above.
> 
>   3. Merge the sorted loose and packed lists, letting loose override
>      packed (so even if we get repacked halfway through our loose
>      traversal and get half of the refs there, it's OK to see duplicates
>      in packed-refs, which we will ignore).
> 
> This is not very far off of what we do now. Obviously we don't do the
> stat-clean check in step 2. But we also don't generate the complete list
> of loose refs before hitting the packed-refs file. Instead we lazily
> load the loose directories as needed. And of course we cache that
> information in memory, even though it may go out of date. I think the
> best we could do is keep a stat() for each individual directory we see,
> and check it before using the in-memory contents. That may be a lot of
> stats, but it's still better than actually opening each loose ref
> separately.

The loose refs cache is only used by the for_each_ref() functions, not
for looking up individual references.  Another approach would be to
change the top-level for_each_ref() functions to re-stat() all of the
loose references within the namespace that interests it, *then* verify
that the packed-ref cache is not stale, *then* start the iteration.
Then there would be no need to re-stat() files during the iteration.
(This would mean that we have to prohibit a second reference iteration
from being started while one is already in progress.)

Of course, clearing (part of) the loose reference cache invalidates any
pointers that other callers might have retained to refnames in the old
version of the cache.  I've never really investigated what callers might
hold onto such pointers under the assumption that they will live to the
end of the process.

Given all of this trouble, there is an obvious question: why do we have
a loose reference cache in the first place?  I think there are a few
reasons:

1. In case one git process has to iterate through the same part of the
reference namespace more than once.  (Does this frequently happen?)

2. Reading a bunch of loose references at the same time is more
efficient than reading them one by one interleaved with other file
reads.  (I think this is a significant win.)

3. Keeping references in a cache means that their refnames have a longer
life, which callers can take advantage of to avoid making their own
copies.  I haven't checked which callers might make this assumption, and
nowhere is the lifetime of such a refname documented so it is not even
clear what callers are *allowed* to assume.  (In my changes I've tried
to stay on the safe side by not reducing any lifetimes.)

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: another packed-refs race

[Michael Haggerty]

On 05/03/2013 07:28 PM, Jeff King wrote:
> On Fri, May 03, 2013 at 11:26:11AM +0200, Johan Herland wrote:
> 
>> You don't really need to be sure that packed-refs is up-to-date. You
>> only need to make sure that don't rely on lazily loading loose refs
>> _after_ you have loaded packed-refs.
> 
> True. As long as you load them both together, and always make sure you
> do loose first, you'd be fine. But I think there will be corner cases
> where you have loaded _part_ of the loose ref namespace. I think part of
> the point of Michael's ref work is that if you call "for_each_tag_ref",
> we would not waste time loading refs/remotes/ at all. If you then follow
> that with a call to "for_each_ref", you would want to re-use the cached
> work from traversing refs/tags/, and then traverse refs/remotes/. You
> know that your cached packed-refs is good with respect to refs/tags/,
> but you don't with respect to refs/remotes.

Correct.

[I wonder if there really are a lot of iterations over overlapping parts
of the reference namespace within a single git process...]

>> The following solution might work in both the resolve-a-single-ref and
>> enumerating-refs case:
>>
>> 0. Look for ref already cached in memory. If found, OK.
>>
>> 1. Look for loose ref. If found, OK.
>>
>> 2. If not found, load all loose refs and packed-refs from disk (in
>> that order), and store in memory for remainder of this process. Never
>> reload packed-refs from disk (unless you also reload all loose refs
>> first).
> 
> I think that would be correct (modulo that step 1 cannot happen for
> enumeration). But we would like to avoid loading all loose refs if we
> can. Especially on a cold cache, it can be quite slow, and you may not
> even care about those refs for the current operation (I do not recall
> the exact original motivation for the lazy loading, but it was something
> along those lines).

Lazy loading was first inspired by the observation that effectively
every git invocation was loading *all* loose references to do an
iteration over refs/replace/ (which I've never even used!)  This was
absolutely killing the performance of filter-branch, which creates a lot
of loose references and invokes git many times--even though the cache
was warm.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: another packed-refs race

[Jeff King]

On Mon, May 06, 2013 at 02:03:40PM +0200, Michael Haggerty wrote:

> > We could fix this by making sure our packed-refs file is up to date
> 
> s/file/cache/

Yeah, I meant "our view of the packed-refs file", but I think "cache"
says that more succinctly. I'll be sure to make it clear when I start
writing real commit messages.

> Let me think out loud alongside your analysis...
> 
> By this mechanism the reader can ensure that it never uses a version of
> the packed-refs file that is older than its information that the
> corresponding loose ref is absent from the filesystem.

Yes, that's a good way of saying it.

> This is all assuming that the filesystem accesses have a defined order;
> how is that guaranteed?  pack_refs() and commit_ref() both rely on
> commit_lock_file(), which calls
> 
>     close(fd) on the lockfile
>     rename(lk->filename, result_file)
> 
> prune_ref() locks the ref, verifies that its SHA-1 is unchanged, then
> calls unlink(), then rollback_lock_file().
> 
> The atomicity of rename() guarantees that a reader sees either the old
> or the new version of the file in question.  But what guarantees are
> there about accesses across two files?

I don't know offhand if any standard makes such guarantees. But there
are other parts of git that do depend on that ordering. For example, I
create a loose object representing commit X. Then I update a ref to
point to X. If the ordering of those operations is not preserved, then a
simultaneous reader would think that the repository is corrupted (the
ref points to a missing object).

I would not be surprised if there are distributed or networked
filesystems for which this property does not hold. But I suspect it does
hold for operations on a single machine with a decent kernel (I would
imagine the VFS layer takes care of this). I am just basing my suspicion
on experimental results (the patch I sent does seem to work on my ext4
system).

> The loose refs cache is only used by the for_each_ref() functions, not
> for looking up individual references.  Another approach would be to
> change the top-level for_each_ref() functions to re-stat() all of the
> loose references within the namespace that interests it, *then* verify
> that the packed-ref cache is not stale, *then* start the iteration.
> Then there would be no need to re-stat() files during the iteration.
> (This would mean that we have to prohibit a second reference iteration
> from being started while one is already in progress.)

Hmm. Thinking on this more, I'm not sure that we need to stat the loose
references at all. We do not need to care if the loose refs are up to
date or not. Well, we might care, but the point here is not to pretend
that we have an up-to-date atomic view of the loose refs; it is only to
make sure that the fallback-to-packed behavior does not lie to us about
the existence or value of a ref.

IOW, it is OK to come up with a value for ref X that was true at the
beginning of the program, even if it has been simultaneously updated.
Our program can operate as if it happened in the instant it started,
even though in real life it takes longer. But it is _not_ OK to miss the
existence of a ref, or to come up with a value that it did not hold at
some point during the program (e.g., it is not OK to return some cruft
we wrote into the packed-refs file when we packed it three weeks ago).

That is a weaker guarantee, and I think we can provide it with:

  1. Load all loose refs into cache for a particular enumeration.

  2. Make sure the packed-refs cache is up-to-date (by checking its
     stat() information and reloading if necessary).

  3. Run the usual iteration over the loose/packed ref caches.

If a loose ref is updated after or during (1), that's OK. The ref
hierarchy is not atomic, so it is possible for us to see a state that
never existed (e.g., we read X, somebody updates X to X' and Y to Y',
then we read Y'; we see X and Y', a state that never existed on disk).
But either the ref was already loose, in which case we always see its
loose value as it was when we read it, or it was previously only packed
(or non-existent), in which case we see get its value from the
packed-refs (or assume it does not exist), which is its state at the
start of our program. If the loose ref is deleted instead of updated,
it's the same thing; we may see it as existing, as it was at the start
of our program.

If the packed-refs file is updated after we have read all of the loose
refs, we may see it "ahead" of the loose refs state we have cached. And
that may mean the packed-refs file even has more up-to-date values. But
we don't have to care, as long as we return some value that was valid
during the course of our program. And we do, either because we have the
loose value cached (in which case it trumps the packed-refs version and
we use it), or it was missing (in which case we will use the updated
pack-refs value, which may not even be the most recent value, but is at
least a value that the ref had to hold at some point during the run of
our program).

I realize my reasoning is a bit hand-wavy there, but I'm not sure how to
express it more formally. But the gist of it is that we would have the
same guarantees under my proposed rule as we would if the loose refs
cache and the packed-refs file did not exist at all. That is, we cannot
read the whole refs hierarchy from the filesystem atomically _anyway_,
so we have to accept that the value we get is only going to be one of
many possible values during the run of our program.

The exception, of course, is when locking a ref for write, but we
perform that read directly from the filesystem once we have the lock.

> Of course, clearing (part of) the loose reference cache invalidates any
> pointers that other callers might have retained to refnames in the old
> version of the cache.  I've never really investigated what callers might
> hold onto such pointers under the assumption that they will live to the
> end of the process.

My proposal above gets rid of the need to invalidate the loose refs
cache, so we can ignore that complexity.

> Given all of this trouble, there is an obvious question: why do we have
> a loose reference cache in the first place?  I think there are a few
> reasons:
> 
> 1. In case one git process has to iterate through the same part of the
> reference namespace more than once.  (Does this frequently happen?)

I'm not sure how often it happens. There are a few obvious candidates if
you "git grep 'for_each[a-z_]*ref'", but I'm not sure if the actual
performance impact is measurable (the cache should be warm after the
first run-through).

> 2. Reading a bunch of loose references at the same time is more
> efficient than reading them one by one interleaved with other file
> reads.  (I think this is a significant win.)

Makes some sense, though I don't recall whether it was ever measured.

> 3. Keeping references in a cache means that their refnames have a longer
> life, which callers can take advantage of to avoid making their own
> copies.  I haven't checked which callers might make this assumption, and
> nowhere is the lifetime of such a refname documented so it is not even
> clear what callers are *allowed* to assume.  (In my changes I've tried
> to stay on the safe side by not reducing any lifetimes.)

Yeah, I'm not sure if this is used or not.

-Peff

Re: another packed-refs race

[Jeff King]

On Mon, May 06, 2013 at 02:12:29PM +0200, Michael Haggerty wrote:

> > I think that would be correct (modulo that step 1 cannot happen for
> > enumeration). But we would like to avoid loading all loose refs if we
> > can. Especially on a cold cache, it can be quite slow, and you may not
> > even care about those refs for the current operation (I do not recall
> > the exact original motivation for the lazy loading, but it was something
> > along those lines).
> 
> Lazy loading was first inspired by the observation that effectively
> every git invocation was loading *all* loose references to do an
> iteration over refs/replace/ (which I've never even used!)  This was
> absolutely killing the performance of filter-branch, which creates a lot
> of loose references and invokes git many times--even though the cache
> was warm.

Yeah, obviously we want to avoid that. I _think_ we can even keep the
lazy loading, as long as keep the ordering as:

  1. Load a chunk of loose refs (whatever we need for the current
     iteration request).

  2. Double-check that our packed-refs cache is up to date, and reload
     if necessary.

  3. Return the results to the caller.

It would perhaps increase latency to getting results to the caller
(since otherwise we can start feeding answers to the caller as we walk
the tree), but should not increase the total amount of work (just the
extra stat() of packed-refs, once per for_each_ref, which is not much).

I'll see if I can cook up a patch.

-Peff

Re: another packed-refs race

[Jeff King]

On Mon, May 06, 2013 at 02:41:22PM -0400, Jeff King wrote:

> That is a weaker guarantee, and I think we can provide it with:
> 
>   1. Load all loose refs into cache for a particular enumeration.
> 
>   2. Make sure the packed-refs cache is up-to-date (by checking its
>      stat() information and reloading if necessary).
> 
>   3. Run the usual iteration over the loose/packed ref caches.

This does seem to work in my experiments. With stock git, I can trigger
the race reliably with:

  # base load, in one terminal, as before
  git init -q repo &&
  cd repo &&
  git commit -q --allow-empty -m one &&
  one=`git rev-parse HEAD` &&
  git commit -q --allow-empty -m two &&
  two=`git rev-parse HEAD` &&
  sha1=$one &&
  while true; do
    # this re-creates the loose ref in .git/refs/heads/master
    if test "$sha1" = "$one"; then
      sha1=$two
    else
      sha1=$one
    fi &&
    git update-ref refs/heads/master $sha1 &&

    # we can remove packed-refs safely, as we know that
    # its only value is now stale. Real git would not do
    # this, but we are simulating the case that "master"
    # simply wasn't included in the last packed-refs file.
    rm -f .git/packed-refs &&

    # and now we repack, which will create an up-to-date
    # packed-refs file, and then delete the loose ref
    git pack-refs --all --prune
  done

  # in another terminal, enumerate and make sure we never miss the ref
  cd repo &&
  while true; do
    refs=`git.compile for-each-ref --format='%(refname)'`
    echo "==> $refs"
    test -z "$refs" && break
  done

It usually takes about 30 seconds to hit a problem, though I measured
failures at up to 90 seconds. With the patch below (on top of the one I
posted the other day, which refreshes the packed-refs cache in
get_packed_refs), it has been running fine for 15 minutes.

The "noop_each_fn" is a little gross. I could also just reimplement the
recursion from do_for_each_ref_in_dir (except we don't care about flags,
trim, base, etc, and would just be calling get_ref_dir recursively).
It's a slight repetition of code, but it would be less subtle than what
I have written below (which uses a no-op callback for the side effect
that it primes the loose ref cache). Which poison do you prefer?

diff --git a/refs.c b/refs.c
index 45a7ee6..59ae7e4 100644
--- a/refs.c
+++ b/refs.c
@@ -1363,19 +1363,38 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	for_each_rawref(warn_if_dangling_symref, &data);
 }
 
+static int noop_each_fn(const char *ref, const unsigned char *sha1, int flags,
+			void *data)
+{
+	return 0;
+}
+
 static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn fn,
 			   int trim, int flags, void *cb_data)
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *packed_dir = get_packed_refs(refs);
-	struct ref_dir *loose_dir = get_loose_refs(refs);
+	struct ref_dir *packed_dir;
+	struct ref_dir *loose_dir;
 	int retval = 0;
 
-	if (base && *base) {
-		packed_dir = find_containing_dir(packed_dir, base, 0);
+	/*
+	 * Prime the loose ref cache; we must make sure the packed ref cache is
+	 * uptodate after we read the loose refs in order to avoid race
+	 * conditions with a simultaneous "pack-refs --prune".
+	 */
+	loose_dir = get_loose_refs(refs);
+	if (base && *base)
 		loose_dir = find_containing_dir(loose_dir, base, 0);
+	if (loose_dir) {
+		sort_ref_dir(loose_dir);
+		do_for_each_ref_in_dir(loose_dir, 0, base, noop_each_fn, 0, 0,
+				       NULL);
 	}
 
+	packed_dir = get_packed_refs(refs);
+	if (base && *base)
+		packed_dir = find_containing_dir(packed_dir, base, 0);
+
 	if (packed_dir && loose_dir) {
 		sort_ref_dir(packed_dir);
 		sort_ref_dir(loose_dir);

[PATCH 0/4] fix packed-refs races

[Jeff King]

This fixes the races I brought up in the surrounding thread:

  http://thread.gmane.org/gmane.comp.version-control.git/223299

The individual races are describe in more detail in each commit, but for
reference, here is the complete reproduction recipe (which I posted
already in several parts throughout the thread, but is collected here):

  # base.sh
  # run this script forever in one terminal
  git init -q repo &&
  cd repo &&
  git commit -q --allow-empty -m one &&
  one=`git rev-parse HEAD` &&
  git commit -q --allow-empty -m two &&
  two=`git rev-parse HEAD` &&
  sha1=$one &&
  while true; do
    # this re-creates the loose ref in .git/refs/heads/master
    if test "$sha1" = "$one"; then
      sha1=$two
    else
      sha1=$one
    fi &&
    git update-ref refs/heads/master $sha1 &&

    # we can remove packed-refs safely, as we know that
    # its only value is now stale. Real git would not do
    # this, but we are simulating the case that "master"
    # simply wasn't included in the last packed-refs file.
    rm -f .git/packed-refs &&

    # and now we repack, which will create an up-to-date
    # packed-refs file, and then delete the loose ref
    git pack-refs --all --prune
  done

  # lookup.sh
  # run this script simultaneously in another terminal; when it exits,
  # git is broken (it erroneously told us that master did not exist).
  # It is fixed by applying up to patch 3/4 below.
  cd repo &&
  while true; do
    ref=`git rev-parse --verify master`
    echo "==> $ref"
    test -z "$ref" && break
  done

  # enumerate.sh
  # run this script simultaneously in another terminal (either with
  # lookup.sh running, too, or just base.sh); when it exits, we
  # for-each-ref has erroneously missed master. It is fixed by applying
  # up to patch 4/4 below.
  cd repo &&
  while true; do
    refs=`git.compile for-each-ref --format='%(refname)'`
    echo "==> $refs"
    test -z "$refs" && break
  done

I don't think is a purely hypothetical race. About once a month for the
past six months or so, I'll run across a corrupted repository on
github.com that is inexplicably missing a few objects near the tip of a
ref. This last time, I happened to catch something very odd in our ref
audit-log. The log for the repo that became corrupted showed a small
push to the tip of "master", but the objects for that push were missing
(the previous ref tip was fine). At almost the exact same time, our
alternates repo was running a "fetch --prune" from the corrupted repo.
But it didn't see the corrupted master ref; it saw that
refs/heads/master didn't exist at all, and it deleted it.

I believe that git-upload-pack hit the enumeration race above, and
showed a ref advertisement in which refs/heads/master was missing[1],
leading fetch to delete the ref. At the same time, a gc was running in
the corrupted repo which hit the same issue, and ended up pruning[2] the
newly pushed objects, which were not referenced from anywhere else.

It may seem unlikely for two programs to hit the race at the same time
(especially given the number of iterations you need to trigger the race
with the scripts above), but I think it's exacerbated when you have a
very large number of refs (because the loose enumeration takes much
longer). So I think there's a good chance this was my problem. And if
not, it is good to fix anyway. :)

  [1/4]: resolve_ref: close race condition for packed refs
  [2/4]: add a stat_validity struct
  [3/4]: get_packed_refs: reload packed-refs file when it changes
  [4/4]: for_each_ref: load all loose refs before packed refs

-Peff

[1] Usually the enumeration race would cause you to see the old value
    from the packed-refs file, not a completely missing ref (unless the
    ref was not packed at all previously, but that is almost certainly
    not the case here). But it does call into resolve_ref to actually
    read the ref, which has its own race that can cause refs to
    "disappear" (and is fixed by patch 1).

    As an aside, I think that calling resolve_ref is probably wrong. We
    know we have a fully qualified refname, because we keep track of
    which directory we are calling readdir() on. But if for whatever
    reason somebody deletes it at the exact moment between when we see
    it in readdir() and when we try to open it (not packs it, but
    actually deletes it), then we'll see it is missing and fall back to
    trying other ref-lookups. So in theory a race with a delete of
    refs/heads/foo could accidentally retrieve the value for
    refs/heads/refs/heads/foo.

    It's quite unlikely, though, and I'm not too concerned about it.

[2] Recently pushed objects should still be safe, even if they are
    unreachable. However, in our case the pruning was exacerbated by a
    gc codepath that could call "git repack -ad" (not in upstream git,
    but we do our own custom gc due to the alternates structure of our
    forks). I've also fixed that, as we should always be using "-A" to
    keep recent unreachable objects.

[PATCH 1/4] resolve_ref: close race condition for packed refs

[Jeff King]

When we attempt to resolve a ref, the first thing we do is
call lstat() to see if it is a symlink or a real ref. If we
find that the ref is missing, we fall back to looking it up
in the packed-refs file. If we find the loose ref does exist
(and is a regular file), we continue with trying to open it.

However, we do not do the same fallback if our open() call
fails; we just report the ref as missing.  A "git pack-refs
--prune" process which is simultaneously running may remove
the loose ref between our lstat() and open().  In this case,
we would erroneously report the ref as missing, even though
we could find it if we checked the packed-refs file.

This patch solves it by factoring out the fallback code from
the lstat() case and calling it from both places. We do not
need to do the same thing for the symlink/readlink code
path, even though it might receive ENOENT, too, because
symlinks cannot be packed (so if it disappears after the
lstat, it is truly being deleted).

Note that this solves only the part of the race within
resolve_ref_unsafe. In the situation described above, we may
still be depending on a cached view of the packed-refs file;
that race will be dealt with in a future patch.

Signed-off-by: Jeff King <peff@peff.net>
---

 refs.c | 63 ++++++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 42 insertions(+), 21 deletions(-)

diff --git a/refs.c b/refs.c
index de2d8eb..5a14703 100644
--- a/refs.c
+++ b/refs.c
@@ -1083,6 +1083,43 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)
 	return -1;
 }
 
+/*
+ * This should be called from resolve_ref_unsafe when a loose ref cannot be
+ * accessed; err must represent the errno from the last attempt to access the
+ * loose ref, and the other options are forwarded from resolve_safe_unsaefe.
+ */
+static const char *handle_loose_ref_failure(int err,
+					    const char *refname,
+					    unsigned char *sha1,
+					    int reading,
+					    int *flag)
+{
+	/*
+	 * If we didn't get ENOENT, something is broken
+	 * with the loose ref, and we should not fallback,
+	 * but instead pretend it doesn't exist.
+	 */
+	if (err != ENOENT)
+		return NULL;
+
+	/*
+	 * The loose reference file does not exist;
+	 * check for a packed reference.
+	 */
+	if (!get_packed_ref(refname, sha1)) {
+		if (flag)
+			*flag |= REF_ISPACKED;
+		return refname;
+	}
+
+	/* The reference is not a packed reference, either. */
+	if (reading)
+		return NULL;
+
+	hashclr(sha1);
+	return refname;
+}
+
 const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int reading, int *flag)
 {
 	int depth = MAXDEPTH;
@@ -1107,26 +1144,9 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 
 		git_snpath(path, sizeof(path), "%s", refname);
 
-		if (lstat(path, &st) < 0) {
-			if (errno != ENOENT)
-				return NULL;
-			/*
-			 * The loose reference file does not exist;
-			 * check for a packed reference.
-			 */
-			if (!get_packed_ref(refname, sha1)) {
-				if (flag)
-					*flag |= REF_ISPACKED;
-				return refname;
-			}
-			/* The reference is not a packed reference, either. */
-			if (reading) {
-				return NULL;
-			} else {
-				hashclr(sha1);
-				return refname;
-			}
-		}
+		if (lstat(path, &st) < 0)
+			return handle_loose_ref_failure(errno, refname, sha1,
+							reading, flag);
 
 		/* Follow "normalized" - ie "refs/.." symlinks by hand */
 		if (S_ISLNK(st.st_mode)) {
@@ -1156,7 +1176,8 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		 */
 		fd = open(path, O_RDONLY);
 		if (fd < 0)
-			return NULL;
+			return handle_loose_ref_failure(errno, refname, sha1,
+							reading, flag);
 		len = read_in_full(fd, buffer, sizeof(buffer)-1);
 		close(fd);
 		if (len < 0)
-- 
1.8.3.rc1.2.g12db477

[PATCH 2/4] add a stat_validity struct

[Jeff King]

It can sometimes be useful to know whether a path in the
filesystem has been updated without going to the work of
opening and re-reading its content. We trust the stat()
information on disk already to handle index updates, and we
can use the same trick here.

This patch introduces a "stat_validity" struct which
encapsulates the concept of checking the stat-freshness of a
file. It is implemented on top of "struct cache_entry" to
reuse the logic about which stat entries to trust for a
particular platform, but hides the complexity behind two
simple functions: check and update.

Signed-off-by: Jeff King <peff@peff.net>
---
This one is prep for the next patch. I'm not super-happy with the way it
builds around cache_entry, just because cache entries may end up
following different rules in the long run. But I at least tried to
encapsulate the grossness, so if it turns out to be a problem, we can
factor out the relevant bits from ce_match_stat_basic into a shared
function.

 cache.h      | 27 +++++++++++++++++++++++++++
 read-cache.c | 31 +++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)

diff --git a/cache.h b/cache.h
index 94ca1ac..adf2874 100644
--- a/cache.h
+++ b/cache.h
@@ -1326,4 +1326,31 @@ int sane_execvp(const char *file, char *const argv[]);
 
 int sane_execvp(const char *file, char *const argv[]);
 
+/*
+ * A struct to encapsulate the concept of whether a file has changed
+ * since we last checked it. This is a simplified version of the up-to-date
+ * checks we use for the index. The implementation is built on an index entry,
+ * but we shield the callers from that ugliness with our struct.
+ */
+struct stat_validity {
+	struct cache_entry *ce;
+};
+
+void stat_validity_clear(struct stat_validity *sv);
+
+/*
+ * Returns 1 if the path matches the saved stat_validity, 0 otherwise.
+ * A missing or inaccessible file is considered a match if the struct was just
+ * initialized, or if the previous update found an inaccessible file.
+ */
+int stat_validity_check(struct stat_validity *sv, const char *path);
+
+/*
+ * Update the stat_validity from a file opened at descriptor fd (if the file
+ * is missing or inaccessible, the validity will reflect that, and future
+ * calls to stat_validity_check will match only if it continues to be
+ * inaccessible).
+ */
+void stat_validity_update(struct stat_validity *sv, int fd);
+
 #endif /* CACHE_H */
diff --git a/read-cache.c b/read-cache.c
index 04ed561..a0bd06c 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1933,3 +1933,34 @@ void *read_blob_data_from_index(struct index_state *istate, const char *path, un
 		*size = sz;
 	return data;
 }
+
+void stat_validity_clear(struct stat_validity *sv)
+{
+	free(sv->ce);
+	sv->ce = NULL;
+}
+
+int stat_validity_check(struct stat_validity *sv, const char *path)
+{
+	struct stat st;
+
+	if (stat(path, &st) < 0)
+		return sv->ce == NULL;
+	if (!sv->ce)
+		return 0;
+	return !ce_match_stat_basic(sv->ce, &st);
+}
+
+void stat_validity_update(struct stat_validity *sv, int fd)
+{
+	struct stat st;
+
+	if (fstat(fd, &st) < 0)
+		stat_validity_clear(sv);
+	else {
+		if (!sv->ce)
+			sv->ce = xcalloc(1, cache_entry_size(0));
+		fill_stat_cache_info(sv->ce, &st);
+		sv->ce->ce_mode = create_ce_mode(st.st_mode);
+	}
+}
-- 
1.8.3.rc1.2.g12db477

[PATCH 3/4] get_packed_refs: reload packed-refs file when it changes

[Jeff King]

Once we read the packed-refs file into memory, we cache it
to save work on future ref lookups. However, our cache may
be out of date with respect to what is on disk if another
process is simultaneously packing the refs. Normally it
is acceptable for us to be a little out of date, since there
is no guarantee whether we read the file before or after the
simultaneous update. However, there is an important special
case: our packed-refs file must be up to date with respect
to any loose refs we read. Otherwise, we risk the following
race condition:

  0. There exists a loose ref refs/heads/master.

  1. Process A starts and looks up the ref "master". It
     first checks $GIT_DIR/master, which does not exist. It
     then loads (and caches) the packed-refs file to see if
     "master" exists in it, which it does not.

  2. Meanwhile, process B runs "pack-refs --all --prune". It
     creates a new packed-refs file which contains
     refs/heads/master, and removes the loose copy at
     $GIT_DIR/refs/heads/master.

  3. Process A continues its lookup, and eventually tries
     $GIT_DIR/refs/heads/master.  It sees that the loose ref
     is missing, and falls back to the packed-refs file. But
     it examines its cached version, which does not have
     refs/heads/master. After trying a few other prefixes,
     it reports master as a non-existent ref.

There are many variants (e.g., step 1 may involve process A
looking up another ref entirely, so even a fully qualified
refname can fail). One of the most interesting ones is if
"refs/heads/master" is already packed. In that case process
A will not see it as missing, but rather will report
whatever value happened to be in the packed-refs file before
process B repacked (which might be an arbitrarily old
value).

We can fix this by making sure we reload the packed-refs
file from disk after looking at any loose refs. That's
unacceptably slow, so we can check it's stat()-validity as a
proxy, and read it only when it appears to have changed.

Reading the packed-refs file after performing any loose-ref
system calls is sufficient because we know the ordering of
the pack-refs process: it always makes sure the newly
written packed-refs file is installed into place before
pruning any loose refs. As long as those operations by B
appear in their executed order to process A, by the time A
sees the missing loose ref, the new packed-refs file must be
in place.

Signed-off-by: Jeff King <peff@peff.net>
---
I hooked the refreshing into get_packed_refs, since then all callers get
it for free. It makes me a little nervous, though, just in case some
caller really cares about calling get_packed_refs but not having the
list of packed-refs change during the call. peel_ref looks like such a
function, but isn't, for reasons I'll explain in a followup patch.

Clone also looks like such a caller, as it calls get_packed_refs once
for each upstream ref it adds (it puts them in the packed-refs list, and
then writes them all out at the end). But it's OK because there is no
packed-refs file for it to refresh from.

An alternative would be to move the refreshing to an explicit
refresh_packed_refs() function, and call it from a few places
(resolve_ref, and later from do_for_each_ref).

 refs.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index 5a14703..6afe8cc 100644
--- a/refs.c
+++ b/refs.c
@@ -708,6 +708,7 @@ static struct ref_cache {
 	struct ref_cache *next;
 	struct ref_entry *loose;
 	struct ref_entry *packed;
+	struct stat_validity packed_validity;
 	/* The submodule name, or "" for the main repo. */
 	char name[FLEX_ARRAY];
 } *ref_cache;
@@ -717,6 +718,7 @@ static void clear_packed_ref_cache(struct ref_cache *refs)
 	if (refs->packed) {
 		free_ref_entry(refs->packed);
 		refs->packed = NULL;
+		stat_validity_clear(&refs->packed_validity);
 	}
 }
 
@@ -878,17 +880,25 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 
 static struct ref_dir *get_packed_refs(struct ref_cache *refs)
 {
+	const char *packed_refs_file;
+
+	if (*refs->name)
+		packed_refs_file = git_path_submodule(refs->name, "packed-refs");
+	else
+		packed_refs_file = git_path("packed-refs");
+
+	if (refs->packed &&
+	    !stat_validity_check(&refs->packed_validity, packed_refs_file))
+		clear_packed_ref_cache(refs);
+
 	if (!refs->packed) {
-		const char *packed_refs_file;
 		FILE *f;
 
 		refs->packed = create_dir_entry(refs, "", 0, 0);
-		if (*refs->name)
-			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
-		else
-			packed_refs_file = git_path("packed-refs");
+
 		f = fopen(packed_refs_file, "r");
 		if (f) {
+			stat_validity_update(&refs->packed_validity, fileno(f));
 			read_packed_refs(f, get_ref_dir(refs->packed));
 			fclose(f);
 		}
-- 
1.8.3.rc1.2.g12db477

[PATCH 4/4] for_each_ref: load all loose refs before packed refs

[Jeff King]

If we are iterating through the refs using for_each_ref (or
any of its sister functions), we can get into a race
condition with a simultaneous "pack-refs --prune" that looks
like this:

  0. We have a large number of loose refs, and a few packed
     refs. refs/heads/z/foo is loose, with no matching entry
     in the packed-refs file.

  1. Process A starts iterating through the refs. It loads
     the packed-refs file from disk, then starts lazily
     traversing through the loose ref directories.

  2. Process B, running "pack-refs --prune", writes out the
     new packed-refs file. It then deletes the newly packed
     refs, including refs/heads/z/foo.

  3. Meanwhile, process A has finally gotten to
     refs/heads/z (it traverses alphabetically). It
     descends, but finds nothing there.  It checks its
     cached view of the packed-refs file, but it does not
     mention anything in "refs/heads/z/" at all (it predates
     the new file written by B in step 2).

The traversal completes successfully without mentioning
refs/heads/z/foo at all (the name, of course, isn't
important; but the more refs you have and the farther down
the alphabetical list a ref is, the more likely it is to hit
the race). If refs/heads/z/foo did exist in the packed refs
file at state 0, we would see an entry for it, but it would
show whatever sha1 the ref had the last time it was packed
(which could be an arbitrarily long time ago).

This can be especially dangerous when process A is "git
prune", as it means our set of reachable tips will be
incomplete, and we may erroneously prune objects reachable
from that tip (the same thing can happen if "repack -ad" is
used, as it simply drops unreachable objects that are
packed).

This patch solves it by loading all of the loose refs for
our traversal into our in-memory cache, and then refreshing
the packed-refs cache. Because a pack-refs writer will
always put the new packed-refs file into place before
starting the prune, we know that any loose refs we fail to
see will either truly be missing, or will have already been
put in the packed-refs file by the time we refresh.

Signed-off-by: Jeff King <peff@peff.net>
---
So this cache-priming is ugly, but I don't think it will have a
performance impact, as it his hitting only directories and
files that we were about to see in a second anyway during
the real traversal. The only difference is that there is a
slight latency before we would start producing any output,
as we read the whole loose refs tree (well, the part we are
interested for this call) before processing any refs.

In theory we could do our lazy walk, and then at the end
double-check that packed-refs had not changed. But if it
does change, we couldn't output any newly found refs, then;
they would be out of sorted order. The only thing we could
do is die().  Which might be OK, and is certainly preferable
to silently dropping a ref and indicating that we processed
the whole list. But I think the latency is probably not that
big a deal.

 refs.c | 38 +++++++++++++++++++++++++++++++++-----
 1 file changed, 33 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index 6afe8cc..c127baf 100644
--- a/refs.c
+++ b/refs.c
@@ -641,6 +641,21 @@ static int do_for_each_ref_in_dirs(struct ref_dir *dir1,
 }
 
 /*
+ * Load all of the refs from the dir into our in-memory cache. The hard work
+ * of loading loose refs is done by get_ref_dir(), so we just need to recurse
+ * through all of the sub-directories. We do not even need to care about
+ * sorting, as traversal order does not matter to us.
+ */
+static void prime_ref_dir(struct ref_dir *dir)
+{
+	int i;
+	for (i = 0; i < dir->nr; i++) {
+		struct ref_entry *entry = dir->entries[i];
+		if (entry->flag & REF_DIR)
+			prime_ref_dir(get_ref_dir(entry));
+	}
+}
+/*
  * Return true iff refname1 and refname2 conflict with each other.
  * Two reference names conflict if one of them exactly matches the
  * leading components of the other; e.g., "foo/bar" conflicts with
@@ -1351,14 +1366,27 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 			   int trim, int flags, void *cb_data)
 {
 	struct ref_cache *refs = get_ref_cache(submodule);
-	struct ref_dir *packed_dir = get_packed_refs(refs);
-	struct ref_dir *loose_dir = get_loose_refs(refs);
+	struct ref_dir *packed_dir;
+	struct ref_dir *loose_dir;
 	int retval = 0;
 
-	if (base && *base) {
-		packed_dir = find_containing_dir(packed_dir, base, 0);
+	/*
+	 * We must make sure that all loose refs are read before accessing the
+	 * packed-refs file; this avoids a race condition in which loose refs
+	 * are migrated to the packed-refs file by a simultaneous process, but
+	 * our in-memory view is from before the migration. get_packed_refs()
+	 * takes care of making sure our view is up to date with what is on
+	 * disk.
+	 */
+	loose_dir = get_loose_refs(refs);
+	if (base && *base)
 		loose_dir = find_containing_dir(loose_dir, base, 0);
-	}
+	if (loose_dir)
+		prime_ref_dir(loose_dir);
+
+	packed_dir = get_packed_refs(refs);
+	if (base && *base)
+		packed_dir = find_containing_dir(packed_dir, base, 0);
 
 	if (packed_dir && loose_dir) {
 		sort_ref_dir(packed_dir);
-- 
1.8.3.rc1.2.g12db477

[PATCH 0/2] peel_ref cleanups changes

[Jeff King]

On Mon, May 06, 2013 at 10:43:13PM -0400, Jeff King wrote:

> I hooked the refreshing into get_packed_refs, since then all callers get
> it for free. It makes me a little nervous, though, just in case some
> caller really cares about calling get_packed_refs but not having the
> list of packed-refs change during the call. peel_ref looks like such a
> function, but isn't, for reasons I'll explain in a followup patch.

I thought I would need the cleanups below for peel_ref, but it turns out
that the middle chunk of the function is never exercised. They conflict
textually with Michael's mh/packed-refs-various topic, so I think it may
make sense to just rebase them on top of that.

  [1/2]: peel_ref: rename "sha1" argument to "peeled"
  [2/2]: peel_ref: refactor for safety with simultaneous update

-Peff

[PATCH 1/2] peel_ref: rename "sha1" argument to "peeled"

[Jeff King]

The "sha1" argument of peel_ref is meant to hold the peeled
object name for output. Let's call it "peeled" which makes
it more clear that it is not an input sha1 (especially as we
will be adding such an input sha1 in the next patch).

Signed-off-by: Jeff King <peff@peff.net>
---
Simple cleanup for the next step.

 refs.c | 8 ++++----
 refs.h | 2 +-
 2 files changed, 5 insertions(+), 5 deletions(-)

diff --git a/refs.c b/refs.c
index de2d8eb..89f8141 100644
--- a/refs.c
+++ b/refs.c
@@ -1231,7 +1231,7 @@ static int filter_refs(const char *refname, const unsigned char *sha1, int flags
 	return filter->fn(refname, sha1, flags, filter->cb_data);
 }
 
-int peel_ref(const char *refname, unsigned char *sha1)
+int peel_ref(const char *refname, unsigned char *peeled)
 {
 	int flag;
 	unsigned char base[20];
@@ -1242,7 +1242,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		if (current_ref->flag & REF_KNOWS_PEELED) {
 			if (is_null_sha1(current_ref->u.value.peeled))
 			    return -1;
-			hashcpy(sha1, current_ref->u.value.peeled);
+			hashcpy(peeled, current_ref->u.value.peeled);
 			return 0;
 		}
 		hashcpy(base, current_ref->u.value.sha1);
@@ -1257,7 +1257,7 @@ int peel_ref(const char *refname, unsigned char *sha1)
 		struct ref_entry *r = find_ref(dir, refname);
 
 		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
-			hashcpy(sha1, r->u.value.peeled);
+			hashcpy(peeled, r->u.value.peeled);
 			return 0;
 		}
 	}
@@ -1274,7 +1274,7 @@ fallback:
 	if (o->type == OBJ_TAG) {
 		o = deref_tag_noverify(o);
 		if (o) {
-			hashcpy(sha1, o->sha1);
+			hashcpy(peeled, o->sha1);
 			return 0;
 		}
 	}
diff --git a/refs.h b/refs.h
index a35eafc..1e8b4e1 100644
--- a/refs.h
+++ b/refs.h
@@ -61,7 +61,7 @@ extern int ref_exists(const char *);
 
 extern int ref_exists(const char *);
 
-extern int peel_ref(const char *refname, unsigned char *sha1);
+extern int peel_ref(const char *refname, unsigned char *peeled);
 
 /** Locks a "refs/" ref returning the lock on success and NULL on failure. **/
 extern struct ref_lock *lock_ref_sha1(const char *refname, const unsigned char *old_sha1);
-- 
1.8.3.rc1.2.g12db477

[PATCH 2/2] peel_ref: refactor for safety with simultaneous update

[Jeff King]

The peel_ref function lets a caller peel an object, taking
advantage of the fact that we may have the peeled value
cached for a packed ref.  However, this function is not
necessarily safe in the face of simultaneous ref updates.

The caller has typically already loaded the ref from disk
(e.g., as part of a for_each_ref enumeration), and therefore
knows what the ref's base sha1 is. But if the asked-for ref
is not the current ref, we will load the ref from disk
ourselves. If another process is simultaneously updating the
ref, we may not get the same sha1 that the caller thinks is
in the ref, and as a result may return a peeled value that
does not match the sha1 that the caller has.

To make this safer, we can have the caller pass in its idea
of the sha1 of the ref, and use that as the base for peeling
(and we can also double-check that it matches the
current_ref pointer when we use that).

This makes the function harder to call (it is not really
"peel this ref", but "peel this object, and by the way, it
is called by this refname"). However, none of the current
callers care, because they always call it from a
for_each_ref enumeration, meaning it is no extra work to
pass in the sha1.

Furthermore, that means that none of the current callers hit
the "read_ref_full" codepath at all (so this bug is not
currently triggerable). They either follow the current_ref
optimization, or if the ref is not packed, they go straight
to the deref_tag fallback.

Let's just rip out the unused code path entirely. Not only
is it not used now, but it would not even make sense to use:
you would get the peeled value of the ref, but you would
have no clue which base object led to that peel.

Signed-off-by: Jeff King <peff@peff.net>
---
So I think peel_ref is buggy as-is (in both master and in
mh/packed-refs-various), it's just not triggerable because of the
dead code path. And it would get buggier again with my other patch
series, as then get_packed_ref could actually re-read the packed-refs
file. But I really think peel_ref is a badly designed function.

You do not peel a ref; you peel an object. You might think it is
convenient to have a function do the ref lookup and the peeling
together, but in practice nobody wants that, because you would not know
what you had just peeled. The real point is to hit the current_ref
optimization. Michael's series already has factored out a peel_object
function with the relevant bits. I think we can simply do away with
peel_ref entirely, and move the current_ref optimization there. I think
it should be perfectly cromulent to do:

  int peel_object(const unsigned char *base, const unsigned char *peeled)
  {
          if (current_ref && current_ref->flag & REF_KNOWS_PEELED &&
              !hashcmp(base, current_ref->u.value.sha1)) {
                  hashcpy(peeled, current_ref->u.value.peeled);
                  return 0;
          }

          /* peel as usual */
  }

That is, we do not need to care that it is _our_ ref that peels to that.
We happen to have a ref whose peeled value we know, and its object
matches the one we want to peel. Whether it is the same ref or not, the
same object sha1 should peel to the same peeled sha1. Of course, in
practice it will be our ref, because that is how the current callers
work. But it is also a safe function for callers who do not know or care
about the optimization.

My original patch on "master" is below for illustration, but do not look
too closely. I think the path I outlined above makes more sense, but I
am not going to work on it tonight.

 builtin/describe.c     |  2 +-
 builtin/pack-objects.c |  4 ++--
 builtin/show-ref.c     |  2 +-
 refs.c                 | 24 ++++--------------------
 refs.h                 |  3 ++-
 upload-pack.c          |  2 +-
 6 files changed, 11 insertions(+), 26 deletions(-)

diff --git a/builtin/describe.c b/builtin/describe.c
index 6636a68..23d7f1a 100644
--- a/builtin/describe.c
+++ b/builtin/describe.c
@@ -150,7 +150,7 @@ static int get_name(const char *path, const unsigned char *sha1, int flag, void
 		return 0;
 
 	/* Is it annotated? */
-	if (!peel_ref(path, peeled)) {
+	if (!peel_ref(path, sha1, peeled)) {
 		is_annotated = !!hashcmp(sha1, peeled);
 	} else {
 		hashcpy(peeled, sha1);
diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index f069462..76352df 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -556,7 +556,7 @@ static int mark_tagged(const char *path, const unsigned char *sha1, int flag,
 
 	if (entry)
 		entry->tagged = 1;
-	if (!peel_ref(path, peeled)) {
+	if (!peel_ref(path, sha1, peeled)) {
 		entry = locate_object_entry(peeled);
 		if (entry)
 			entry->tagged = 1;
@@ -2032,7 +2032,7 @@ static int add_ref_tag(const char *path, const unsigned char *sha1, int flag, vo
 	unsigned char peeled[20];
 
 	if (!prefixcmp(path, "refs/tags/") && /* is a tag? */
-	    !peel_ref(path, peeled)        && /* peelable? */
+	    !peel_ref(path, sha1, peeled)  && /* peelable? */
 	    locate_object_entry(peeled))      /* object packed? */
 		add_object_entry(sha1, OBJ_TAG, NULL, 0);
 	return 0;
diff --git a/builtin/show-ref.c b/builtin/show-ref.c
index 8d9b76a..64f339d 100644
--- a/builtin/show-ref.c
+++ b/builtin/show-ref.c
@@ -78,7 +78,7 @@ match:
 	if (!deref_tags)
 		return 0;
 
-	if (!peel_ref(refname, peeled)) {
+	if (!peel_ref(refname, sha1, peeled)) {
 		hex = find_unique_abbrev(peeled, abbrev);
 		printf("%s %s^{}\n", hex, refname);
 	}
diff --git a/refs.c b/refs.c
index 89f8141..c16bd75 100644
--- a/refs.c
+++ b/refs.c
@@ -1231,38 +1231,22 @@ int peel_ref(const char *refname, unsigned char *peeled)
 	return filter->fn(refname, sha1, flags, filter->cb_data);
 }
 
-int peel_ref(const char *refname, unsigned char *peeled)
+int peel_ref(const char *refname, const unsigned char *base,
+	     unsigned char *peeled)
 {
-	int flag;
-	unsigned char base[20];
 	struct object *o;
 
 	if (current_ref && (current_ref->name == refname
-		|| !strcmp(current_ref->name, refname))) {
+		|| !strcmp(current_ref->name, refname))
+	    && !hashcmp(current_ref->u.value.sha1, base)) {
 		if (current_ref->flag & REF_KNOWS_PEELED) {
 			if (is_null_sha1(current_ref->u.value.peeled))
 			    return -1;
 			hashcpy(peeled, current_ref->u.value.peeled);
 			return 0;
 		}
-		hashcpy(base, current_ref->u.value.sha1);
-		goto fallback;
-	}
-
-	if (read_ref_full(refname, base, 1, &flag))
-		return -1;
-
-	if ((flag & REF_ISPACKED)) {
-		struct ref_dir *dir = get_packed_refs(get_ref_cache(NULL));
-		struct ref_entry *r = find_ref(dir, refname);
-
-		if (r != NULL && r->flag & REF_KNOWS_PEELED) {
-			hashcpy(peeled, r->u.value.peeled);
-			return 0;
-		}
 	}
 
-fallback:
 	o = lookup_unknown_object(base);
 	if (o->type == OBJ_NONE) {
 		int type = sha1_object_info(base, NULL);
diff --git a/refs.h b/refs.h
index 1e8b4e1..39817a4 100644
--- a/refs.h
+++ b/refs.h
@@ -61,7 +61,8 @@ extern int ref_exists(const char *);
 
 extern int ref_exists(const char *);
 
-extern int peel_ref(const char *refname, unsigned char *peeled);
+extern int peel_ref(const char *refname, const unsigned char *base,
+		    unsigned char *peeled);
 
 /** Locks a "refs/" ref returning the lock on success and NULL on failure. **/
 extern struct ref_lock *lock_ref_sha1(const char *refname, const unsigned char *old_sha1);
diff --git a/upload-pack.c b/upload-pack.c
index bfa6279..6acff92 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -755,7 +755,7 @@ static int send_ref(const char *refname, const unsigned char *sha1, int flag, vo
 	else
 		packet_write(1, "%s %s\n", sha1_to_hex(sha1), refname_nons);
 	capabilities = NULL;
-	if (!peel_ref(refname, peeled))
+	if (!peel_ref(refname, sha1, peeled))
 		packet_write(1, "%s %s^{}\n", sha1_to_hex(peeled), refname_nons);
 	return 0;
 }
-- 
1.8.3.rc1.2.g12db477

Re: another packed-refs race

[Michael Haggerty]

On 05/06/2013 08:41 PM, Jeff King wrote:
> On Mon, May 06, 2013 at 02:03:40PM +0200, Michael Haggerty wrote:
> [...]
>> The loose refs cache is only used by the for_each_ref() functions, not
>> for looking up individual references.  Another approach would be to
>> change the top-level for_each_ref() functions to re-stat() all of the
>> loose references within the namespace that interests it, *then* verify
>> that the packed-ref cache is not stale, *then* start the iteration.
>> Then there would be no need to re-stat() files during the iteration.
>> (This would mean that we have to prohibit a second reference iteration
>> from being started while one is already in progress.)
> 
> Hmm. Thinking on this more, I'm not sure that we need to stat the loose
> references at all. We do not need to care if the loose refs are up to
> date or not. Well, we might care, but the point here is not to pretend
> that we have an up-to-date atomic view of the loose refs; it is only to
> make sure that the fallback-to-packed behavior does not lie to us about
> the existence or value of a ref.
> 
> IOW, it is OK to come up with a value for ref X that was true at the
> beginning of the program, even if it has been simultaneously updated.
> Our program can operate as if it happened in the instant it started,
> even though in real life it takes longer. But it is _not_ OK to miss the
> existence of a ref, or to come up with a value that it did not hold at
> some point during the program (e.g., it is not OK to return some cruft
> we wrote into the packed-refs file when we packed it three weeks ago).

This all sounds correct to me.

Another potential problem caused by the non-atomicity of loose reference
reading could be to confuse reachability tests if process 1 is reading
loose references while process 2 is renaming a reference:

1. Process 1 looks for refs/heads/aaaaa and finds it missing.

2. Process 2 renames zzzzz -> aaaaa

3. Process 1 looks for refs/heads/zzzzz and finds it missing.

Process 2 would think that any objects pointed to by aaaaa (formerly
zzzzz) are unreachable.  This would be unfortunate if it is doing an
upload-pack and very bad if it is doing a gc.  I wonder if this could be
a problem in practice?  (Gee, wouldn't it be nice to keep reflogs for
deleted refs? :-) )

> That is a weaker guarantee, and I think we can provide it with:
> 
>   1. Load all loose refs into cache for a particular enumeration.
> 
>   2. Make sure the packed-refs cache is up-to-date (by checking its
>      stat() information and reloading if necessary).
> 
>   3. Run the usual iteration over the loose/packed ref caches.

This sounds reasonable, too, though I'll need some more time to digest
your suggestion in detail.

> [...]
>> Of course, clearing (part of) the loose reference cache invalidates any
>> pointers that other callers might have retained to refnames in the old
>> version of the cache.  I've never really investigated what callers might
>> hold onto such pointers under the assumption that they will live to the
>> end of the process.
> 
> My proposal above gets rid of the need to invalidate the loose refs
> cache, so we can ignore that complexity.

The same concern applies to invalidating the packed-ref cache, which you
still want to do.

>> Given all of this trouble, there is an obvious question: why do we have
>> a loose reference cache in the first place?  I think there are a few
>> reasons:
>>
>> 1. In case one git process has to iterate through the same part of the
>> reference namespace more than once.  (Does this frequently happen?)
> 
> I'm not sure how often it happens. There are a few obvious candidates if
> you "git grep 'for_each[a-z_]*ref'", but I'm not sure if the actual
> performance impact is measurable (the cache should be warm after the
> first run-through).
> 
>> 2. Reading a bunch of loose references at the same time is more
>> efficient than reading them one by one interleaved with other file
>> reads.  (I think this is a significant win.)
> 
> Makes some sense, though I don't recall whether it was ever measured.

I think I measured it once and found it a significant benefit, though I
can't remember whether this was with a warm cache or only with a cold cache.

In fact, I experimented with some other strategies for loose reference
loading for performance reasons.  Currently loose references are read
into the cache lazily, one directory at a time.  I experimented with
changes in both directions:

* Preloading the whole tree of loose references before starting an
iteration.  As I recall, this was a performance *win*.  It was on my
to-do list of things to pursue when I have some free time (ha, ha).  I
mostly wanted to check first that there are not callers who abort the
iteration soon after starting it.  For example, imagine a caller who
tries to determine "are there any tags at all" by iterating over
"refs/tags" with a callback that just returns 1; such a caller would
suffer the cost of reading all of the loose references in "refs/tags".

* Lazy loading loose references one reference at a time.  The ideas was
that this would allow the reference cache to be used for
single-reference lookups.  This change alone caused a significant
performance loss, so it would have had to be combined with code for
preloading directories or subtrees before a for_each_ref() iteration.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: another packed-refs race

[Jeff King]

On Tue, May 07, 2013 at 06:32:12AM +0200, Michael Haggerty wrote:

> Another potential problem caused by the non-atomicity of loose reference
> reading could be to confuse reachability tests if process 1 is reading
> loose references while process 2 is renaming a reference:
> 
> 1. Process 1 looks for refs/heads/aaaaa and finds it missing.
> 
> 2. Process 2 renames zzzzz -> aaaaa
> 
> 3. Process 1 looks for refs/heads/zzzzz and finds it missing.
> 
> Process 2 would think that any objects pointed to by aaaaa (formerly
> zzzzz) are unreachable.  This would be unfortunate if it is doing an
> upload-pack and very bad if it is doing a gc.  I wonder if this could be
> a problem in practice?  (Gee, wouldn't it be nice to keep reflogs for
> deleted refs? :-) )

Ugh. Yeah, that is definitely a possible race, and it could be quite
disastrous for prune.

I am really starting to think that we need a pluggable refs
architecture, and that busy servers can use something like sqlite to
keep the ref storage. That would require bumping repositoryformatversion,
of course, but it would be OK for a server accessible only by git
protocols.

I also wonder if we can spend extra time to get more reliable results
for prune, like checking refs, coming up with a prune list, and then
checking again. I have a feeling it's a 2-generals sort of problem where
we can always miss a ref that keeps bouncing around, but we could bound
the probability. I haven't thought that hard about it. Perhaps this will
give us something to talk about on Thursday. :)

> > My proposal above gets rid of the need to invalidate the loose refs
> > cache, so we can ignore that complexity.
> 
> The same concern applies to invalidating the packed-ref cache, which you
> still want to do.

True. In theory a call to resolve_ref can invalidate it, so any call
from inside a for_each_ref callback would be suspect.

> * Preloading the whole tree of loose references before starting an
> iteration.  As I recall, this was a performance *win*.  It was on my
> to-do list of things to pursue when I have some free time (ha, ha).  I
> mostly wanted to check first that there are not callers who abort the
> iteration soon after starting it.  For example, imagine a caller who
> tries to determine "are there any tags at all" by iterating over
> "refs/tags" with a callback that just returns 1; such a caller would
> suffer the cost of reading all of the loose references in "refs/tags".

Well, you can measure my patches, because that's what they do. :) I
didn't really consider an early termination from the iteration.
Certainly something like:

  git for-each-ref refs/tags | head -1

would take longer. Though if you have that many refs that the latency is
a big problem, you should probably consider packing them (it can't
possibly bite you with a race condition, right?).

-Peff

Re: [PATCH 0/4] fix packed-refs races

[Junio C Hamano]

Thanks.

I queued this, and will push the result out on the side of 'pu'
closer to 'next'. Could you double check the conflict resolution?

I haven't got around to the peel-ref-cleanup yet.

Re: another packed-refs race

[Michael Haggerty]

On 05/07/2013 06:44 AM, Jeff King wrote:
> On Tue, May 07, 2013 at 06:32:12AM +0200, Michael Haggerty wrote:
> 
>> Another potential problem caused by the non-atomicity of loose reference
>> reading could be to confuse reachability tests if process 1 is reading
>> loose references while process 2 is renaming a reference:
>>
>> 1. Process 1 looks for refs/heads/aaaaa and finds it missing.
>>
>> 2. Process 2 renames zzzzz -> aaaaa
>>
>> 3. Process 1 looks for refs/heads/zzzzz and finds it missing.
>>
>> Process 2 would think that any objects pointed to by aaaaa (formerly
>> zzzzz) are unreachable.  This would be unfortunate if it is doing an
>> upload-pack and very bad if it is doing a gc.  I wonder if this could be
>> a problem in practice?  (Gee, wouldn't it be nice to keep reflogs for
>> deleted refs? :-) )
> 
> Ugh. Yeah, that is definitely a possible race, and it could be quite
> disastrous for prune.
> 
> I am really starting to think that we need a pluggable refs
> architecture, and that busy servers can use something like sqlite to
> keep the ref storage. That would require bumping repositoryformatversion,
> of course, but it would be OK for a server accessible only by git
> protocols.

That would be a fun project.  I like the idea of not burdening people's
local mostly-one-user-at-a-time repositories with code that is hardened
against server-level pounding.

> I also wonder if we can spend extra time to get more reliable results
> for prune, like checking refs, coming up with a prune list, and then
> checking again. I have a feeling it's a 2-generals sort of problem where
> we can always miss a ref that keeps bouncing around, but we could bound
> the probability. I haven't thought that hard about it. Perhaps this will
> give us something to talk about on Thursday. :)

It's not 100% solvable without big changes; there could always be a
malign Dijkstra running around your system, renaming references right
before you read them.  But I guess it would be pretty safe if pack would
keep the union of objects reachable from the references read at the
beginning of the run and objects reachable from the references read at
(aka near) the end of the run.

>> * Preloading the whole tree of loose references before starting an
>> iteration.  As I recall, this was a performance *win*.  It was on my
>> to-do list of things to pursue when I have some free time (ha, ha).  I
>> mostly wanted to check first that there are not callers who abort the
>> iteration soon after starting it.  For example, imagine a caller who
>> tries to determine "are there any tags at all" by iterating over
>> "refs/tags" with a callback that just returns 1; such a caller would
>> suffer the cost of reading all of the loose references in "refs/tags".
> 
> Well, you can measure my patches, because that's what they do. :) I
> didn't really consider an early termination from the iteration.
> Certainly something like:
> 
>   git for-each-ref refs/tags | head -1
> 
> would take longer. Though if you have that many refs that the latency is
> a big problem, you should probably consider packing them (it can't
> possibly bite you with a race condition, right?).

No, I don't see a correctness issue.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH 0/4] fix packed-refs races

[Jeff King]

On Mon, May 06, 2013 at 11:40:47PM -0700, Junio C Hamano wrote:

> I queued this, and will push the result out on the side of 'pu'
> closer to 'next'. Could you double check the conflict resolution?

I eyeballed the "--cc" output, as well as the resulting file, and it
looks fine to me.

> I haven't got around to the peel-ref-cleanup yet.

I'd leave that for now; the current code does have a bug, but it's not
triggerable through any of the current callers, so we can afford to take
our time. I'll try to work up a patch that just goes on top of Michael's
series.

-Peff

Re: [PATCH 3/4] get_packed_refs: reload packed-refs file when it changes

[Eric Sunshine]

On Mon, May 6, 2013 at 10:43 PM, Jeff King <peff@peff.net> wrote:
> Once we read the packed-refs file into memory, we cache it
> to save work on future ref lookups. However, our cache may
> be out of date with respect to what is on disk if another
> process is simultaneously packing the refs. Normally it
> is acceptable for us to be a little out of date, since there
> is no guarantee whether we read the file before or after the
> simultaneous update. However, there is an important special
> case: our packed-refs file must be up to date with respect
> to any loose refs we read. Otherwise, we risk the following
> race condition:
>
>   0. There exists a loose ref refs/heads/master.
>
>   1. Process A starts and looks up the ref "master". It
>      first checks $GIT_DIR/master, which does not exist. It
>      then loads (and caches) the packed-refs file to see if
>      "master" exists in it, which it does not.
>
>   2. Meanwhile, process B runs "pack-refs --all --prune". It
>      creates a new packed-refs file which contains
>      refs/heads/master, and removes the loose copy at
>      $GIT_DIR/refs/heads/master.
>
>   3. Process A continues its lookup, and eventually tries
>      $GIT_DIR/refs/heads/master.  It sees that the loose ref
>      is missing, and falls back to the packed-refs file. But
>      it examines its cached version, which does not have
>      refs/heads/master. After trying a few other prefixes,
>      it reports master as a non-existent ref.
>
> There are many variants (e.g., step 1 may involve process A
> looking up another ref entirely, so even a fully qualified
> refname can fail). One of the most interesting ones is if
> "refs/heads/master" is already packed. In that case process
> A will not see it as missing, but rather will report
> whatever value happened to be in the packed-refs file before
> process B repacked (which might be an arbitrarily old
> value).
>
> We can fix this by making sure we reload the packed-refs
> file from disk after looking at any loose refs. That's
> unacceptably slow, so we can check it's stat()-validity as a

s/it's/its/

> proxy, and read it only when it appears to have changed.
>
> Reading the packed-refs file after performing any loose-ref
> system calls is sufficient because we know the ordering of
> the pack-refs process: it always makes sure the newly
> written packed-refs file is installed into place before
> pruning any loose refs. As long as those operations by B
> appear in their executed order to process A, by the time A
> sees the missing loose ref, the new packed-refs file must be
> in place.
>
> Signed-off-by: Jeff King <peff@peff.net>

Re: [PATCH 1/4] resolve_ref: close race condition for packed refs

[Michael Haggerty]

On 05/07/2013 04:38 AM, Jeff King wrote:
> When we attempt to resolve a ref, the first thing we do is
> call lstat() to see if it is a symlink or a real ref. If we
> find that the ref is missing, we fall back to looking it up
> in the packed-refs file. If we find the loose ref does exist
> (and is a regular file), we continue with trying to open it.
> 
> However, we do not do the same fallback if our open() call
> fails; we just report the ref as missing.  A "git pack-refs
> --prune" process which is simultaneously running may remove
> the loose ref between our lstat() and open().  In this case,
> we would erroneously report the ref as missing, even though
> we could find it if we checked the packed-refs file.
> 
> This patch solves it by factoring out the fallback code from
> the lstat() case and calling it from both places. We do not
> need to do the same thing for the symlink/readlink code
> path, even though it might receive ENOENT, too, because
> symlinks cannot be packed (so if it disappears after the
> lstat, it is truly being deleted).
> 
> Note that this solves only the part of the race within
> resolve_ref_unsafe. In the situation described above, we may
> still be depending on a cached view of the packed-refs file;
> that race will be dealt with in a future patch.
> 
> Signed-off-by: Jeff King <peff@peff.net>

+1, with trivial suggestions below.

> ---
> 
>  refs.c | 63 ++++++++++++++++++++++++++++++++++++++++++---------------------
>  1 file changed, 42 insertions(+), 21 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index de2d8eb..5a14703 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -1083,6 +1083,43 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)
>  	return -1;
>  }
>  
> +/*
> + * This should be called from resolve_ref_unsafe when a loose ref cannot be
> + * accessed; err must represent the errno from the last attempt to access the
> + * loose ref, and the other options are forwarded from resolve_safe_unsaefe.

s/resolve_ref_unsaefe/resolve_ref_unsafe/

> + */
> +static const char *handle_loose_ref_failure(int err,
> +					    const char *refname,
> +					    unsigned char *sha1,
> +					    int reading,
> +					    int *flag)
> +{
> +	/*
> +	 * If we didn't get ENOENT, something is broken
> +	 * with the loose ref, and we should not fallback,
> +	 * but instead pretend it doesn't exist.
> +	 */
> +	if (err != ENOENT)
> +		return NULL;
> +
> +	/*
> +	 * The loose reference file does not exist;
> +	 * check for a packed reference.
> +	 */
> +	if (!get_packed_ref(refname, sha1)) {
> +		if (flag)
> +			*flag |= REF_ISPACKED;
> +		return refname;
> +	}
> +
> +	/* The reference is not a packed reference, either. */
> +	if (reading)
> +		return NULL;
> +
> +	hashclr(sha1);
> +	return refname;
> +}
> +
>  const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int reading, int *flag)
>  {
>  	int depth = MAXDEPTH;
> @@ -1107,26 +1144,9 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
>  
>  		git_snpath(path, sizeof(path), "%s", refname);
>  
> -		if (lstat(path, &st) < 0) {
> -			if (errno != ENOENT)
> -				return NULL;
> -			/*
> -			 * The loose reference file does not exist;
> -			 * check for a packed reference.
> -			 */
> -			if (!get_packed_ref(refname, sha1)) {
> -				if (flag)
> -					*flag |= REF_ISPACKED;
> -				return refname;
> -			}
> -			/* The reference is not a packed reference, either. */
> -			if (reading) {
> -				return NULL;
> -			} else {
> -				hashclr(sha1);
> -				return refname;
> -			}
> -		}
> +		if (lstat(path, &st) < 0)
> +			return handle_loose_ref_failure(errno, refname, sha1,
> +							reading, flag);
>  
>  		/* Follow "normalized" - ie "refs/.." symlinks by hand */
>  		if (S_ISLNK(st.st_mode)) {
> @@ -1156,7 +1176,8 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
>  		 */
>  		fd = open(path, O_RDONLY);
>  		if (fd < 0)
> -			return NULL;
> +			return handle_loose_ref_failure(errno, refname, sha1,
> +							reading, flag);

I probably would have separated the rest of the patch, which is a pure
refactoring, from this last chunk, which is a functional change.  But
that's just me.

I suggest adding a comment here mentioning briefly the race condition
that the call to handle_loose_ref_failure() is meant to address;
otherwise somebody not thinking of race conditions might have the clever
idea of "inlining" the call to "return NULL" because it seems redundant
with the check of ENOENT following the lstat() call above.

>  		len = read_in_full(fd, buffer, sizeof(buffer)-1);
>  		close(fd);
>  		if (len < 0)
> 

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH 1/4] resolve_ref: close race condition for packed refs

[Michael Haggerty]

On 05/07/2013 04:38 AM, Jeff King wrote:
> [...]
> This patch solves it by factoring out the fallback code from
> the lstat() case and calling it from both places. We do not
> need to do the same thing for the symlink/readlink code
> path, even though it might receive ENOENT, too, because
> symlinks cannot be packed (so if it disappears after the
> lstat, it is truly being deleted).

To be really pedantic, we should handle all kinds of changes that
another process might make simultaneously:

* symlink -> deleted

  Was already OK, as you explained above.

* regular file -> deleted

  Handled by your patch

* symlink -> regular file

  Could come from

      update-ref --no-deref

  if the old version of the reference were a symlink-based symbolic
  reference.  Oops, wait, that's broken anyway:

      $ ln -sf master .git/refs/heads/foo
      $ git for-each-ref
      4204906e2ee75f9b7224860c40df712d112c004b commit	refs/heads/foo
      4204906e2ee75f9b7224860c40df712d112c004b commit	refs/heads/master
      $ git update-ref --no-deref refs/heads/foo master
      $ dir .git/refs/heads/foo
      lrwxrwxrwx 1 mhagger mhagger 6 May 13 01:07 .git/refs/heads/foo ->
master

  But supposing that were fixed and it occurred between the call to
  lstat() and the call to readlink(), then readlink() would fail with
  errno == EINVAL and we should respond by repeating the code starting
  with the lstat().

* regular file -> symlink

  Could come from overwriting a reference with a symlink-based symbolic
  reference.  But this could only happen if the parallel process were
  an old version of Git

I think it's been quite a while since Git has used symlinks for symbolic
references, so I doubt that it is worth fixing the second two cases.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH 2/4] add a stat_validity struct

[Michael Haggerty]

On 05/07/2013 04:39 AM, Jeff King wrote:
> It can sometimes be useful to know whether a path in the
> filesystem has been updated without going to the work of
> opening and re-reading its content. We trust the stat()
> information on disk already to handle index updates, and we
> can use the same trick here.
> 
> This patch introduces a "stat_validity" struct which
> encapsulates the concept of checking the stat-freshness of a
> file. It is implemented on top of "struct cache_entry" to
> reuse the logic about which stat entries to trust for a
> particular platform, but hides the complexity behind two
> simple functions: check and update.

Given that "struct cache_entry" holds a lot of information that is
irrelevant to stat-freshness and that ce_match_stat_basic() has a lot of
logic that is geared towards cache_entries, it seems like there should
be some kind of "struct stat_data" that holds the portion of the stat
information that we use for checking whether a file might have been
changed between two accesses.  cache_entry would contain a stat_data as
a member, and the functionality for checking that part of a cache_entry
validity would be moved to a separate function.

Then your "struct validity_info" could hold a pointer to a stat_data
rather than to a cache_entry, and it wouldn't have to contain the
unrelated cache_entry stuff.

I'll send patches shortly to show what I mean.

Michael

> Signed-off-by: Jeff King <peff@peff.net>
> ---
> This one is prep for the next patch. I'm not super-happy with the way it
> builds around cache_entry, just because cache entries may end up
> following different rules in the long run. But I at least tried to
> encapsulate the grossness, so if it turns out to be a problem, we can
> factor out the relevant bits from ce_match_stat_basic into a shared
> function.
> 
>  cache.h      | 27 +++++++++++++++++++++++++++
>  read-cache.c | 31 +++++++++++++++++++++++++++++++
>  2 files changed, 58 insertions(+)
> 
> diff --git a/cache.h b/cache.h
> index 94ca1ac..adf2874 100644
> --- a/cache.h
> +++ b/cache.h
> @@ -1326,4 +1326,31 @@ int sane_execvp(const char *file, char *const argv[]);
>  
>  int sane_execvp(const char *file, char *const argv[]);
>  
> +/*
> + * A struct to encapsulate the concept of whether a file has changed
> + * since we last checked it. This is a simplified version of the up-to-date
> + * checks we use for the index. The implementation is built on an index entry,
> + * but we shield the callers from that ugliness with our struct.
> + */
> +struct stat_validity {
> +	struct cache_entry *ce;
> +};
> +
> +void stat_validity_clear(struct stat_validity *sv);
> +
> +/*
> + * Returns 1 if the path matches the saved stat_validity, 0 otherwise.
> + * A missing or inaccessible file is considered a match if the struct was just
> + * initialized, or if the previous update found an inaccessible file.
> + */
> +int stat_validity_check(struct stat_validity *sv, const char *path);
> +
> +/*
> + * Update the stat_validity from a file opened at descriptor fd (if the file
> + * is missing or inaccessible, the validity will reflect that, and future
> + * calls to stat_validity_check will match only if it continues to be
> + * inaccessible).
> + */
> +void stat_validity_update(struct stat_validity *sv, int fd);
> +
>  #endif /* CACHE_H */
> diff --git a/read-cache.c b/read-cache.c
> index 04ed561..a0bd06c 100644
> --- a/read-cache.c
> +++ b/read-cache.c
> @@ -1933,3 +1933,34 @@ void *read_blob_data_from_index(struct index_state *istate, const char *path, un
>  		*size = sz;
>  	return data;
>  }
> +
> +void stat_validity_clear(struct stat_validity *sv)
> +{
> +	free(sv->ce);
> +	sv->ce = NULL;
> +}
> +
> +int stat_validity_check(struct stat_validity *sv, const char *path)
> +{
> +	struct stat st;
> +
> +	if (stat(path, &st) < 0)
> +		return sv->ce == NULL;
> +	if (!sv->ce)
> +		return 0;
> +	return !ce_match_stat_basic(sv->ce, &st);
> +}
> +
> +void stat_validity_update(struct stat_validity *sv, int fd)
> +{
> +	struct stat st;
> +
> +	if (fstat(fd, &st) < 0)
> +		stat_validity_clear(sv);
> +	else {
> +		if (!sv->ce)
> +			sv->ce = xcalloc(1, cache_entry_size(0));
> +		fill_stat_cache_info(sv->ce, &st);
> +		sv->ce->ce_mode = create_ce_mode(st.st_mode);
> +	}
> +}
> 


-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

Re: [PATCH 3/4] get_packed_refs: reload packed-refs file when it changes

[Michael Haggerty]

On 05/07/2013 04:43 AM, Jeff King wrote:
> Once we read the packed-refs file into memory, we cache it
> to save work on future ref lookups. However, our cache may
> be out of date with respect to what is on disk if another
> process is simultaneously packing the refs. Normally it
> is acceptable for us to be a little out of date, since there
> is no guarantee whether we read the file before or after the
> simultaneous update. However, there is an important special
> case: our packed-refs file must be up to date with respect
> to any loose refs we read. Otherwise, we risk the following
> race condition:
> 
>   0. There exists a loose ref refs/heads/master.
> 
>   1. Process A starts and looks up the ref "master". It
>      first checks $GIT_DIR/master, which does not exist. It
>      then loads (and caches) the packed-refs file to see if
>      "master" exists in it, which it does not.
> 
>   2. Meanwhile, process B runs "pack-refs --all --prune". It
>      creates a new packed-refs file which contains
>      refs/heads/master, and removes the loose copy at
>      $GIT_DIR/refs/heads/master.
> 
>   3. Process A continues its lookup, and eventually tries
>      $GIT_DIR/refs/heads/master.  It sees that the loose ref
>      is missing, and falls back to the packed-refs file. But
>      it examines its cached version, which does not have
>      refs/heads/master. After trying a few other prefixes,
>      it reports master as a non-existent ref.
> 
> There are many variants (e.g., step 1 may involve process A
> looking up another ref entirely, so even a fully qualified
> refname can fail). One of the most interesting ones is if
> "refs/heads/master" is already packed. In that case process
> A will not see it as missing, but rather will report
> whatever value happened to be in the packed-refs file before
> process B repacked (which might be an arbitrarily old
> value).
> 
> We can fix this by making sure we reload the packed-refs
> file from disk after looking at any loose refs. That's
> unacceptably slow, so we can check it's stat()-validity as a
> proxy, and read it only when it appears to have changed.
> 
> Reading the packed-refs file after performing any loose-ref
> system calls is sufficient because we know the ordering of
> the pack-refs process: it always makes sure the newly
> written packed-refs file is installed into place before
> pruning any loose refs. As long as those operations by B
> appear in their executed order to process A, by the time A
> sees the missing loose ref, the new packed-refs file must be
> in place.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I hooked the refreshing into get_packed_refs, since then all callers get
> it for free. It makes me a little nervous, though, just in case some
> caller really cares about calling get_packed_refs but not having the
> list of packed-refs change during the call. peel_ref looks like such a
> function, but isn't, for reasons I'll explain in a followup patch.
> 
> Clone also looks like such a caller, as it calls get_packed_refs once
> for each upstream ref it adds (it puts them in the packed-refs list, and
> then writes them all out at the end). But it's OK because there is no
> packed-refs file for it to refresh from.
> 
> An alternative would be to move the refreshing to an explicit
> refresh_packed_refs() function, and call it from a few places
> (resolve_ref, and later from do_for_each_ref).

I think this will be necessary, because otherwise there are too many
places where the packed-refs cache can be invalidated and re-read.

As a test, I changed your stat_validity_check() to return 0 *all* of the
time when a file exists.  I think this simulates a hyperactive
repository in which the packed-refs file changes every time it is
checked.  With this change, hundreds of tests in the test suite fail.

I haven't had time to dig into the failures.  One example is

git-upload-pack: refs.c:542: do_for_each_ref_in_dir: Assertion
`dir->sorted == dir->nr' failed.

This suggests that the packed ref cache was invalidated while somebody
was iterating over it, resulting perhaps in illegal memory references.

Maybe my test is misguided.  But I definitely would not proceed on this
patch until the situation has been understood better.

Michael

>  refs.c | 20 +++++++++++++++-----
>  1 file changed, 15 insertions(+), 5 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index 5a14703..6afe8cc 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -708,6 +708,7 @@ static struct ref_cache {
>  	struct ref_cache *next;
>  	struct ref_entry *loose;
>  	struct ref_entry *packed;
> +	struct stat_validity packed_validity;
>  	/* The submodule name, or "" for the main repo. */
>  	char name[FLEX_ARRAY];
>  } *ref_cache;
> @@ -717,6 +718,7 @@ static void clear_packed_ref_cache(struct ref_cache *refs)
>  	if (refs->packed) {
>  		free_ref_entry(refs->packed);
>  		refs->packed = NULL;
> +		stat_validity_clear(&refs->packed_validity);
>  	}
>  }
>  
> @@ -878,17 +880,25 @@ static struct ref_dir *get_packed_refs(struct ref_cache *refs)
>  
>  static struct ref_dir *get_packed_refs(struct ref_cache *refs)
>  {
> +	const char *packed_refs_file;
> +
> +	if (*refs->name)
> +		packed_refs_file = git_path_submodule(refs->name, "packed-refs");
> +	else
> +		packed_refs_file = git_path("packed-refs");
> +
> +	if (refs->packed &&
> +	    !stat_validity_check(&refs->packed_validity, packed_refs_file))
> +		clear_packed_ref_cache(refs);
> +
>  	if (!refs->packed) {
> -		const char *packed_refs_file;
>  		FILE *f;
>  
>  		refs->packed = create_dir_entry(refs, "", 0, 0);
> -		if (*refs->name)
> -			packed_refs_file = git_path_submodule(refs->name, "packed-refs");
> -		else
> -			packed_refs_file = git_path("packed-refs");
> +
>  		f = fopen(packed_refs_file, "r");
>  		if (f) {
> +			stat_validity_update(&refs->packed_validity, fileno(f));
>  			read_packed_refs(f, get_ref_dir(refs->packed));
>  			fclose(f);
>  		}
> 


-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[RFC 0/2] Separate stat_data from cache_entry

[Michael Haggerty]

This series is a possible replacement for Peff's

    "[PATCH 2/4] add a stat_validity struct"

that doesn't misuse the cache_entry too much in the implementation of
the new functions.  It is only interesting in the context of Peff's
series (or something like it), or if there are other places where
somebody wants to be able to tell whether a file has changed since
it was last checked.

Michael

Michael Haggerty (2):
  Extract a struct stat_data from cache_entry
  add a stat_validity struct

 builtin/ls-files.c |  12 ++--
 cache.h            |  60 +++++++++++++++--
 read-cache.c       | 191 ++++++++++++++++++++++++++++++++++-------------------
 3 files changed, 183 insertions(+), 80 deletions(-)

-- 
1.8.2.2

[RFC 1/2] Extract a struct stat_data from cache_entry

[Michael Haggerty]

This structure will later be used to check the validity of other types
of file.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Feel free to suggest better names.  I tried to follow the convention
of names used nearby.

 builtin/ls-files.c |  12 ++--
 cache.h            |  33 ++++++++---
 read-cache.c       | 161 +++++++++++++++++++++++++++++++----------------------
 3 files changed, 126 insertions(+), 80 deletions(-)

diff --git a/builtin/ls-files.c b/builtin/ls-files.c
index 2202072..6a0730f 100644
--- a/builtin/ls-files.c
+++ b/builtin/ls-files.c
@@ -165,11 +165,13 @@ static void show_ce_entry(const char *tag, struct cache_entry *ce)
 	}
 	write_name(ce->name, ce_namelen(ce));
 	if (debug_mode) {
-		printf("  ctime: %d:%d\n", ce->ce_ctime.sec, ce->ce_ctime.nsec);
-		printf("  mtime: %d:%d\n", ce->ce_mtime.sec, ce->ce_mtime.nsec);
-		printf("  dev: %d\tino: %d\n", ce->ce_dev, ce->ce_ino);
-		printf("  uid: %d\tgid: %d\n", ce->ce_uid, ce->ce_gid);
-		printf("  size: %d\tflags: %x\n", ce->ce_size, ce->ce_flags);
+		struct stat_data *sd = &ce->ce_stat_data;
+
+		printf("  ctime: %d:%d\n", sd->sd_ctime.sec, sd->sd_ctime.nsec);
+		printf("  mtime: %d:%d\n", sd->sd_mtime.sec, sd->sd_mtime.nsec);
+		printf("  dev: %d\tino: %d\n", sd->sd_dev, sd->sd_ino);
+		printf("  uid: %d\tgid: %d\n", sd->sd_uid, sd->sd_gid);
+		printf("  size: %d\tflags: %x\n", sd->sd_size, ce->ce_flags);
 	}
 }
 
diff --git a/cache.h b/cache.h
index 94ca1ac..55b4b14 100644
--- a/cache.h
+++ b/cache.h
@@ -119,15 +119,19 @@ struct cache_time {
 	unsigned int nsec;
 };
 
+struct stat_data {
+	struct cache_time sd_ctime;
+	struct cache_time sd_mtime;
+	unsigned int sd_dev;
+	unsigned int sd_ino;
+	unsigned int sd_uid;
+	unsigned int sd_gid;
+	unsigned int sd_size;
+};
+
 struct cache_entry {
-	struct cache_time ce_ctime;
-	struct cache_time ce_mtime;
-	unsigned int ce_dev;
-	unsigned int ce_ino;
+	struct stat_data ce_stat_data;
 	unsigned int ce_mode;
-	unsigned int ce_uid;
-	unsigned int ce_gid;
-	unsigned int ce_size;
 	unsigned int ce_flags;
 	unsigned int ce_namelen;
 	unsigned char sha1[20];
@@ -509,6 +513,21 @@ extern int limit_pathspec_to_literal(void);
 #define HASH_FORMAT_CHECK 2
 extern int index_fd(unsigned char *sha1, int fd, struct stat *st, enum object_type type, const char *path, unsigned flags);
 extern int index_path(unsigned char *sha1, const char *path, struct stat *st, unsigned flags);
+
+/*
+ * Record to sd the data from st that we use to check whether a file
+ * might have changed.
+ */
+extern void fill_stat_data(struct stat_data *sd, struct stat *st);
+
+/*
+ * Return 0 if st is consistent with a file not having been changed
+ * since sd was filled.  If there are differences, return a
+ * combination of MTIME_CHANGED, CTIME_CHANGED, OWNER_CHANGED,
+ * INODE_CHANGED, and DATA_CHANGED.
+ */
+extern int match_stat_data(struct stat_data *sd, struct stat *st);
+
 extern void fill_stat_cache_info(struct cache_entry *ce, struct stat *st);
 
 #define REFRESH_REALLY		0x0001	/* ignore_valid */
diff --git a/read-cache.c b/read-cache.c
index 04ed561..9c1e089 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -68,21 +68,78 @@ void rename_index_entry_at(struct index_state *istate, int nr, const char *new_n
 }
 
 /*
+ * Record to sd the data from st that we use to check whether a file
+ * might have changed.
+ */
+void fill_stat_data(struct stat_data *sd, struct stat *st)
+{
+	sd->sd_ctime.sec = (unsigned int)st->st_ctime;
+	sd->sd_mtime.sec = (unsigned int)st->st_mtime;
+	sd->sd_ctime.nsec = ST_CTIME_NSEC(*st);
+	sd->sd_mtime.nsec = ST_MTIME_NSEC(*st);
+	sd->sd_dev = st->st_dev;
+	sd->sd_ino = st->st_ino;
+	sd->sd_uid = st->st_uid;
+	sd->sd_gid = st->st_gid;
+	sd->sd_size = st->st_size;
+}
+
+/*
+ * Return 0 if st is consistent with a file not having been changed
+ * since sd was filled.  If there are differences, return a
+ * combination of MTIME_CHANGED, CTIME_CHANGED, OWNER_CHANGED,
+ * INODE_CHANGED, and DATA_CHANGED.
+ */
+int match_stat_data(struct stat_data *sd, struct stat *st)
+{
+	int changed = 0;
+
+	if (sd->sd_mtime.sec != (unsigned int)st->st_mtime)
+		changed |= MTIME_CHANGED;
+	if (trust_ctime && check_stat &&
+	    sd->sd_ctime.sec != (unsigned int)st->st_ctime)
+		changed |= CTIME_CHANGED;
+
+#ifdef USE_NSEC
+	if (check_stat && sd->sd_mtime.nsec != ST_MTIME_NSEC(*st))
+		changed |= MTIME_CHANGED;
+	if (trust_ctime && check_stat &&
+	    sd->sd_ctime.nsec != ST_CTIME_NSEC(*st))
+		changed |= CTIME_CHANGED;
+#endif
+
+	if (check_stat) {
+		if (sd->sd_uid != (unsigned int) st->st_uid ||
+			sd->sd_gid != (unsigned int) st->st_gid)
+			changed |= OWNER_CHANGED;
+		if (sd->sd_ino != (unsigned int) st->st_ino)
+			changed |= INODE_CHANGED;
+	}
+
+#ifdef USE_STDEV
+	/*
+	 * st_dev breaks on network filesystems where different
+	 * clients will have different views of what "device"
+	 * the filesystem is on
+	 */
+	if (check_stat && sd->sd_dev != (unsigned int) st->st_dev)
+			changed |= INODE_CHANGED;
+#endif
+
+	if (sd->sd_size != (unsigned int) st->st_size)
+		changed |= DATA_CHANGED;
+
+	return changed;
+}
+
+/*
  * This only updates the "non-critical" parts of the directory
  * cache, ie the parts that aren't tracked by GIT, and only used
  * to validate the cache.
  */
 void fill_stat_cache_info(struct cache_entry *ce, struct stat *st)
 {
-	ce->ce_ctime.sec = (unsigned int)st->st_ctime;
-	ce->ce_mtime.sec = (unsigned int)st->st_mtime;
-	ce->ce_ctime.nsec = ST_CTIME_NSEC(*st);
-	ce->ce_mtime.nsec = ST_MTIME_NSEC(*st);
-	ce->ce_dev = st->st_dev;
-	ce->ce_ino = st->st_ino;
-	ce->ce_uid = st->st_uid;
-	ce->ce_gid = st->st_gid;
-	ce->ce_size = st->st_size;
+	fill_stat_data(&ce->ce_stat_data, st);
 
 	if (assume_unchanged)
 		ce->ce_flags |= CE_VALID;
@@ -195,43 +252,11 @@ static int ce_match_stat_basic(struct cache_entry *ce, struct stat *st)
 	default:
 		die("internal error: ce_mode is %o", ce->ce_mode);
 	}
-	if (ce->ce_mtime.sec != (unsigned int)st->st_mtime)
-		changed |= MTIME_CHANGED;
-	if (trust_ctime && check_stat &&
-	    ce->ce_ctime.sec != (unsigned int)st->st_ctime)
-		changed |= CTIME_CHANGED;
-
-#ifdef USE_NSEC
-	if (check_stat && ce->ce_mtime.nsec != ST_MTIME_NSEC(*st))
-		changed |= MTIME_CHANGED;
-	if (trust_ctime && check_stat &&
-	    ce->ce_ctime.nsec != ST_CTIME_NSEC(*st))
-		changed |= CTIME_CHANGED;
-#endif
 
-	if (check_stat) {
-		if (ce->ce_uid != (unsigned int) st->st_uid ||
-			ce->ce_gid != (unsigned int) st->st_gid)
-			changed |= OWNER_CHANGED;
-		if (ce->ce_ino != (unsigned int) st->st_ino)
-			changed |= INODE_CHANGED;
-	}
-
-#ifdef USE_STDEV
-	/*
-	 * st_dev breaks on network filesystems where different
-	 * clients will have different views of what "device"
-	 * the filesystem is on
-	 */
-	if (check_stat && ce->ce_dev != (unsigned int) st->st_dev)
-			changed |= INODE_CHANGED;
-#endif
-
-	if (ce->ce_size != (unsigned int) st->st_size)
-		changed |= DATA_CHANGED;
+	changed |= match_stat_data(&ce->ce_stat_data, st);
 
 	/* Racily smudged entry? */
-	if (!ce->ce_size) {
+	if (!ce->ce_stat_data.sd_size) {
 		if (!is_empty_blob_sha1(ce->sha1))
 			changed |= DATA_CHANGED;
 	}
@@ -245,11 +270,11 @@ static int is_racy_timestamp(const struct index_state *istate, struct cache_entr
 		istate->timestamp.sec &&
 #ifdef USE_NSEC
 		 /* nanosecond timestamped files can also be racy! */
-		(istate->timestamp.sec < ce->ce_mtime.sec ||
-		 (istate->timestamp.sec == ce->ce_mtime.sec &&
-		  istate->timestamp.nsec <= ce->ce_mtime.nsec))
+		(istate->timestamp.sec < ce->ce_stat_data.sd_mtime.sec ||
+		 (istate->timestamp.sec == ce->ce_stat_data.sd_mtime.sec &&
+		  istate->timestamp.nsec <= ce->ce_stat_data.sd_mtime.nsec))
 #else
-		istate->timestamp.sec <= ce->ce_mtime.sec
+		istate->timestamp.sec <= ce->ce_stat_data.sd_mtime.sec
 #endif
 		 );
 }
@@ -340,7 +365,7 @@ int ie_modified(const struct index_state *istate,
 	 * then we know it is.
 	 */
 	if ((changed & DATA_CHANGED) &&
-	    (S_ISGITLINK(ce->ce_mode) || ce->ce_size != 0))
+	    (S_ISGITLINK(ce->ce_mode) || ce->ce_stat_data.sd_size != 0))
 		return changed;
 
 	changed_fs = ce_modified_check_fs(ce, st);
@@ -1322,16 +1347,16 @@ static struct cache_entry *cache_entry_from_ondisk(struct ondisk_cache_entry *on
 {
 	struct cache_entry *ce = xmalloc(cache_entry_size(len));
 
-	ce->ce_ctime.sec = ntoh_l(ondisk->ctime.sec);
-	ce->ce_mtime.sec = ntoh_l(ondisk->mtime.sec);
-	ce->ce_ctime.nsec = ntoh_l(ondisk->ctime.nsec);
-	ce->ce_mtime.nsec = ntoh_l(ondisk->mtime.nsec);
-	ce->ce_dev   = ntoh_l(ondisk->dev);
-	ce->ce_ino   = ntoh_l(ondisk->ino);
+	ce->ce_stat_data.sd_ctime.sec = ntoh_l(ondisk->ctime.sec);
+	ce->ce_stat_data.sd_mtime.sec = ntoh_l(ondisk->mtime.sec);
+	ce->ce_stat_data.sd_ctime.nsec = ntoh_l(ondisk->ctime.nsec);
+	ce->ce_stat_data.sd_mtime.nsec = ntoh_l(ondisk->mtime.nsec);
+	ce->ce_stat_data.sd_dev   = ntoh_l(ondisk->dev);
+	ce->ce_stat_data.sd_ino   = ntoh_l(ondisk->ino);
 	ce->ce_mode  = ntoh_l(ondisk->mode);
-	ce->ce_uid   = ntoh_l(ondisk->uid);
-	ce->ce_gid   = ntoh_l(ondisk->gid);
-	ce->ce_size  = ntoh_l(ondisk->size);
+	ce->ce_stat_data.sd_uid   = ntoh_l(ondisk->uid);
+	ce->ce_stat_data.sd_gid   = ntoh_l(ondisk->gid);
+	ce->ce_stat_data.sd_size  = ntoh_l(ondisk->size);
 	ce->ce_flags = flags & ~CE_NAMEMASK;
 	ce->ce_namelen = len;
 	hashcpy(ce->sha1, ondisk->sha1);
@@ -1608,7 +1633,7 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)
 	 * The only thing we care about in this function is to smudge the
 	 * falsely clean entry due to touch-update-touch race, so we leave
 	 * everything else as they are.  We are called for entries whose
-	 * ce_mtime match the index file mtime.
+	 * ce_stat_data.sd_mtime match the index file mtime.
 	 *
 	 * Note that this actually does not do much for gitlinks, for
 	 * which ce_match_stat_basic() always goes to the actual
@@ -1647,7 +1672,7 @@ static void ce_smudge_racily_clean_entry(struct cache_entry *ce)
 		 * file, and never calls us, so the cached size information
 		 * for "frotz" stays 6 which does not match the filesystem.
 		 */
-		ce->ce_size = 0;
+		ce->ce_stat_data.sd_size = 0;
 	}
 }
 
@@ -1657,16 +1682,16 @@ static char *copy_cache_entry_to_ondisk(struct ondisk_cache_entry *ondisk,
 {
 	short flags;
 
-	ondisk->ctime.sec = htonl(ce->ce_ctime.sec);
-	ondisk->mtime.sec = htonl(ce->ce_mtime.sec);
-	ondisk->ctime.nsec = htonl(ce->ce_ctime.nsec);
-	ondisk->mtime.nsec = htonl(ce->ce_mtime.nsec);
-	ondisk->dev  = htonl(ce->ce_dev);
-	ondisk->ino  = htonl(ce->ce_ino);
+	ondisk->ctime.sec = htonl(ce->ce_stat_data.sd_ctime.sec);
+	ondisk->mtime.sec = htonl(ce->ce_stat_data.sd_mtime.sec);
+	ondisk->ctime.nsec = htonl(ce->ce_stat_data.sd_ctime.nsec);
+	ondisk->mtime.nsec = htonl(ce->ce_stat_data.sd_mtime.nsec);
+	ondisk->dev  = htonl(ce->ce_stat_data.sd_dev);
+	ondisk->ino  = htonl(ce->ce_stat_data.sd_ino);
 	ondisk->mode = htonl(ce->ce_mode);
-	ondisk->uid  = htonl(ce->ce_uid);
-	ondisk->gid  = htonl(ce->ce_gid);
-	ondisk->size = htonl(ce->ce_size);
+	ondisk->uid  = htonl(ce->ce_stat_data.sd_uid);
+	ondisk->gid  = htonl(ce->ce_stat_data.sd_gid);
+	ondisk->size = htonl(ce->ce_stat_data.sd_size);
 	hashcpy(ondisk->sha1, ce->sha1);
 
 	flags = ce->ce_flags;
-- 
1.8.2.2

[RFC 2/2] add a stat_validity struct

[Michael Haggerty]

It can sometimes be useful to know whether a path in the
filesystem has been updated without going to the work of
opening and re-reading its content. We trust the stat()
information on disk already to handle index updates, and we
can use the same trick here.

This patch introduces a "stat_validity" struct which
encapsulates the concept of checking the stat-freshness of a
file. It is implemented on top of "struct stat_data" to
reuse the logic about which stat entries to trust for a
particular platform, but hides the complexity behind two
simple functions: check and update.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
This is essentially the same as Peff's patch

    "[PATCH 2/4] add a stat_validity struct"

except that it uses the "struct stat_data" from the previous commit
rather than grabbing the fields directly out of cache_entry.

 cache.h      | 27 +++++++++++++++++++++++++++
 read-cache.c | 30 ++++++++++++++++++++++++++++++
 2 files changed, 57 insertions(+)

diff --git a/cache.h b/cache.h
index 55b4b14..71385dc 100644
--- a/cache.h
+++ b/cache.h
@@ -1345,4 +1345,31 @@ int checkout_fast_forward(const unsigned char *from,
 
 int sane_execvp(const char *file, char *const argv[]);
 
+/*
+ * A struct to encapsulate the concept of whether a file has changed
+ * since we last checked it. This uses criteria similar to those used
+ * for the index.
+ */
+struct stat_validity {
+	struct stat_data *sd;
+};
+
+void stat_validity_clear(struct stat_validity *sv);
+
+/*
+ * Returns 1 if the path is a regular file (or a symlink to a regular
+ * file) and matches the saved stat_validity, 0 otherwise.  A missing
+ * or inaccessible file is considered a match if the struct was just
+ * initialized, or if the previous update found an inaccessible file.
+ */
+int stat_validity_check(struct stat_validity *sv, const char *path);
+
+/*
+ * Update the stat_validity from a file opened at descriptor fd. If
+ * the file is missing, inaccessible, or not a regular file, then
+ * future calls to stat_validity_check will match iff one of those
+ * conditions continues to be true.
+ */
+void stat_validity_update(struct stat_validity *sv, int fd);
+
 #endif /* CACHE_H */
diff --git a/read-cache.c b/read-cache.c
index 9c1e089..9dd157f 100644
--- a/read-cache.c
+++ b/read-cache.c
@@ -1958,3 +1958,33 @@ void *read_blob_data_from_index(struct index_state *istate, const char *path, un
 		*size = sz;
 	return data;
 }
+
+void stat_validity_clear(struct stat_validity *sv)
+{
+	free(sv->sd);
+	sv->sd = NULL;
+}
+
+int stat_validity_check(struct stat_validity *sv, const char *path)
+{
+	struct stat st;
+
+	if (stat(path, &st) < 0)
+		return sv->sd == NULL;
+	if (!sv->sd)
+		return 0;
+	return S_ISREG(st.st_mode) && !match_stat_data(sv->sd, &st);
+}
+
+void stat_validity_update(struct stat_validity *sv, int fd)
+{
+	struct stat st;
+
+	if (fstat(fd, &st) < 0 || !S_ISREG(st.st_mode))
+		stat_validity_clear(sv);
+	else {
+		if (!sv->sd)
+			sv->sd = xcalloc(1, sizeof(struct stat_data));
+		fill_stat_data(sv->sd, &st);
+	}
+}
-- 
1.8.2.2

Re: [RFC 0/2] Separate stat_data from cache_entry

[Junio C Hamano]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> Michael Haggerty (2):
>   Extract a struct stat_data from cache_entry
>   add a stat_validity struct

Some indentation glitches carried over from the original in that
"from-ondisk" function were distracting while reading it through,
but I think these show us a reasonable direction to go, if we want
to have "We have read that file and already know what it says.  Do
we have to read it again?" check for files that are not tracked
working tree files.

Re: [PATCH 1/4] resolve_ref: close race condition for packed refs

[Jeff King]

On Mon, May 13, 2013 at 12:56:05AM +0200, Michael Haggerty wrote:

> > + * This should be called from resolve_ref_unsafe when a loose ref cannot be
> > + * accessed; err must represent the errno from the last attempt to access the
> > + * loose ref, and the other options are forwarded from resolve_safe_unsaefe.
> 
> s/resolve_ref_unsaefe/resolve_ref_unsafe/

Oops, thanks.

> > -			return NULL;
> > +			return handle_loose_ref_failure(errno, refname, sha1,
> > +							reading, flag);
> 
> I probably would have separated the rest of the patch, which is a pure
> refactoring, from this last chunk, which is a functional change.  But
> that's just me.

Yeah, I go back and forth on whether it is better to have strict
refactors followed by changes or not. Sometimes it is hard to understand
the motivation for the refactor without seeing the change, and you end
up explaining it twice.

My usual rule of thumb is:

  - If you are factoring out some code, and then are going to change
    that code, make it two separate changes. That keeps the diffs
    readable (the first one is pure movement and you do not need to look
    closely, and the second shows a sane diff of the change).

  - If you are factoring out some code, and then adding more callers,
    it's OK to do it together. The new caller provides the motivation
    for the refactor.

This is the latter case. But I'm open to arguments that the rule is not
a good one. :)

> I suggest adding a comment here mentioning briefly the race condition
> that the call to handle_loose_ref_failure() is meant to address;
> otherwise somebody not thinking of race conditions might have the clever
> idea of "inlining" the call to "return NULL" because it seems redundant
> with the check of ENOENT following the lstat() call above.

Yeah, I thought I had mentioned that at the top of
handle_loose_ref_failure, but I see that I didn't. Probably something
like this squashed on top makes sense:

diff --git a/refs.c b/refs.c
index c127baf..1a7e4ef 100644
--- a/refs.c
+++ b/refs.c
@@ -1111,7 +1111,7 @@ static int get_packed_ref(const char *refname, unsigned char *sha1)
 /*
  * This should be called from resolve_ref_unsafe when a loose ref cannot be
  * accessed; err must represent the errno from the last attempt to access the
- * loose ref, and the other options are forwarded from resolve_safe_unsaefe.
+ * loose ref, and the other options are forwarded from resolve_safe_unsafe.
  */
 static const char *handle_loose_ref_failure(int err,
 					    const char *refname,
@@ -1200,9 +1200,16 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		 * a ref
 		 */
 		fd = open(path, O_RDONLY);
-		if (fd < 0)
+		if (fd < 0) {
+			/*
+			 * We need to check again here for ENOENT and fall back
+			 * to the packed-refs file to avoid a race condition in
+			 * which the ref is packed and pruned between our
+			 * lstat() and open() calls.
+			 */
 			return handle_loose_ref_failure(errno, refname, sha1,
 							reading, flag);
+		}
 		len = read_in_full(fd, buffer, sizeof(buffer)-1);
 		close(fd);
 		if (len < 0)

Re: [PATCH 2/4] add a stat_validity struct

[Jeff King]

On Mon, May 13, 2013 at 04:29:34AM +0200, Michael Haggerty wrote:

> > This patch introduces a "stat_validity" struct which
> > encapsulates the concept of checking the stat-freshness of a
> > file. It is implemented on top of "struct cache_entry" to
> > reuse the logic about which stat entries to trust for a
> > particular platform, but hides the complexity behind two
> > simple functions: check and update.
> 
> Given that "struct cache_entry" holds a lot of information that is
> irrelevant to stat-freshness and that ce_match_stat_basic() has a lot of
> logic that is geared towards cache_entries, it seems like there should
> be some kind of "struct stat_data" that holds the portion of the stat
> information that we use for checking whether a file might have been
> changed between two accesses.  cache_entry would contain a stat_data as
> a member, and the functionality for checking that part of a cache_entry
> validity would be moved to a separate function.
> 
> Then your "struct validity_info" could hold a pointer to a stat_data
> rather than to a cache_entry, and it wouldn't have to contain the
> unrelated cache_entry stuff.

Yes, I had the exact same thought, and came up with the exact same
solution. I was just hesitant to do it because it meant touching all of
the cache_entry users to adjust their struct accesses.

But from your patches, it doesn't look too bad (and we can be sure we
updated every spot, because it's easy for the compiler to enforce).

I'm sorry to be so slow lately; I'm on vacation (and will be for a bit
yet). I'm happy to rebuild my series on top of yours, and it looks like
it is still only in pu (I haven't yet read "What's Cooking" to see the
plans for it). I don't think there's a rush, as it is post-1.8.3 anyway
(I _do_ think it's a serious bug, in that it can cause data loss, but in
practice I doubt most people would hit it).

-Peff

Re: [PATCH 1/4] resolve_ref: close race condition for packed refs

[Michael Haggerty]

On 05/16/2013 05:47 AM, Jeff King wrote:
>> I probably would have separated the rest of the patch, which is a pure
>> refactoring, from this last chunk, which is a functional change.  But
>> that's just me.
> 
> Yeah, I go back and forth on whether it is better to have strict
> refactors followed by changes or not. Sometimes it is hard to understand
> the motivation for the refactor without seeing the change, and you end
> up explaining it twice.

A pure refactoring doesn't need much justification.  Something like
"extract function foo()" plus maybe "this function will soon have
multiple callers" is IMO usually adequate, especially if the function is
well-named and documented in the patch itself.

> My usual rule of thumb is:
> 
>   - If you are factoring out some code, and then are going to change
>     that code, make it two separate changes. That keeps the diffs
>     readable (the first one is pure movement and you do not need to look
>     closely, and the second shows a sane diff of the change).
> 
>   - If you are factoring out some code, and then adding more callers,
>     it's OK to do it together. The new caller provides the motivation
>     for the refactor.
> 
> This is the latter case. But I'm open to arguments that the rule is not
> a good one. :)

Yes, I see how keeping the changes together makes the justification of
the refactoring more obvious.  On the other hand, splitting has the
following benefits:

1. Reviewers have a single thing to check in each patch: "Did he
   transcribe the code correctly into a function and choose a good
   API?" vs. "Does it make sense to call the function from this new
   place?"  The threads of feedback emails about each patch are
   similarly separated.

   On the other hand, of course these two changes are not completely
   independent, because having an idea what new callers want to do
   with the function affects what its API should be.

2. If the patch series needs to be revised, it is quite possible that
   the revisions affect only one patch or the other.  Therefore, the
   unaffected patch can be carried along through interactive rebases
   etc. intact, or might serve as a building block for an alternative
   solution.

3. If there's a problem, bisect can figure out which half of the change
   was to blame.

That being said, this case is very much in the gray area where it is a
matter of personal preference and I don't mind at all if you leave it as
a single patch.

Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/

[PATCH 0/4] Fix a race condition when reading loose refs

[Michael Haggerty]

This patch series is inspired by the first patch [1] in a series by
Peff and solves the race condition that he discovered plus a second,
similar race.  The general problem is that loose ref files are read in
two steps: lstat() followed by readlink() or open().  If another
process changes the file between our two steps, then the old code gets
confused and can give incorrect results.  The new code detects if an
error reported by readlink()/open() is inconsistent with the results
of the previous lstat(), and if so, tries anew.

The first three commits are just preparatory.  All four commits could
easily be squashed together if it is preferred (especially commits 2
through 4), but I did it this way to separate the
code-churning-but-trivial changes from the functional changes to make
review easier.

[1] http://article.gmane.org/gmane.comp.version-control.git/223525

Michael Haggerty (4):
  resolve_ref_unsafe(): extract function handle_missing_loose_ref()
  resolve_ref_unsafe(): handle the case of an SHA-1 within loop
  resolve_ref_unsafe(): nest reference-reading code in an infinite loop
  resolve_ref_unsafe(): close race condition reading loose refs

 refs.c | 187 ++++++++++++++++++++++++++++++++++++++++-------------------------
 1 file changed, 114 insertions(+), 73 deletions(-)

-- 
1.8.3

[PATCH 1/4] resolve_ref_unsafe(): extract function handle_missing_loose_ref()

[Michael Haggerty]

The nesting was getting a bit out of hand, and it's about to get
worse.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c | 55 ++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 34 insertions(+), 21 deletions(-)

diff --git a/refs.c b/refs.c
index d17931a..1acce17 100644
--- a/refs.c
+++ b/refs.c
@@ -1193,6 +1193,37 @@ static struct ref_entry *get_packed_ref(const char *refname)
 	return find_ref(get_packed_refs(&ref_cache), refname);
 }
 
+/*
+ * A loose ref file doesn't exist; check for a packed ref.  The
+ * options are forwarded from resolve_safe_unsafe().
+ */
+static const char *handle_missing_loose_ref(const char *refname,
+					    unsigned char *sha1,
+					    int reading,
+					    int *flag)
+{
+	struct ref_entry *entry;
+
+	/*
+	 * The loose reference file does not exist; check for a packed
+	 * reference.
+	 */
+	entry = get_packed_ref(refname);
+	if (entry) {
+		hashcpy(sha1, entry->u.value.sha1);
+		if (flag)
+			*flag |= REF_ISPACKED;
+		return refname;
+	}
+	/* The reference is not a packed reference, either. */
+	if (reading) {
+		return NULL;
+	} else {
+		hashclr(sha1);
+		return refname;
+	}
+}
+
 const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int reading, int *flag)
 {
 	int depth = MAXDEPTH;
@@ -1218,28 +1249,10 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		git_snpath(path, sizeof(path), "%s", refname);
 
 		if (lstat(path, &st) < 0) {
-			struct ref_entry *entry;
-
-			if (errno != ENOENT)
+			if (errno == ENOENT)
+				return handle_missing_loose_ref(refname, sha1, reading, flag);
+			else
 				return NULL;
-			/*
-			 * The loose reference file does not exist;
-			 * check for a packed reference.
-			 */
-			entry = get_packed_ref(refname);
-			if (entry) {
-				hashcpy(sha1, entry->u.value.sha1);
-				if (flag)
-					*flag |= REF_ISPACKED;
-				return refname;
-			}
-			/* The reference is not a packed reference, either. */
-			if (reading) {
-				return NULL;
-			} else {
-				hashclr(sha1);
-				return refname;
-			}
 		}
 
 		/* Follow "normalized" - ie "refs/.." symlinks by hand */
-- 
1.8.3

[PATCH 2/4] resolve_ref_unsafe(): handle the case of an SHA-1 within loop

[Michael Haggerty]

There is only one "break" statement within the loop, which jumps to
the code after the loop that handles the case of a file that holds a
SHA-1.  So move that code from below the loop into the if statement
where the break was previously located.  This makes the logic flow
more local and also opens the way for nesting the checking code in
an inner loop.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c | 22 +++++++++++++---------
 1 file changed, 13 insertions(+), 9 deletions(-)

diff --git a/refs.c b/refs.c
index 1acce17..2722f75 100644
--- a/refs.c
+++ b/refs.c
@@ -1295,8 +1295,19 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		/*
 		 * Is it a symbolic ref?
 		 */
-		if (prefixcmp(buffer, "ref:"))
-			break;
+		if (prefixcmp(buffer, "ref:")) {
+			/*
+			 * Please note that FETCH_HEAD has a second
+			 * line containing other data.
+			 */
+			if (get_sha1_hex(buffer, sha1) ||
+			    (buffer[40] != '\0' && !isspace(buffer[40]))) {
+				if (flag)
+					*flag |= REF_ISBROKEN;
+				return NULL;
+			}
+			return refname;
+		}
 		if (flag)
 			*flag |= REF_ISSYMREF;
 		buf = buffer + 4;
@@ -1309,13 +1320,6 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 		}
 		refname = strcpy(refname_buffer, buf);
 	}
-	/* Please note that FETCH_HEAD has a second line containing other data. */
-	if (get_sha1_hex(buffer, sha1) || (buffer[40] != '\0' && !isspace(buffer[40]))) {
-		if (flag)
-			*flag |= REF_ISBROKEN;
-		return NULL;
-	}
-	return refname;
 }
 
 char *resolve_refdup(const char *ref, unsigned char *sha1, int reading, int *flag)
-- 
1.8.3

[PATCH 3/4] resolve_ref_unsafe(): nest reference-reading code in an infinite loop

[Michael Haggerty]

The last statement of the loop body is "break", so this doesn't change
the logical flow...yet.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
This commit is 98% whitespace changes, so do it in a separate commit
to make the changes in the next commit more obvious.

 refs.c | 123 ++++++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 64 insertions(+), 59 deletions(-)

diff --git a/refs.c b/refs.c
index 2722f75..7a77d76 100644
--- a/refs.c
+++ b/refs.c
@@ -1248,77 +1248,82 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 
 		git_snpath(path, sizeof(path), "%s", refname);
 
-		if (lstat(path, &st) < 0) {
-			if (errno == ENOENT)
-				return handle_missing_loose_ref(refname, sha1, reading, flag);
-			else
-				return NULL;
-		}
+		for (;;) {
+			if (lstat(path, &st) < 0) {
+				if (errno == ENOENT)
+					return handle_missing_loose_ref(
+							refname, sha1,
+							reading, flag);
+				else
+					return NULL;
+			}
 
-		/* Follow "normalized" - ie "refs/.." symlinks by hand */
-		if (S_ISLNK(st.st_mode)) {
-			len = readlink(path, buffer, sizeof(buffer)-1);
-			if (len < 0)
-				return NULL;
-			buffer[len] = 0;
-			if (!prefixcmp(buffer, "refs/") &&
-					!check_refname_format(buffer, 0)) {
-				strcpy(refname_buffer, buffer);
-				refname = refname_buffer;
-				if (flag)
-					*flag |= REF_ISSYMREF;
-				continue;
+			/* Follow "normalized" - ie "refs/.." symlinks by hand */
+			if (S_ISLNK(st.st_mode)) {
+				len = readlink(path, buffer, sizeof(buffer)-1);
+				if (len < 0)
+					return NULL;
+				buffer[len] = 0;
+				if (!prefixcmp(buffer, "refs/") &&
+				    !check_refname_format(buffer, 0)) {
+					strcpy(refname_buffer, buffer);
+					refname = refname_buffer;
+					if (flag)
+						*flag |= REF_ISSYMREF;
+					break;
+				}
 			}
-		}
 
-		/* Is it a directory? */
-		if (S_ISDIR(st.st_mode)) {
-			errno = EISDIR;
-			return NULL;
-		}
+			/* Is it a directory? */
+			if (S_ISDIR(st.st_mode)) {
+				errno = EISDIR;
+				return NULL;
+			}
 
-		/*
-		 * Anything else, just open it and try to use it as
-		 * a ref
-		 */
-		fd = open(path, O_RDONLY);
-		if (fd < 0)
-			return NULL;
-		len = read_in_full(fd, buffer, sizeof(buffer)-1);
-		close(fd);
-		if (len < 0)
-			return NULL;
-		while (len && isspace(buffer[len-1]))
-			len--;
-		buffer[len] = '\0';
+			/*
+			 * Anything else, just open it and try to use it as
+			 * a ref
+			 */
+			fd = open(path, O_RDONLY);
+			if (fd < 0)
+				return NULL;
+			len = read_in_full(fd, buffer, sizeof(buffer)-1);
+			close(fd);
+			if (len < 0)
+				return NULL;
+			while (len && isspace(buffer[len-1]))
+				len--;
+			buffer[len] = '\0';
 
-		/*
-		 * Is it a symbolic ref?
-		 */
-		if (prefixcmp(buffer, "ref:")) {
 			/*
-			 * Please note that FETCH_HEAD has a second
-			 * line containing other data.
+			 * Is it a symbolic ref?
 			 */
-			if (get_sha1_hex(buffer, sha1) ||
-			    (buffer[40] != '\0' && !isspace(buffer[40]))) {
+			if (prefixcmp(buffer, "ref:")) {
+				/*
+				 * Please note that FETCH_HEAD has a second
+				 * line containing other data.
+				 */
+				if (get_sha1_hex(buffer, sha1) ||
+				    (buffer[40] != '\0' && !isspace(buffer[40]))) {
+					if (flag)
+						*flag |= REF_ISBROKEN;
+					return NULL;
+				}
+				return refname;
+			}
+			if (flag)
+				*flag |= REF_ISSYMREF;
+			buf = buffer + 4;
+			while (isspace(*buf))
+				buf++;
+			if (check_refname_format(buf, REFNAME_ALLOW_ONELEVEL)) {
 				if (flag)
 					*flag |= REF_ISBROKEN;
 				return NULL;
 			}
-			return refname;
-		}
-		if (flag)
-			*flag |= REF_ISSYMREF;
-		buf = buffer + 4;
-		while (isspace(*buf))
-			buf++;
-		if (check_refname_format(buf, REFNAME_ALLOW_ONELEVEL)) {
-			if (flag)
-				*flag |= REF_ISBROKEN;
-			return NULL;
+			refname = strcpy(refname_buffer, buf);
+			break;
 		}
-		refname = strcpy(refname_buffer, buf);
 	}
 }
 
-- 
1.8.3

[PATCH 4/4] resolve_ref_unsafe(): close race condition reading loose refs

[Michael Haggerty]

We read loose references in two steps.  The code is roughly:

    lstat()
    if error ENOENT:
        loose ref is missing; look for corresponding packed ref
    else if S_ISLNK:
        readlink()
        if error:
            report failure
    else if S_ISDIR:
        report failure
    else
        open()
        if error:
            report failure
        read()

The problem is that the first filesystem call, to lstat(), is not
atomic with the second filesystem call, to readlink() or open().
Therefore it is possible for another process to change the file
between our two calls, for example:

* If the other process deletes the file, our second call will fail
  with ENOENT, which we *should* interpret as "loose ref is missing;
  look for corresponding packed ref".  This can arise if the other
  process is pack-refs; it might have just written a new packed-refs
  file containing the old contents of the reference then deleted the
  loose ref.

* If the other process changes a symlink into a plain file, our call
  to readlink() will fail with EINVAL, which we *should* respond to by
  trying to open() and read() the file.

The old code treats the reference as missing in both of these cases,
which is incorrect.

So instead, wrap the above code in a loop.  If the result of
readline()/open() is a failure that is inconsistent with the result of
the previous lstat(), then just loop again starting with a fresh call
to lstat().

One race is still possible and undetected: another process could
change the file from a regular file into a symlink between the call to
lstat and the call to open().  The open() call would silently follow
the symlink and not know that something is wrong.  I don't see a way
to detect this situation without the use of the O_NOFOLLOW option,
which is not portable and is not used elsewhere in our code base.

However, we don't use symlinks anymore, so this situation is unlikely.
And it doesn't appear that treating a symlink as a regular file would
have grave consequences; after all, this is exactly how the code
handles non-relative symlinks.

Note that this solves only the part of the race within
resolve_ref_unsafe. In the situation described above, we may still be
depending on a cached view of the packed-refs file; that race will be
dealt with in a future patch.

This problem was reported and diagnosed by Jeff King <peff@peff.net>,
and this solution is derived from his patch.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Please note that if there is some bizarre filesystem somewhere for
which, for a single, static file

    lstat() reports S_ISLNK and readlink() fails with ENOENT or EINVAL

or

    lstat() reports neither S_ISLNK nor S_ISDIR and open() fails with ENOENT

then the inner loop would never terminate.  I can't imagine this
happening, but if somebody is worried about it the solution is simple:
limit the inner loop to 3 iterations or so.

Another obvious way to solve the problem would be to skip the lstat()
call altogether, and to rely on errno to distinguish the cases:

    readlink()
    if error ENOENT:
        loose ref is missing; look for corresponding packed ref
    else if error EINVAL:
        must not be a symlink; fall through to open()
    else if other error:
        report failure
    else:
        handle as symlink

    open()
    if error ENOENT:
        file must have been deleted since readlink(); look for packed ref
    else if other error:
        report failure
    else:
        read() and handle file contents

There is still a gap between readlink() and open(), during which the
file could have been changed from a regular file into a symlink, so
the remaining race mentioned above would still be undetected.  I don't
see a strong reason to prefer the looping code in this patch vs. the
no-lstat() alternative so I took the variant that was closer to the
old code.

 refs.c | 27 +++++++++++++++++++++++----
 1 file changed, 23 insertions(+), 4 deletions(-)

diff --git a/refs.c b/refs.c
index 7a77d76..6e7c1fd 100644
--- a/refs.c
+++ b/refs.c
@@ -1248,6 +1248,15 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 
 		git_snpath(path, sizeof(path), "%s", refname);
 
+		/*
+		 * This loop is to avoid race conditions.  First we
+		 * lstat() the file, then we try to read it as a link
+		 * or as a file.  But if somebody changes the type of
+		 * the file (file <-> directory <-> symlink) between
+		 * the lstat() and reading, then we don't want to
+		 * report that as an error but rather try again
+		 * starting with the lstat().
+		 */
 		for (;;) {
 			if (lstat(path, &st) < 0) {
 				if (errno == ENOENT)
@@ -1261,8 +1270,13 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 			/* Follow "normalized" - ie "refs/.." symlinks by hand */
 			if (S_ISLNK(st.st_mode)) {
 				len = readlink(path, buffer, sizeof(buffer)-1);
-				if (len < 0)
-					return NULL;
+				if (len < 0) {
+					if (errno == ENOENT || errno == EINVAL)
+						/* inconsistent with lstat; retry */
+						continue;
+					else
+						return NULL;
+				}
 				buffer[len] = 0;
 				if (!prefixcmp(buffer, "refs/") &&
 				    !check_refname_format(buffer, 0)) {
@@ -1285,8 +1299,13 @@ const char *resolve_ref_unsafe(const char *refname, unsigned char *sha1, int rea
 			 * a ref
 			 */
 			fd = open(path, O_RDONLY);
-			if (fd < 0)
-				return NULL;
+			if (fd < 0) {
+				if (errno == ENOENT)
+					/* inconsistent with lstat; retry */
+					continue;
+				else
+					return NULL;
+			}
 			len = read_in_full(fd, buffer, sizeof(buffer)-1);
 			close(fd);
 			if (len < 0)
-- 
1.8.3

Re: [PATCH 0/4] Fix a race condition when reading loose refs

[Junio C Hamano]

I've read the series while on a bus and found all of them sensible.
I do share the worry of retry storm you expressed in the last one,
and I agree that giving up after N times is a reasonable way out,
when it becomes necessary.

Thanks.

Re: [PATCH 4/4] resolve_ref_unsafe(): close race condition reading loose refs

[Jeff King]

On Tue, Jun 11, 2013 at 04:26:20PM +0200, Michael Haggerty wrote:

> Please note that if there is some bizarre filesystem somewhere for
> which, for a single, static file
> 
>     lstat() reports S_ISLNK and readlink() fails with ENOENT or EINVAL
> [...]
> then the inner loop would never terminate.

Yeah, I had the exact same thought while reading your description above.
I think we can call that "too crazy to worry about", and deal with it if
it ever actually comes up.

Overall your series looks correct to me. The use of the extra "for(;;)"
and its control flow feels a little tortured to me.  Would it be
simpler to just do:

  stat_ref:
          if (lstat(...) < 0)
            ...
          if (readlink(...) < 0)
                  if (errno == ENOENT || errno == EINVAL)
                          /* inconsistent with lstat; retry */
                          goto stat_ref;

          if (open(...) < 0)
                  if (errno == ENOENT)
                          /* inconsistent with lstat; retry */
                          goto stat_ref;

It is really the same thing, but somehow the goto makes it more obvious
to me that it is the exceptional case to loop at all (and I think your
patch 3/4 could just go away entirely).  But I don't mind that much if
it stays with the for loop.

Thanks for a pleasant read; the split made the refactoring easy to
follow.

-Peff

Re: [PATCH 4/4] resolve_ref_unsafe(): close race condition reading loose refs

[Thomas Rast]

Michael Haggerty <mhagger@alum.mit.edu> writes:

> One race is still possible and undetected: another process could
> change the file from a regular file into a symlink between the call to
> lstat and the call to open().  The open() call would silently follow
> the symlink and not know that something is wrong.  I don't see a way
> to detect this situation without the use of the O_NOFOLLOW option,
> which is not portable and is not used elsewhere in our code base.
>
> However, we don't use symlinks anymore, so this situation is unlikely.
> And it doesn't appear that treating a symlink as a regular file would
> have grave consequences; after all, this is exactly how the code
> handles non-relative symlinks.

You could fstat() the fd you got from open(), and verify that it is
still the same inode/device.  That's wasting one syscall per ref for
pretty much everyone, but perhaps if we really cared about this (and I
gather from the above that we don't), we could conditionally use
O_NOFOLLOW if available, otherwise do that fstat().

-- 
Thomas Rast
trast@{inf,student}.ethz.ch

Re: [PATCH 4/4] resolve_ref_unsafe(): close race condition reading loose refs

[Michael Haggerty]

On 06/13/2013 10:22 AM, Thomas Rast wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> One race is still possible and undetected: another process could
>> change the file from a regular file into a symlink between the call to
>> lstat and the call to open().  The open() call would silently follow
>> the symlink and not know that something is wrong.  I don't see a way
>> to detect this situation without the use of the O_NOFOLLOW option,
>> which is not portable and is not used elsewhere in our code base.
>>
>> However, we don't use symlinks anymore, so this situation is unlikely.
>> And it doesn't appear that treating a symlink as a regular file would
>> have grave consequences; after all, this is exactly how the code
>> handles non-relative symlinks.
> 
> You could fstat() the fd you got from open(), and verify that it is
> still the same inode/device.  That's wasting one syscall per ref for
> pretty much everyone, but perhaps if we really cared about this (and I
> gather from the above that we don't), we could conditionally use
> O_NOFOLLOW if available, otherwise do that fstat().

Yes, that would work.  For now I think I will not worry about it, but
I'll keep your trick in mind.

Thanks,
Michael

-- 
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/