Re: [PATCH v2 29/33] refs: resolve symbolic refs first

On 05/12/2016 10:25 AM, Jeff King wrote:

On Thu, May 12, 2016 at 03:45:28AM -0400, Jeff King wrote:

quoted

So I'd expect us to hit that lock_ref_for_update() for each of the new
refs. But then we end up in verify_refname_available_dir(), which wants
to read all of the loose refs again. So we end up with a quadratic
number of calls to read_ref_full().

I haven't found the actual bug yet. It may be something as simple as not
clearing REF_INCOMPLETE from the loose-ref cache when we ought to. But
that's a wild (optimistic) guess.

Ah, nope, nothing so simple.

It looks like we get in a chain of:

  1. we want to update a ref, so we end up in
     verify_refname_available_dir to make sure we can do so.

  2. that has to load all of the loose refs in refs/tags, which is
     expensive.

  3. we actually update the ref, which calls clear_loose_ref_cache().

And repeat. Each ref update does the expensive step 2, and it gets
larger and larger each time.

I understand why we need to verify_refname_available() on the packed
refs. But traditionally we would rely on EISDIR or EEXIST to detect
conflicts with the loose refs, rather than loading using our own cache.
So I guess that's the new thing that is causing a problem.

Torsten, thanks for the report. Peff, thanks for the analysis.

The problem in this case is a misguided call to
verify_refname_available_dir() in the case that read_raw_ref() fails
with ENOENT. In that case it is not possible for there to be a conflict
with another loose reference, because (1) we already hold the lock, so
the containing directory must exist, and (2) we got ENOENT, so there
can't be a loose reference in a subdirectory named after the reference
that we are trying to create.

As Peff explained, the call of verify_refname_available_dir() was
forcing the loose tags to be loaded, which is expensive in this test
because there are 100000 of them being created one at a time. (If they
were created in a single ref_transaction instead, the "available" tests
would all be done together, before any changes are committed, so the
loose ref cache would not have to be invalidated each time.)

So instead of calling verify_refname_available_dir() here, we should
just consider the reference to be missing but available to be written.

I'll rewrite this patch and submit the new version to the mailing list
as v3 (also with a fix in the commit message). The rest of the patch
series is OK as is, so I won't resend it. The entire series is also
available from my GitHub repo [1] as branch "split-under-lock".

Please note that there are still some calls of
verify_refname_available_dir() against the loose reference cache in this
function. If we wanted to give up a little bit on the quality of our
error messages, I think we could make those paths faster, too. But they
are all in failure paths, so I don't think that they are performance
critical, so I won't make that change.

Michael

[1] https://github.com/mhagger/git