If a directory vanishes while renaming the temporary reflog file,
retry (up to 3 times).  This could happen if another process deletes
the directory created by safe_create_leading_directories() just before
we rename the file into the directory.

As far as I can tell, this race could not occur internal to git.  The
only time that a directory under $GIT_DIR/logs is deleted is if room
has to be made for a log file for a reference with the same name;
for example, in the following sequence:

    git branch foo/bar    # Creates file .git/logs/refs/heads/foo/bar
    git branch -d foo/bar # Deletes file but leaves .git/logs/refs/heads/foo/
    git branch foo        # Deletes .git/logs/refs/heads/foo/

But the only reason the last command deletes the directory is because
it wants to create a file with the same name.  So if another process
(e.g.,

    git branch foo/baz

) wants to create that directory, one of the two is doomed to failure
anyway because of a D/F conflict.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

It's about to become a bit more complex.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

If hold_lock_file_for_update() fails with errno==ENOENT, it might be
because somebody else (for example, a pack-refs process) has just
deleted one of the lockfile's ancestor directories.  So if this
condition is detected, try again (up to 3 times).
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

If safe_create_leading_directories() fails because a file along the
path unexpectedly vanished, try again (up to 3 times).

This can occur if another process is deleting directories at the same
time as we are trying to make them.  For example, "git pack-refs
--all" tries to delete the loose refs and any empty directories that
are left behind.  If a pack-refs process is running, then it might
delete a directory that we need to put a new loose reference in.

If safe_create_leading_directories() thinks this might have happened,
then take its advice and try again (maximum three attempts).
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The function 'invalidate_ref_cache' was introduced in 79c7ca54 (2011-10-17,
invalidate_ref_cache(): rename function from invalidate_cached_refs())
by a rename and elevated to be publicly usable in 8be8bde7 (2011-10-17,
invalidate_ref_cache(): expose this function in the refs API)

However it is not used anymore, as 8bf90dc9 (2011-10-17, write_ref_sha1():
only invalidate the loose ref cache) and (much) later 506a760d (2013-04-22,
refs: change how packed refs are deleted) removed any calls to this
function. So it seems as if we don't need that function any more,
good bye!
Signed-off-by: NStefan Beller <stefanbeller@googlemail.com>
Acked-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

In shorten_unambiguous_ref, we build and cache a reverse-map of the
rev-parse rules like this:

  static char **scanf_fmts;
  static int nr_rules;
  if (!nr_rules) {
	  for (; ref_rev_parse_rules[nr_rules]; nr_rules++)
		  ... generate scanf_fmts ...
  }

where ref_rev_parse_rules is terminated with a NULL pointer.
Compiling with "gcc -O2 -Wall" does not cause any problems, but
compiling with "-O3 -Wall" generates:

  $ make CFLAGS='-O3 -Wall' refs.o
  refs.c: In function ‘shorten_unambiguous_ref’:
  refs.c:3379:29: warning: array subscript is above array bounds [-Warray-bounds]
     for (; ref_rev_parse_rules[nr_rules]; nr_rules++)

Curiously, we can silence this by explicitly nr_rules to 0
in the beginning of the loop, even though the compiler
should be able to tell that we follow this code path only
when nr_rules is already 0.
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

A call to update_ref_lock() passes '0' to the 'int *type_p' parameter.
Noticed by sparse.  ("Using plain integer as NULL pointer")
Signed-off-by: NRamsay Jones <ramsay@ramsay1.demon.co.uk>
Signed-off-by: NJonathan Nieder <jrnieder@gmail.com>

Typing 'HEAD' is tedious, especially when we can use '@' instead.

The reason for choosing '@' is that it follows naturally from the
ref@op syntax (e.g. HEAD@{u}), except we have no ref, and no
operation, and when we don't have those, it makes sens to assume
'HEAD'.

So now we can use 'git show @~1', and all that goody goodness.

Until now '@' was a valid name, but it conflicts with this idea, so
let's make it invalid. Probably very few people, if any, used this name.
Signed-off-by: NFelipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Add 'struct ref_update' to encode the information needed to update or
delete a ref (name, new sha1, optional old sha1, no-deref flag).  Add
function 'update_refs' accepting an array of updates to perform.  First
sort the input array to order locks consistently everywhere and reject
multiple updates to the same ref.  Then acquire locks on all refs with
verified old values.  Then update or delete all refs accordingly.  Fail
if any one lock cannot be obtained or any one old value does not match.

Though the refs themselves cannot be modified together in a single
atomic transaction, this function does enable some useful semantics.
For example, a caller may create a new branch starting from the head of
another branch and rewind the original branch at the same time.  This
transfers ownership of commits between branches without risk of losing
commits added to the original branch by a concurrent process, or risk of
a concurrent process creating the new branch first.
Signed-off-by: NBrad King <brad.king@kitware.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Generalize repack_without_ref as repack_without_refs to support a list
of refs and implement the former in terms of the latter.
Signed-off-by: NBrad King <brad.king@kitware.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Factor loose ref deletion into helper function delete_ref_loose to allow
later use elsewhere.
Signed-off-by: NBrad King <brad.king@kitware.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Factor the lock and write steps and error handling into helper functions
update_ref_lock and update_ref_write to allow later use elsewhere.
Expose lock_any_ref_for_update's type_p to update_ref_lock callers.

While at it, drop "static" from the local "lock" variable as it is not
necessary to keep across invocations.
Signed-off-by: NBrad King <brad.king@kitware.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This is useful to make sure we don't step outside the boundaries of what
we are interpreting at the moment. For example while interpreting
foobar@{u}~1, the job of interpret_branch_name() ends right before ~1,
but there's no way to figure that out inside the function, unless the
len argument is passed.

So let's do that.
Signed-off-by: NFelipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Expose lock_ref_sha1_basic's type_p argument to callers of
lock_any_ref_for_update.  Update all call sites to ignore it by passing
NULL for now.
Signed-off-by: NBrad King <brad.king@kitware.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This reverts commit cdfd9483, as it
does not just apply to "@" (and forms with modifiers like @{u}
applied to it), but also affects e.g. "refs/heads/@/foo", which it
shouldn't.

The basic idea of giving a short-hand might be good, and the topic
can be retried later, but let's revert to avoid affecting existing
use cases for now for the upcoming release.

If do_one_ref() is called recursively, then the inner call should not
permanently overwrite the value stored in current_ref by the outer
call.  Aside from the tiny optimization loss, peel_ref() expects the
value of current_ref not to change across a call to peel_entry().  But
in the presence of replace references that assumption could be
violated by a recursive call to do_one_ref:

do_for_each_entry()
  do_one_ref()
    builtin/describe.c:get_name()
      peel_ref()
        peel_entry()
          peel_object ()
            deref_tag_noverify()
              parse_object()
                lookup_replace_object()
                  do_lookup_replace_object()
                    prepare_replace_object()
                      do_for_each_ref()
                        do_for_each_entry()
                          do_for_each_entry_in_dir()
                            do_one_ref()

The inner call to do_one_ref() was unconditionally setting current_ref
to NULL when it was done, causing peel_ref() to perform an invalid
memory access.

So change do_one_ref() to save the old value of current_ref before
overwriting it, and restore the old value afterward rather than
setting it to NULL.
Reported-by: NMantas Mikulėnas <grawity@gmail.com>
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The definition of "struct ref" in "cache.h", a header file so
central to the system, always confused me.  This structure is not
about the local ref used by sha1-name API to name local objects.

It is what refspecs are expanded into, after finding out what refs
the other side has, to define what refs are updated after object
transfer succeeds to what values.  It belongs to "remote.h" together
with "struct refspec".

While we are at it, also move the types and functions related to the
Git transport connection to a new header file connect.h
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Now that we keep track of the packed-refs file metadata, we can detect
when the packed-refs file has been modified since we last read it, and
we do so automatically every time that get_packed_ref_cache() is
called.  So there is no need to invalidate the cache automatically
when lock_packed_refs() is called; usually the old copy will still be
valid.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

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

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 its 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: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Increment the packed_ref_cache reference count while it is locked to
prevent its being freed.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

This function calls a user-supplied callback function which could do
something that causes the packed refs cache to be invalidated.  So
acquire a reference count on the data structure to prevent our copy
from being freed while we are iterating over it.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

In struct packed_ref_cache, keep a count of the number of users of the
data structure.  Only free the packed ref cache when the reference
count goes to zero rather than when the packed ref cache is cleared.
This mechanism will be used to prevent the cache data structure from
being freed while it is being iterated over.

So far, only the reference in struct ref_cache::packed is counted;
other users will be adjusted in separate commits.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Handle simple transactions for the packed-refs file at the
packed_ref_cache level via new functions lock_packed_refs(),
commit_packed_refs(), and rollback_packed_refs().

Only allow the packed ref cache to be modified (via add_packed_ref())
while the packed refs file is locked.

Change clone to add the new references within a transaction.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

As we know, we can solve any problem in this manner.  In this case,
the problem is to avoid freeing a packed refs cache while somebody is
using it.  So add a level of indirection as a prelude to
reference-counting the packed refs cache.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Split pack_refs() into multiple passes:

* Iterate over loose refs.  For each one that can be turned into a
  packed ref, create a corresponding entry in the packed refs cache.

* Write the packed refs to the packed-refs file.

This change isolates the mutation of the packed-refs file to a single
place.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The repack_without_ref() function first removes the deleted ref from
the internal packed-refs list, then writes the packed-refs list to
disk, omitting any broken or stale entries.  This patch splits that
second step into multiple passes:

* collect the list of refnames that should be deleted from packed_refs

* delete those refnames from the cache

* write the remainder to the packed-refs file

The purpose of this change is to make the "write the remainder" part
reusable.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

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, handle errors more selectively: if the result of
readline()/open() is a failure that is inconsistent with the result of
the previous lstat(), then something is fishy.  In this case jump back
and start over again 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.  This situation
could be detected in two ways:

* On systems that support O_NOFOLLOW, pass that option to the open().

* On other systems, call fstat() on the fd returned by open() and make
  sure that it agrees with the stat info from the original lstat().

However, we don't use symlinks anymore, so this situation is unlikely.
Moreover, 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.  So this commit leaves that race
unaddressed.

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: NMichael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

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.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

The nesting was getting a bit out of hand, and it's about to get
worse.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Reviewed-by: NJeff King <peff@peff.net>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Typing 'HEAD' is tedious, especially when we can use '@' instead.

The reason for choosing '@' is that it follows naturally from the
ref@op syntax (e.g. HEAD@{u}), except we have no ref, and no
operation, and when we don't have those, it makes sens to assume
'HEAD'.

So now we can use 'git show @~1', and all that goody goodness.

Until now '@' was a valid name, but it conflicts with this idea, so
let's make it invalid. Probably very few people, if any, used this name.
Signed-off-by: NFelipe Contreras <felipe.contreras@gmail.com>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Hold the ref_cache instance for the main repository in a dedicated,
statically-allocated instance to avoid the need for a function call
and a linked-list traversal when it is needed.

Suggested by: Heiko Voigt <hvoigt@hvoigt.net>
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Change the callers convert submodule names into ref_cache pointers.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Change pack_refs() to work with a file descriptor instead of a FILE*
(making the file-locking code less awkward) and use
write_packed_entry() to do the writing.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Change pack_one_ref() to call peel_entry() rather than using its own
code for peeling references.  Aside from sharing code, this lets it
take advantage of the optimization introduced by 6c4a060d.

Please note that we *could* use any peeled values that happen to
already be stored in the ref_entries, which would avoid some object
lookups for references that were already packed.  But doing so would
also propagate any peeling errors across runs of "git pack-refs" and
give no way to recover from such errors.  And "git pack-refs" isn't
run often enough that the performance cost is a problem.  So instead,
add a new option to peel_entry() to force the entry to be re-peeled,
and call it with that option set.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Function do_not_prune() was redundantly checking REF_ISSYMREF, which
was already tested at the top of pack_one_ref(), so remove that check.
And the rest was trivial, so inline the function.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

pack_refs() was not using any of the extra features of for_each_ref(),
so change it to use do_for_each_entry().  This also gives it access to
the ref_entry and in particular its peeled field, which will be taken
advantage of in the next commit.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Use a single struct lock_file for both pack_refs() and
repack_without_ref().
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>

Make this function conform to the naming convention established in
65385ef7 for the rest of the refs.c file.
Signed-off-by: NMichael Haggerty <mhagger@alum.mit.edu>
Signed-off-by: NJunio C Hamano <gitster@pobox.com>