has_sha1_file: re-check pack directory before giving up

When we read a sha1 file, we first look for a packed
version, then a loose version, and then re-check the pack
directory again before concluding that we cannot find it.
This lets us handle a process that is writing to the
repository simultaneously (e.g., receive-pack writing a new
pack followed by a ref update, or git-repack packing
existing loose objects into a new pack).

However, we do not do the same trick with has_sha1_file; we
only check the packed objects once, followed by loose
objects. This means that we might incorrectly report that we
do not have an object, even though we could find it if we
simply re-checked the pack directory.

By itself, this is usually not a big deal. The other process
is running simultaneously, so we may run has_sha1_file
before it writes, anyway. It is a race whether we see the
object or not.  However, we may also see other things
the writing process has done (like updating refs); and in
that case, we must be able to also see the new objects.

For example, imagine we are doing a for_each_ref iteration,
and somebody simultaneously pushes. Receive-pack may write
the pack and update a ref after we have examined the
objects/pack directory, but before the iteration gets to the
updated ref. When we do finally see the updated ref,
for_each_ref will call has_sha1_file to check whether the
ref is broken. If has_sha1_file returns the wrong answer, we
erroneously will think that the ref is broken.

For a normal iteration without DO_FOR_EACH_INCLUDE_BROKEN,
this means that the caller does not see the ref at all
(neither the old nor the new value).  So not only will we
fail to see the new value of the ref (which is acceptable,
since we are running simultaneously with the writer, and we
might well read the ref before the writer commits its
write), but we will not see the old value either. For
programs that act on reachability like pack-objects or
prune, this can cause data loss, as we may see the objects
referenced by the original ref value as dangling (and either
omit them from the pack, or delete them via prune).

There's no test included here, because the success case is
two processes running simultaneously forever. But you can
replicate the issue with:

  # base.sh
  # run this in one terminal; it creates and pushes
  # repeatedly to a repository
  git init parent &&
  (cd parent &&

    # create a base commit that will trigger us looking at
    # the objects/pack directory before we hit the updated ref
    echo content >file &&
    git add file &&
    git commit -m base &&

    # set the unpack limit abnormally low, which
    # lets us simulate full-size pushes using tiny ones
    git config receive.unpackLimit 1
  ) &&
  git clone parent child &&
  cd child &&
  n=0 &&
  while true; do
    echo $n >file && git add file && git commit -m $n &&
    git push origin HEAD:refs/remotes/child/master &&
    n=$(($n + 1))
  done

  # fsck.sh
  # now run this simultaneously in another terminal; it
  # repeatedly fscks, looking for us to consider the
  # newly-pushed ref broken. We cannot use for-each-ref
  # here, as it uses DO_FOR_EACH_INCLUDE_BROKEN, which
  # skips the has_sha1_file check (and if it wants
  # more information on the object, it will actually read
  # the object, which does the proper two-step lookup)
  cd parent &&
  while true; do
    broken=`git fsck 2>&1 | grep remotes/child`
    if test -n "$broken"; then
      echo $broken
      exit 1
    fi
  done

Without this patch, the fsck loop fails within a few seconds
(and almost instantly if the test repository actually has a
large number of refs). With it, the two can run
indefinitely.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
reset: rename update_refs to reset_refs

The function resets refs rather than doing arbitrary updates.
Rename it to allow a future general-purpose update_refs function
to be added.

Signed-off-by: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: report ref type from lock_any_ref_for_update

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: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: factor update_ref steps into helpers

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.

Signed-off-by: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: factor delete_ref loose ref step into a helper

Factor loose ref deletion into helper function delete_ref_loose to allow
later use elsewhere.

Signed-off-by: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: add function to repack without multiple refs

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: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
refs: add update_refs for multiple simultaneous updates

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 (and release any lock obtained so
far) 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: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
update-ref: support multiple simultaneous updates

Add a --stdin signature to read update instructions from standard input
and apply multiple ref updates together.  Use an input format that
supports any update that could be specified via the command-line,
including object names like 'branch:path with space'.

Signed-off-by: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
update-ref: add test cases covering --stdin signature

Extend t/t1400-update-ref.sh to cover cases using the --stdin option.

Signed-off-by: Brad King <brad.king@kitware.com>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
Merge branch 'jc/ls-files-killed-optim' into jch

"git ls-files -k" needs to crawl only the part of the working tree
that may overlap the paths in the index to find killed files, but
shared code with the logic to find all the untracked files, which
made it unnecessarily inefficient.

* jc/ls-files-killed-optim:
  dir.c::test_one_path(): work around directory_exists_in_index_icase() breakage
  t3010: update to demonstrate "ls-files -k" optimization pitfalls
  ls-files -k: a directory only can be killed if the index has a non-directory
  dir.c: use the cache_* macro to access the current index

# Conflicts:
# 	builtin/ls-files.c
# 	dir.c
# 	t/t3010-ls-files-killed-modified.sh
### third batch
Merge branch 'jx/branch-vv-always-compare-with-upstream' into jch

"git branch -v -v" (and "git status") did not distinguish among a
branch that does not build on any other branch, a branch that is in
sync with the branch it builds on, and a branch that is configured
to build on some other branch that no longer exists.

Am I waiting for another reroll?

* jx/branch-vv-always-compare-with-upstream:
  status: always show tracking branch even no change
  branch: report invalid tracking branch as gone
Merge branch 'ks/p4-view-spec' into jch

* ks/p4-view-spec:
  WAITING FOR ACK
  git p4: implement view spec wildcards with "p4 where"
  git p4 test: sanitize P4CHARSET
Merge branch 'nd/fetch-into-shallow' into jch

When there is no sufficient overlap between old and new history
during a fetch into a shallow repository, we unnecessarily sent
objects the sending side knows the receiving end has.

* nd/fetch-into-shallow:
  Add testcase for needless objects during a shallow fetch
  list-objects: mark more commits as edges in mark_edges_uninteresting
  list-objects: reduce one argument in mark_edges_uninteresting
  upload-pack: delegate rev walking in shallow fetch to pack-objects
  shallow: add setup_temporary_shallow()
  shallow: only add shallow graft points to new shallow file
  move setup_alternate_shallow and write_shallow_commits to shallow.c

# Conflicts:
# 	fetch-pack.c
Merge branch 'mm/mediawiki-dumb-push-fix' into jch

* mm/mediawiki-dumb-push-fix:
  git-remote-mediawiki: no need to update private ref in non-dumb push
  git-remote-mediawiki: use dont-update-private capability on dumb push
  transport-helper: add dont-update-private capability
  git-remote-mediawiki: add test and check Makefile targets

# Conflicts:
# 	transport-helper.c
Merge branch 'jk/duplicate-objects-in-packs' into jch

A packfile that stores the same object more than once is broken and
will be rejected.

* jk/duplicate-objects-in-packs:
  default pack.indexDuplicates to false
  index-pack: optionally reject packs with duplicate objects
  test index-pack on packs with recoverable delta cycles
  add tests for indexing packs with delta cycles
  sha1-lookup: handle duplicate keys with GIT_USE_LOOKUP
  test-sha1: add a binary output mode
Merge branch 'rv/send-email-cache-generated-mid' into jch

* rv/send-email-cache-generated-mid:
  git-send-email: Cache generated message-ids, use them when prompting
  git-send-email: add optional 'choices' parameter to the ask sub
Merge branch 'mm/fast-import-feature-doc' into jch

* mm/fast-import-feature-doc:
  Documentation/fast-import: clarify summary for `feature` command
Merge branch 'mn/doc-pack-heu-remove-dead-pastebin' into jch

* mn/doc-pack-heu-remove-dead-pastebin:
  remove dead pastebin link from pack-heuristics document
Merge branch 'ap/commit-author-mailmap' into jch

"git commit --author=$name", when $name is not in the canonical
"A. U. Thor <au.thor@example.xz>" format, looks for a matching name
from existing history, but did not consult mailmap to grab the
preferred author name.

* ap/commit-author-mailmap:
  commit: search author pattern against mailmap