for_each_ref: load all loose refs before packed refs

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: Michael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>

diff --git a/refs.c b/refs.c
index 60f250769ed2665f7103f519e04594819f3501d5..787cc1c9bc6af558bceb18d933321e93b399f195 100644 (file)
--- a/refs.c
+++ b/refs.c
@@ -749,6 +749,21 @@ static int do_for_each_entry_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
@@ -1603,15 +1618,31 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
 static int do_for_each_entry(struct ref_cache *refs, const char *base,
                             each_ref_entry_fn fn, void *cb_data)
 {
-       struct packed_ref_cache *packed_ref_cache = get_packed_ref_cache(refs);
-       struct ref_dir *packed_dir = get_packed_ref_dir(packed_ref_cache);
-       struct ref_dir *loose_dir = get_loose_refs(refs);
+       struct packed_ref_cache *packed_ref_cache;
+       struct ref_dir *loose_dir;
+       struct ref_dir *packed_dir;
        int retval = 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_ref_cache()
+        * 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_ref_cache = get_packed_ref_cache(refs);
        acquire_packed_ref_cache(packed_ref_cache);
+       packed_dir = get_packed_ref_dir(packed_ref_cache);
        if (base && *base) {
                packed_dir = find_containing_dir(packed_dir, base, 0);
-               loose_dir = find_containing_dir(loose_dir, base, 0);
        }
 
        if (packed_dir && loose_dir) {