patchsha1_name: don't resolve refs when core.warnambiguousrefs is false

> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.

> ---
>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>         int at, reflog_len, nth_prior = 0;
>
>         if (len == 40 && !get_sha1_hex(str, sha1)) {
> -               if (warn_on_object_refname_ambiguity) {
> +               if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>                         refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -                       if (refs_found > 0 && warn_ambiguous_refs) {
> +                       if (refs_found > 0) {
>                                 warning(warn_msg, len, str);
>                                 if (advice_object_name_warning)
>                                         fprintf(stderr, "%s\n", _(object_name_msg));
> --
> 1.8.3.4 (Apple Git-47)
>

> On Mon, Jan 6, 2014 at 7:32 PM, Brodie Rao <brodie@sf.io> wrote:
> > This change ensures get_sha1_basic() doesn't try to resolve full hashes
> > as refs when ambiguous ref warnings are disabled.
> >
> > This provides a substantial performance improvement when passing many
> > hashes to a command (like "git rev-list --stdin") when
> > core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> > hash supplied, which can be costly over NFS.
> 
> Forgot to add:
> 
> Signed-off-by: Brodie Rao <brodie@sf.io>

> Jeff King <peff@peff.net> writes:
> 
> > Alternatively, I guess "cat-file
> > --batch" could just turn off warn_ambiguous_refs itself.
> 
> Sounds like a sensible way to go, perhaps on top of this change?

> On Tue, Jan 07, 2014 at 09:51:07AM -0800, Junio C Hamano wrote:
>
>> Jeff King <peff@peff.net> writes:
>> 
>> > Alternatively, I guess "cat-file
>> > --batch" could just turn off warn_ambiguous_refs itself.
>> 
>> Sounds like a sensible way to go, perhaps on top of this change?
>
> The downside is that we would not warn about ambiguous refs anymore,
> even if the user was expecting it to. I don't know if that matters much.

> >> > Alternatively, I guess "cat-file
> >> > --batch" could just turn off warn_ambiguous_refs itself.
> >> 
> >> Sounds like a sensible way to go, perhaps on top of this change?
> >
> > The downside is that we would not warn about ambiguous refs anymore,
> > even if the user was expecting it to. I don't know if that matters much.
> 
> That is true already with or without Brodie's change, isn't it?
> With warn_on_object_refname_ambiguity, "cat-file --batch" makes us
> ignore core.warnambigousrefs setting.  If we redo 25fba78d
> (cat-file: disable object/refname ambiguity check for batch mode,
> 2013-07-12) to unconditionally disable warn_ambiguous_refs in
> "cat-file --batch" and get rid of warn_on_object_refname_ambiguity,
> the end result would be the same, no?

> > I kind of feel in the --batch situation that it is somewhat useless (I
> > wonder if "rev-list --stdin" should turn it off, too).
> 
> I think doing the same as "cat-file --batch" in "rev-list --stdin"
> makes sense.  Both interfaces are designed to grok extended SHA-1s,
> and full 40-hex object names could be ambiguous and we are missing
> the warning for them.

> On Tue, Jan 07, 2014 at 11:38:15AM -0800, Junio C Hamano wrote:
>
>> >> > Alternatively, I guess "cat-file
>> >> > --batch" could just turn off warn_ambiguous_refs itself.
>> >> 
>> >> Sounds like a sensible way to go, perhaps on top of this change?
>> >
>> > The downside is that we would not warn about ambiguous refs anymore,
>> > even if the user was expecting it to. I don't know if that matters much.
>> 
>> That is true already with or without Brodie's change, isn't it?
>> With warn_on_object_refname_ambiguity, "cat-file --batch" makes us
>> ignore core.warnambigousrefs setting.  If we redo 25fba78d
>> (cat-file: disable object/refname ambiguity check for batch mode,
>> 2013-07-12) to unconditionally disable warn_ambiguous_refs in
>> "cat-file --batch" and get rid of warn_on_object_refname_ambiguity,
>> the end result would be the same, no?
>
> No, I don't think the end effect is the same (or maybe we are not
> talking about the same thing. :) ).
>
> There are two ambiguity situations:
>
>   1. Ambiguous non-fully-qualified refs (e.g., same tag and head name).
>
>   2. 40-hex sha1 object names which might also be unqualified ref names.
>
> Prior to 25ffba78d, cat-file checked both (like all the rest of git).
> But checking (2) is very expensive,...

> The two options I was musing over earlier today were (all on top of
> Brodie's patch):
>
>   a. Revert 25ffba78d. With Brodie's patch, core.warnAmbiguousRefs
>      disables _both_ warnings. So we default to safe-but-slow, but
>      people who care about performance can turn off ambiguity warnings.
>      The downside is that you have to know to turn it off manually (and
>      it's a global config flag, so you end up turning it off
>      _everywhere_, not just in big queries where it matters).

>   b. Revert 25ffba78d, but then on top of it just turn off
>      warn_ambiguous_refs unconditionally in "cat-file --batch-check".
>      The downside is that we drop the safety from (1). The upside is
>      that the code is a little simpler, as we drop the extra flag.
>
> And obviously:
>
>   c. Just leave it at Brodie's patch with nothing else on top.
>
> My thinking in favor of (b) was basically "does anybody actually care
> about ambiguous refs in this situation anyway?". If they do, then I
> think (c) is my preferred choice.

>> > I kind of feel in the --batch situation that it is somewhat useless (I
>> > wonder if "rev-list --stdin" should turn it off, too).
>> 
>> I think doing the same as "cat-file --batch" in "rev-list --stdin"
>> makes sense.  Both interfaces are designed to grok extended SHA-1s,
>> and full 40-hex object names could be ambiguous and we are missing
>> the warning for them.
>
> I'm not sure I understand what you are saying. We _do_ have the warning
> for "rev-list --stdin" currently. We do _not_ have the warning for
> "cat-file --batch", since my 25ffba78d.

> >   c. Just leave it at Brodie's patch with nothing else on top.
> >
> > My thinking in favor of (b) was basically "does anybody actually care
> > about ambiguous refs in this situation anyway?". If they do, then I
> > think (c) is my preferred choice.
> 
> OK.  I agree with that line of thinking.  Let's take it one step at
> a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
> "rev-list --stdin" first and leave the simplification (i.e. b.) for
> later.

> > OK.  I agree with that line of thinking.  Let's take it one step at
> > a time, i.e. do c. and also use warn_on_object_refname_ambiguity in
> > "rev-list --stdin" first and leave the simplification (i.e. b.) for
> > later.
> 
> Here's a series to do that. The first three are just cleanups I noticed
> while looking at the problem.
> 
> While I was writing the commit messages, though, I had a thought. Maybe
> we could simply do the check faster for the common case that most refs
> do not look like object names? Right now we blindly call dwim_ref for
> each get_sha1 call, which is the expensive part. If we instead just
> loaded all of the refnames from the dwim_ref location (basically heads,
> tags and the top-level of "refs/"), we could build an index of all of
> the entries matching the 40-hex pattern. In 99% of cases, this would be
> zero entries, and the check would collapse to a simple integer
> comparison (and even if we did have one, it would be a simple binary
> search in memory).

> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> 
> > +			if (flags & DO_FOR_EACH_NO_RECURSE) {
> > +				struct ref_dir *subdir = get_ref_dir(entry);
> > +				sort_ref_dir(subdir);
> > +				retval = do_for_each_entry_in_dir(subdir, 0,
> 
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.

> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> 
>> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
>> +				struct ref_dir *subdir = get_ref_dir(entry);
>> +				sort_ref_dir(subdir);
>> +				retval = do_for_each_entry_in_dir(subdir, 0,
> 
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.
> 
> Michael was nice enough to point it out to me off-list, but well, I have
> to face the brown paper bag at some point. :) In my defense, it was a
> last minute refactor before going to dinner. That is what I get for
> rushing out the series.
> 
> Here's a fixed version of patch 3/5.

> subdirectories, returning each ref it finds. However, in
> some cases we may want to just iterate over the top-level of
> a certain part of the tree.
> 
> The introduction of the "flags" option is a little
> mysterious. We already have a "flags" option that gets stuck
> in a callback struct and ends up interpreted in do_one_ref.
> But the traversal itself does not currently have any flags,
> and it needs to know about this new flag.
> 
> We _could_ introduce this as a completely separate flag
> parameter. But instead, we simply put both flag types into a
> single namespace, and make it available at both sites. This
> is simple, and given that we do not have a proliferation of
> flags (we have had exactly one until now), it is probably
> sufficient.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
>  1 file changed, 38 insertions(+), 23 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index 3926136..b70b018 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
>  
>  /* Include broken references in a do_for_each_ref*() iteration: */
>  #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
> +/* Do not recurse into subdirs, just iterate at a single level. */
> +#define DO_FOR_EACH_NO_RECURSE     0x02
>  
>  /*
>   * Return true iff the reference described by entry can be resolved to
> @@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
>   * called for all references, including broken ones.
>   */
>  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> -				    each_ref_entry_fn fn, void *cb_data)
> +				    each_ref_entry_fn fn, void *cb_data,
> +				    int flags)
>  {
>  	int i;
>  	assert(dir->sorted == dir->nr);

> [...]
> @@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
>  	data.conflicting_refname = NULL;
>  
>  	sort_ref_dir(dir);
> -	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
> +	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
>  		error("'%s' exists; cannot create '%s'",
>  		      data.conflicting_refname, refname);
>  		return 0;
> @@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
>   * 0.
>   */
>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> -			     each_ref_entry_fn fn, void *cb_data)
> +			     each_ref_entry_fn fn, void *cb_data,
> +			     int flags)
>  {
>  	struct packed_ref_cache *packed_ref_cache;
>  	struct ref_dir *loose_dir;

> > Here's a fixed version of patch 3/5.
> 
> v2 4/5 doesn't apply cleanly on top of v3 3/5.  So I'm basing my review
> on the branch you have at GitHub peff/git "jk/cat-file-warn-ambiguous";
> I hope it is the same.

> > -- >8 --
> > Subject: refs: teach for_each_ref a flag to avoid recursion
> > 
> > The normal for_each_ref traversal descends into
> 
> You haven't changed any for_each_ref*() functions; you have only exposed
> the DO_FOR_EACH_NO_RECURSE option to the (static) functions
> for_each_entry*() and do_for_each_ref().  (This is part and parcel of
> your decision not to expose the new functionality in the refs API.)
> Please correct the line above.

> >  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> > -				    each_ref_entry_fn fn, void *cb_data)
> > +				    each_ref_entry_fn fn, void *cb_data,
> > +				    int flags)
> >  {
> >  	int i;
> >  	assert(dir->sorted == dir->nr);
> 
> Please update the docstring for this function, which still says that it
> recurses without mentioning DO_FOR_EACH_NO_RECURSE.

> >  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> > -			     each_ref_entry_fn fn, void *cb_data)
> > +			     each_ref_entry_fn fn, void *cb_data,
> > +			     int flags)
> >  {
> >  	struct packed_ref_cache *packed_ref_cache;
> >  	struct ref_dir *loose_dir;
> 
> A few lines after this, do_for_each_entry() calls
> prime_ref_dir(loose_dir) to ensure that all of the loose references that
> will be iterated over are read before the packed-refs file is checked.
> It seems to me that prime_ref_dir() should also get a flags parameter to
> prevent it reading more loose references than necessary, something like
> this:

> > [...]
> > @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
> >  	data.fn = fn;
> >  	data.cb_data = cb_data;
> >  
> > -	return do_for_each_entry(refs, base, do_one_ref, &data);
> > +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
> >  }
> 
> This change makes the DO_FOR_EACH_NO_RECURSE option usable with
> do_for_each_ref() (even though it is never in fact used).  It should
> either be mentioned in the docstring or (if there is a reason not to
> allow it) explicitly prohibited.

> On Wed, Jan 08, 2014 at 12:29:51PM +0100, Michael Haggerty wrote:
> 
>>> Here's a fixed version of patch 3/5.
>>
>> v2 4/5 doesn't apply cleanly on top of v3 3/5.  So I'm basing my review
>> on the branch you have at GitHub peff/git "jk/cat-file-warn-ambiguous";
>> I hope it is the same.
> 
> Hrmph. I didn't have to do any conflict resolution during the rebase, so
> I would think it would apply at least with "am -3".

> [...]
>>>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
>>> -			     each_ref_entry_fn fn, void *cb_data)
>>> +			     each_ref_entry_fn fn, void *cb_data,
>>> +			     int flags)
>>>  {
>>>  	struct packed_ref_cache *packed_ref_cache;
>>>  	struct ref_dir *loose_dir;
>>
>> A few lines after this, do_for_each_entry() calls
>> prime_ref_dir(loose_dir) to ensure that all of the loose references that
>> will be iterated over are read before the packed-refs file is checked.
>> It seems to me that prime_ref_dir() should also get a flags parameter to
>> prevent it reading more loose references than necessary, something like
>> this:
> 
> Hmm. I hadn't considered that, but yeah, it definitely nullifies part of
> the purpose of the optimization.
> 
> However, is it safe to prime only part of the loose ref namespace? The
> point of that priming is to avoid the race fixed in 98eeb09, which
> depends on us caching the loose refs before the packed refs. But when we
> read packed-refs, we will be reading and storing _all_ of it, even if we
> do not touch it in this traversal. So it does not affect the race for
> this traversal, but have we setup a cache situation where a subsequent
> for_each_ref in the same process would be subject to the race?

>>> [...]
>>> @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
>>>  	data.fn = fn;
>>>  	data.cb_data = cb_data;
>>>  
>>> -	return do_for_each_entry(refs, base, do_one_ref, &data);
>>> +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
>>>  }
>>
>> This change makes the DO_FOR_EACH_NO_RECURSE option usable with
>> do_for_each_ref() (even though it is never in fact used).  It should
>> either be mentioned in the docstring or (if there is a reason not to
>> allow it) explicitly prohibited.
> 
> Hrm, yeah. I guess there are no callers, and there is no plan for any.
> So we could just pass "0" here, and then "flags" passed to
> do_for_each_ref really is _just_ for the callback data that goes to
> do_one_ref. That clears up the weird "combined namespace" stuff I
> mentioned in the commit message, and is a bit cleaner. I'll take it in
> that direction.

> > However, is it safe to prime only part of the loose ref namespace?
> [...]
> 
> prime_ref_dir() is called by do_for_each_entry(), which all the
> iteration functions pass through.  It is always called before the
> iteration starts, and it primes only the subtree of the refs hierarchy
> that is being iterated over.  For example, if iterating over
> "refs/heads" then it only primes references with that prefix.
> 
> This is OK, because if later somebody iterates over a broader part of
> the refs hierarchy (say, "refs"), then priming is done again, including
> re-checking the packed refs.

> It would also be possible to swing in the other direction.  I don't
> remember a particular reason why I left the DO_FOR_EACH_INCLUDE_BROKEN
> handling at the do_for_each_ref() level rather than handling it at the
> do_for_each_entry() level.  But now that you are passing the flags
> parameter all the way down the call stack, it wouldn't cost anything to
> support both of the DO_FOR_EACH flags everywhere and just document it
> that way.

> On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
>
>> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
>> +				struct ref_dir *subdir = get_ref_dir(entry);
>> +				sort_ref_dir(subdir);
>> +				retval = do_for_each_entry_in_dir(subdir, 0,
>
> Obviously this is totally wrong and inverts the point of the flag. And
> causes something like half of the test suite to fail.
>
> Michael was nice enough to point it out to me off-list, but well, I have
> to face the brown paper bag at some point. :) In my defense, it was a
> last minute refactor before going to dinner. That is what I get for
> rushing out the series.

> Here's a fixed version of patch 3/5.
>
> -- >8 --
> Subject: refs: teach for_each_ref a flag to avoid recursion
>
> The normal for_each_ref traversal descends into
> subdirectories, returning each ref it finds. However, in
> some cases we may want to just iterate over the top-level of
> a certain part of the tree.
>
> The introduction of the "flags" option is a little
> mysterious. We already have a "flags" option that gets stuck
> in a callback struct and ends up interpreted in do_one_ref.
> But the traversal itself does not currently have any flags,
> and it needs to know about this new flag.
>
> We _could_ introduce this as a completely separate flag
> parameter. But instead, we simply put both flag types into a
> single namespace, and make it available at both sites. This
> is simple, and given that we do not have a proliferation of
> flags (we have had exactly one until now), it is probably
> sufficient.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  refs.c | 61 ++++++++++++++++++++++++++++++++++++++-----------------------
>  1 file changed, 38 insertions(+), 23 deletions(-)
>
> diff --git a/refs.c b/refs.c
> index 3926136..b70b018 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -589,6 +589,8 @@ static void sort_ref_dir(struct ref_dir *dir)
>  
>  /* Include broken references in a do_for_each_ref*() iteration: */
>  #define DO_FOR_EACH_INCLUDE_BROKEN 0x01
> +/* Do not recurse into subdirs, just iterate at a single level. */
> +#define DO_FOR_EACH_NO_RECURSE     0x02
>  
>  /*
>   * Return true iff the reference described by entry can be resolved to
> @@ -661,7 +663,8 @@ static int do_one_ref(struct ref_entry *entry, void *cb_data)
>   * called for all references, including broken ones.
>   */
>  static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
> -				    each_ref_entry_fn fn, void *cb_data)
> +				    each_ref_entry_fn fn, void *cb_data,
> +				    int flags)
>  {
>  	int i;
>  	assert(dir->sorted == dir->nr);
> @@ -669,9 +672,13 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
>  		struct ref_entry *entry = dir->entries[i];
>  		int retval;
>  		if (entry->flag & REF_DIR) {
> -			struct ref_dir *subdir = get_ref_dir(entry);
> -			sort_ref_dir(subdir);
> -			retval = do_for_each_entry_in_dir(subdir, 0, fn, cb_data);
> +			if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
> +				struct ref_dir *subdir = get_ref_dir(entry);
> +				sort_ref_dir(subdir);
> +				retval = do_for_each_entry_in_dir(subdir, 0,
> +								  fn, cb_data,
> +								  flags);
> +			}
>  		} else {
>  			retval = fn(entry, cb_data);
>  		}
> @@ -691,7 +698,8 @@ static int do_for_each_entry_in_dir(struct ref_dir *dir, int offset,
>   */
>  static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  				     struct ref_dir *dir2,
> -				     each_ref_entry_fn fn, void *cb_data)
> +				     each_ref_entry_fn fn, void *cb_data,
> +				     int flags)
>  {
>  	int retval;
>  	int i1 = 0, i2 = 0;
> @@ -702,10 +710,12 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  		struct ref_entry *e1, *e2;
>  		int cmp;
>  		if (i1 == dir1->nr) {
> -			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data);
> +			return do_for_each_entry_in_dir(dir2, i2, fn, cb_data,
> +							flags);
>  		}
>  		if (i2 == dir2->nr) {
> -			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data);
> +			return do_for_each_entry_in_dir(dir1, i1, fn, cb_data,
> +							flags);
>  		}
>  		e1 = dir1->entries[i1];
>  		e2 = dir2->entries[i2];
> @@ -713,12 +723,15 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  		if (cmp == 0) {
>  			if ((e1->flag & REF_DIR) && (e2->flag & REF_DIR)) {
>  				/* Both are directories; descend them in parallel. */
> -				struct ref_dir *subdir1 = get_ref_dir(e1);
> -				struct ref_dir *subdir2 = get_ref_dir(e2);
> -				sort_ref_dir(subdir1);
> -				sort_ref_dir(subdir2);
> -				retval = do_for_each_entry_in_dirs(
> -						subdir1, subdir2, fn, cb_data);
> +				if (!(flags & DO_FOR_EACH_NO_RECURSE)) {
> +					struct ref_dir *subdir1 = get_ref_dir(e1);
> +					struct ref_dir *subdir2 = get_ref_dir(e2);
> +					sort_ref_dir(subdir1);
> +					sort_ref_dir(subdir2);
> +					retval = do_for_each_entry_in_dirs(
> +							subdir1, subdir2,
> +							fn, cb_data, flags);
> +				}
>  				i1++;
>  				i2++;
>  			} else if (!(e1->flag & REF_DIR) && !(e2->flag & REF_DIR)) {
> @@ -743,7 +756,7 @@ static int do_for_each_entry_in_dirs(struct ref_dir *dir1,
>  				struct ref_dir *subdir = get_ref_dir(e);
>  				sort_ref_dir(subdir);
>  				retval = do_for_each_entry_in_dir(
> -						subdir, 0, fn, cb_data);
> +						subdir, 0, fn, cb_data, flags);
>  			} else {
>  				retval = fn(e, cb_data);
>  			}
> @@ -817,7 +830,7 @@ static int is_refname_available(const char *refname, const char *oldrefname,
>  	data.conflicting_refname = NULL;
>  
>  	sort_ref_dir(dir);
> -	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data)) {
> +	if (do_for_each_entry_in_dir(dir, 0, name_conflict_fn, &data, 0)) {
>  		error("'%s' exists; cannot create '%s'",
>  		      data.conflicting_refname, refname);
>  		return 0;
> @@ -1651,7 +1664,8 @@ void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
>   * 0.
>   */
>  static int do_for_each_entry(struct ref_cache *refs, const char *base,
> -			     each_ref_entry_fn fn, void *cb_data)
> +			     each_ref_entry_fn fn, void *cb_data,
> +			     int flags)
>  {
>  	struct packed_ref_cache *packed_ref_cache;
>  	struct ref_dir *loose_dir;
> @@ -1684,15 +1698,15 @@ static int do_for_each_entry(struct ref_cache *refs, const char *base,
>  		sort_ref_dir(packed_dir);
>  		sort_ref_dir(loose_dir);
>  		retval = do_for_each_entry_in_dirs(
> -				packed_dir, loose_dir, fn, cb_data);
> +				packed_dir, loose_dir, fn, cb_data, flags);
>  	} else if (packed_dir) {
>  		sort_ref_dir(packed_dir);
>  		retval = do_for_each_entry_in_dir(
> -				packed_dir, 0, fn, cb_data);
> +				packed_dir, 0, fn, cb_data, flags);
>  	} else if (loose_dir) {
>  		sort_ref_dir(loose_dir);
>  		retval = do_for_each_entry_in_dir(
> -				loose_dir, 0, fn, cb_data);
> +				loose_dir, 0, fn, cb_data, flags);
>  	}
>  
>  	release_packed_ref_cache(packed_ref_cache);
> @@ -1718,7 +1732,7 @@ static int do_for_each_ref(struct ref_cache *refs, const char *base,
>  	data.fn = fn;
>  	data.cb_data = cb_data;
>  
> -	return do_for_each_entry(refs, base, do_one_ref, &data);
> +	return do_for_each_entry(refs, base, do_one_ref, &data, flags);
>  }
>  
>  static int do_head_ref(const char *submodule, each_ref_fn fn, void *cb_data)
> @@ -2200,7 +2214,7 @@ int commit_packed_refs(void)
>  
>  	do_for_each_entry_in_dir(get_packed_ref_dir(packed_ref_cache),
>  				 0, write_packed_entry_fn,
> -				 &packed_ref_cache->lock->fd);
> +				 &packed_ref_cache->lock->fd, 0);
>  	if (commit_lock_file(packed_ref_cache->lock))
>  		error = -1;
>  	packed_ref_cache->lock = NULL;
> @@ -2345,7 +2359,7 @@ int pack_refs(unsigned int flags)
>  	cbdata.packed_refs = get_packed_refs(&ref_cache);
>  
>  	do_for_each_entry_in_dir(get_loose_refs(&ref_cache), 0,
> -				 pack_if_possible_fn, &cbdata);
> +				 pack_if_possible_fn, &cbdata, 0);
>  
>  	if (commit_packed_refs())
>  		die_errno("unable to overwrite old ref-pack file");
> @@ -2447,7 +2461,8 @@ static int repack_without_refs(const char **refnames, int n)
>  	}
>  
>  	/* Remove any other accumulated cruft */
> -	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn, &refs_to_delete);
> +	do_for_each_entry_in_dir(packed, 0, curate_packed_ref_fn,
> +				 &refs_to_delete, 0);
>  	for_each_string_list_item(ref_to_delete, &refs_to_delete) {
>  		if (remove_entry(packed, ref_to_delete->string) == -1)
>  			die("internal error");

> > On Tue, Jan 07, 2014 at 06:58:50PM -0500, Jeff King wrote:
> >
> >> +			if (flags & DO_FOR_EACH_NO_RECURSE) {
> >> +				struct ref_dir *subdir = get_ref_dir(entry);
> >> +				sort_ref_dir(subdir);
> >> +				retval = do_for_each_entry_in_dir(subdir, 0,
> >
> > Obviously this is totally wrong and inverts the point of the flag. And
> > causes something like half of the test suite to fail.
> >
> > Michael was nice enough to point it out to me off-list, but well, I have
> > to face the brown paper bag at some point. :) In my defense, it was a
> > last minute refactor before going to dinner. That is what I get for
> > rushing out the series.
> 
> And perhaps a bad naming that calls for double-negation in the
> normal cases, which might have been less likely to happen it the new
> flag were called "onelevel only" or something, perhaps?

> Since 798c35f (get_sha1: warn about full or short object
> names that look like refs, 2013-05-29), a 40-hex sha1 causes
> us to call dwim_ref on the result, on the off chance that we
> have a matching ref. This can cause a noticeable slow-down
> when there are a large number of objects.  E.g., on
> linux.git:
> 
>   [baseline timing]
>   $ best-of-five git rev-list --all --pretty=raw
>   real    0m3.996s
>   user    0m3.900s
>   sys     0m0.100s
> 
>   [same thing, but calling get_sha1 on each commit from stdin]
>   $ git rev-list --all >commits
>   $ best-of-five -i commits git rev-list --stdin --pretty=raw
>   real    0m7.862s
>   user    0m6.108s
>   sys     0m1.760s
> 
> The problem is that each call to dwim_ref individually stats
> the possible refs in refs/heads, refs/tags, etc. In the
> common case, there are no refs that look like sha1s at all.
> We can therefore do the same check much faster by loading
> all ambiguous-looking candidates once, and then checking our
> index for each object.
> 
> This is technically more racy (somebody might create such a
> ref after we build our index), but that's OK, as it's just a
> warning (and we provide no guarantees about whether a
> simultaneous process ran before or after the ref was created
> anyway).

> Here is the time after this patch, which implements the
> strategy described above:
> 
>   $ best-of-five -i commits git rev-list --stdin --pretty=raw
>   real    0m4.966s
>   user    0m4.776s
>   sys     0m0.192s
> 
> We still pay some price to read the commits from stdin, but
> notice the system time is much lower, as we are avoiding
> hundreds of thousands of stat() calls.
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I wanted to make the ref traversal as cheap as possible, hence the
> NO_RECURSE flag I added. I thought INCLUDE_BROKEN used to not open up
> the refs at all, but it looks like it does these days. I wonder if that
> is worth changing or not.

> 
>  refs.c      | 47 +++++++++++++++++++++++++++++++++++++++++++++++
>  refs.h      |  2 ++
>  sha1_name.c |  4 +---
>  3 files changed, 50 insertions(+), 3 deletions(-)
> 
> diff --git a/refs.c b/refs.c
> index ca854d6..cddd871 100644
> --- a/refs.c
> +++ b/refs.c
> @@ -4,6 +4,7 @@
>  #include "tag.h"
>  #include "dir.h"
>  #include "string-list.h"
> +#include "sha1-array.h"
>  
>  /*
>   * Make sure "ref" is something reasonable to have under ".git/refs/";
> @@ -2042,6 +2043,52 @@ int dwim_log(const char *str, int len, unsigned char *sha1, char **log)
>  	return logs_found;
>  }
>  
> +static int check_ambiguous_sha1_ref(const char *refname,
> +				    const unsigned char *sha1,
> +				    int flags,
> +				    void *data)
> +{
> +	unsigned char tmp_sha1[20];
> +	if (strlen(refname) == 40 && !get_sha1_hex(refname, tmp_sha1))
> +		sha1_array_append(data, tmp_sha1);
> +	return 0;
> +}
> +
> +static void build_ambiguous_sha1_ref_index(struct sha1_array *idx)
> +{
> +	const char **rule;
> +
> +	for (rule = ref_rev_parse_rules; *rule; rule++) {
> +		const char *prefix = *rule;
> +		const char *end = strstr(prefix, "%.*s");
> +		char *buf;
> +
> +		if (!end)
> +			continue;
> +
> +		buf = xmemdupz(prefix, end - prefix);
> +		do_for_each_ref(&ref_cache, buf, check_ambiguous_sha1_ref,
> +				end - prefix,
> +				DO_FOR_EACH_INCLUDE_BROKEN |
> +				DO_FOR_EACH_NO_RECURSE,
> +				idx);

> +		free(buf);
> +	}
> +}
> +
> +int sha1_is_ambiguous_with_ref(const unsigned char *sha1)
> +{
> +	struct sha1_array idx = SHA1_ARRAY_INIT;
> +	static int loaded;
> +
> +	if (!loaded) {
> +		build_ambiguous_sha1_ref_index(&idx);
> +		loaded = 1;
> +	}
> +
> +	return sha1_array_lookup(&idx, sha1) >= 0;
> +}
> +
>  static struct ref_lock *lock_ref_sha1_basic(const char *refname,
>  					    const unsigned char *old_sha1,
>  					    int flags, int *type_p)
> diff --git a/refs.h b/refs.h
> index 87a1a79..c7d5f89 100644
> --- a/refs.h
> +++ b/refs.h
> @@ -229,4 +229,6 @@ int update_refs(const char *action, const struct ref_update **updates,
>  extern int parse_hide_refs_config(const char *var, const char *value, const char *);
>  extern int ref_is_hidden(const char *);
>  
> +int sha1_is_ambiguous_with_ref(const unsigned char *sha1);
> +
>  #endif /* REFS_H */

> diff --git a/sha1_name.c b/sha1_name.c
> index a5578f7..f83ecb7 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -452,13 +452,11 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>  
>  	if (len == 40 && !get_sha1_hex(str, sha1)) {
>  		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
> -			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -			if (refs_found > 0) {
> +			if (sha1_is_ambiguous_with_ref(sha1)) {
>  				warning(warn_msg, len, str);
>  				if (advice_object_name_warning)
>  					fprintf(stderr, "%s\n", _(object_name_msg));
>  			}
> -			free(real_ref);
>  		}
>  		return 0;
>  	}
> 

> It's not only racy WRT other processes.  If the current git process
> would create a new reference, it wouldn't be reflected in the cache.
>
> It's true that the main ref_cache doesn't invalidate itself
> automatically either when a new reference is created, so it's not really
> a fair complaint.  However, as we add places where the cache is
> invalidated, it is easy to overlook this cache that is stuck in static
> variables within a function definition and it is impossible to
> invalidate it.  Might it not be better to attach the cache to the
> ref_cache structure instead, and couple its lifetime to that object?
>
> Alternatively, the cache could be created and managed on the caller
> side, since the caller would know when the cache would have to be
> invalidated.  Also, different callers are likely to have different
> performance characteristics.  It is unlikely that the time to initialize
> the cache will be amortized in most cases; in fact, "rev-list --stdin"
> might be the *only* plausible use case.

> Regarding the overall strategy: you gather all refnames that could be
> confused with an SHA-1 into a sha1_array, then later look up SHA-1s in
> the array to see if they are ambiguous.  This is a very special-case
> optimization for SHA-1s.
>
> I wonder whether another approach would gain almost the same amount of
> performance but be more general.  We could change dwim_ref() (or a
> version of it?) to read its data out of a ref_cache instead of going to
> disk every time.  Then, at the cost of populating the relevant parts of
> the ref_cache once, we would have fast dwim_ref() calls for all strings.

> It's not only racy WRT other processes.  If the current git process
> would create a new reference, it wouldn't be reflected in the cache.
> 
> It's true that the main ref_cache doesn't invalidate itself
> automatically either when a new reference is created, so it's not really
> a fair complaint.  However, as we add places where the cache is
> invalidated, it is easy to overlook this cache that is stuck in static
> variables within a function definition and it is impossible to
> invalidate it.  Might it not be better to attach the cache to the
> ref_cache structure instead, and couple its lifetime to that object?

> Alternatively, the cache could be created and managed on the caller
> side, since the caller would know when the cache would have to be
> invalidated.  Also, different callers are likely to have different
> performance characteristics.  It is unlikely that the time to initialize
> the cache will be amortized in most cases; in fact, "rev-list --stdin"
> might be the *only* plausible use case.

> I wonder whether another approach would gain almost the same amount of
> performance but be more general.  We could change dwim_ref() (or a
> version of it?) to read its data out of a ref_cache instead of going to
> disk every time.  Then, at the cost of populating the relevant parts of
> the ref_cache once, we would have fast dwim_ref() calls for all strings.

> It's true that the lookups wouldn't be quite so fast--they would require
> a few bisects per refname lookup (one for each level in the refname
> hierarchy) and several refname lookups (one for each ref_rev_parse_rule)
> for every dwim_ref() call, vs. a single bisect in your current design.
> But this approach it would bring us most of the gain, it might
> nevertheless be preferable.

> > I wanted to make the ref traversal as cheap as possible, hence the
> > NO_RECURSE flag I added. I thought INCLUDE_BROKEN used to not open up
> > the refs at all, but it looks like it does these days. I wonder if that
> > is worth changing or not.
> 
> What do you mean by "open up the refs"?  The loose reference files are
> read when populating the cache.  (Was that ever different?)

> This doesn't correctly handle the rule
> 
> 	"refs/remotes/%.*s/HEAD"
>
> We might be willing to accept this limitation, but it should at least be
> mentioned somewhere.  OTOH if we want to handle this pattern as well, we
> could do use a technique like that of shorten_unambiguous_ref().

> That being said, we could further optimize this by not opening the files
> at all (and make that the responsibility of do_one_ref, which we are
> avoiding here). I am slightly worried about the open() cost of my
> solution. It's amortized away in a big call, but it is probably
> noticeable for something like `git rev-parse <40-hex>`.

> On Fri, Jan 10, 2014 at 04:41:20AM -0500, Jeff King wrote:
> 
>> That being said, we could further optimize this by not opening the files
>> at all (and make that the responsibility of do_one_ref, which we are
>> avoiding here). I am slightly worried about the open() cost of my
>> solution. It's amortized away in a big call, but it is probably
>> noticeable for something like `git rev-parse <40-hex>`.
> 
> I took a look at this. It gets a bit hairy. My strategy is to add a flag
> to ask read_loose_refs to create REF_INCOMPLETE values. We currently use
> this flag for loose REF_DIRs to mean "we haven't opendir()'d the
> subdirectory yet". This would extend it to the non-REF_DIR case to mean
> "we haven't opened the loose ref file yet". We'd check REF_INCOMPLETE
> before handing the ref_entry to a callback, and complete it if
> necessary.
> 
> It gets ugly, though, because we need to pass that flag through quite a
> bit of callstack. get_ref_dir() needs to know it, which means all of
> find_containing_dir, etc need it, meaning it pollutes all of the
> packed-refs code paths too.
> 
> I have a half-done patch in this direction if that doesn't sound too
> nasty.

>>> This doesn't correctly handle the rule
>>>
>>> 	"refs/remotes/%.*s/HEAD"
>> [...]
> 
>> I'll see how painful it is to make it work.
> 
> It's actually reasonably painful. I thought at first we could get away
> with more cleverly parsing the rule, find the prefix (up to the
> placeholder), and then look for the suffix ("/HEAD") inside there. But
> it can never work with the current do_for_each_* code. That code only
> triggers a callback when we see a concrete ref. It _never_ lets the
> callbacks see an intermediate directory.
> 
> So a NO_RECURSE flag is not sufficient to handle this case. I'd need to
> teach do_for_each_ref to recurse based on pathspecs, or a custom
> callback function. And that is getting quite complicated.

> I think it might be simpler to just do my own custom traversal. What I
> need is much simpler than what do_for_each_entry provides. I don't need
> recursion, and I don't actually need to look at the loose and packed
> refs together. It's OK for me to do them one at a time because I don't
> care about the actual value; I just want to know about which refs exist.

> Now that our object/refname ambiguity test is much faster
> (thanks to the previous commit), there is no reason for code
> like "cat-file --batch-check" to turn it off. Here are
> before and after timings with this patch (on git.git):
> 
>   $ git rev-list --objects --all | cut -d' ' -f1 >objects
> 
>   [with flag]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m0.392s
>   user    0m0.368s
>   sys     0m0.024s
> 
>   [without flag, without speedup; i.e., pre-25fba78]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m1.652s
>   user    0m0.904s
>   sys     0m0.748s
> 
>   [without flag, with speedup]
>   $ best-of-five -i objects ./git cat-file --batch-check
>   real    0m0.388s
>   user    0m0.356s
>   sys     0m0.028s
> 
> So the new implementation does just as well as we did with
> the flag turning the whole thing off (better actually, but
> that is within the noise).
> 
> Signed-off-by: Jeff King <peff@peff.net>
> [...]

> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.
> ---
>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>         int at, reflog_len, nth_prior = 0;
>
>         if (len == 40 && !get_sha1_hex(str, sha1)) {
> -               if (warn_on_object_refname_ambiguity) {
> +               if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>                         refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -                       if (refs_found > 0 && warn_ambiguous_refs) {
> +                       if (refs_found > 0) {
>                                 warning(warn_msg, len, str);
>                                 if (advice_object_name_warning)
>                                         fprintf(stderr, "%s\n", _(object_name_msg));

> This change ensures get_sha1_basic() doesn't try to resolve full hashes
> as refs when ambiguous ref warnings are disabled.
>
> This provides a substantial performance improvement when passing many
> hashes to a command (like "git rev-list --stdin") when
> core.warnambiguousrefs is false. The check incurs 6 stat()s for every
> hash supplied, which can be costly over NFS.
> ---

>  sha1_name.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/sha1_name.c b/sha1_name.c
> index e9c2999..10bd007 100644
> --- a/sha1_name.c
> +++ b/sha1_name.c
> @@ -451,9 +451,9 @@ static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
>  	int at, reflog_len, nth_prior = 0;
>  
>  	if (len == 40 && !get_sha1_hex(str, sha1)) {
> -		if (warn_on_object_refname_ambiguity) {
> +		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
>  			refs_found = dwim_ref(str, len, tmp_sha1, &real_ref);
> -			if (refs_found > 0 && warn_ambiguous_refs) {
> +			if (refs_found > 0) {
>  				warning(warn_msg, len, str);
>  				if (advice_object_name_warning)
>  					fprintf(stderr, "%s\n", _(object_name_msg));