Re: [PATCH 2/2] index-pack: prefetch missing REF_DELTA bases

On Tue, May 14, 2019 at 02:10:55PM -0700, Jonathan Tan wrote:

I agree that the current implementation (and probably any sane implementation) would not send us a delta if we have not provided any haves. But this does mean that a malicious server could send a client into an infinite loop.

Pretty unlikely, but should we put some kind of circuit-breaker into the client to ensure this?

Ah, but now things get more tricky.

You are assuming that the server does not ever send a REF_DELTA unless the base object is not present in the pack (it would use OFS_DELTA instead). If we imagine a server which did, then there are two implications:

  1. We might pre-fetch a full copy of an object that we don't need.
     It's just that it's stored as a delta in the pack which we are
     currently indexing.

  2. If we pre-fetch multiple objects, some of them may be REF_DELTAs
     against each other, leading to an infinite loop.

Off the top of my head, I am pretty sure your assumption holds for all versions of Git that support delta-base-offset[1]. But that feels a lot less certain to me. I could imagine an alternate server implementation, for example, that is gluing together packs and does not try hard to order the base before the delta, which would require it to use REF_DELTA instead of OFS_DELTA.

That's sort of contrived, but it does feel like we're introducing a really subtle requirement on the server here, which might close off options to us in the future.

Unfortunately, I can't really think of a way for an existing client to solve this without doing individual fetches for each REF_DELTA as we encounter a need for it. In fact, even then we may lose if our ordering is unlucky. E.g., imagine we have two packfile entries whose object ids (which we don't know yet!) are X and Y, and they are stored as REF_DELTAs with bases Z and X, respectively. Then either:

  1. We try to resolve X first. We fetch Z on-demand, and reconstruct X.
     We're lucky, because when we try to resolve Y, we see that we
     already have its base X.

  2. We try to resolve Y first. We fetch X on-demand, and reconstruct Y.
     We're unlucky; we then resolve X, but only after on-demand fetching
     Z and reconstructing it do we realize that we already had it.

So really, pre-fetching all of the REF_DELTAs just means we always hit the unlucky case. But even with careful on-demand fetching, our worst case is the same (and even worse in terms of latency).

I dunno. Maybe we should just ignore it. It's a fundamental issue with partial clones that we're going to have to fetch extra junk here anyway, because what the server _optimally_ would do is not send us deltas against objects we don't have anyway. We just don't have an efficient way to tell it what we do have.

If we're willing to modify the format, one thing we _could_ do is have the server communicate the expectations for each base. I.e., introduce a new THIN_DELTA type that behaves exactly as a REF_DELTA, but with the extra 1-bit of knowledge that the server knows it is not including the base in the pack. I'm not sure how painful that retro-fitting would be. It would need at least a new capability and options to pack-objects and index-pack. We might be tight on bits in the packfile type field.

-Peff

[1] Of course there are versions of Git that don't support
    delta-base-offset. They wouldn't support partial clones either, but
    it's possible to fetch into a partially-cloned repository from
    another remote. Given how old and rare such versions are, I think we
    can probably discount it entirely. I'm much more concerned about
    alternate implementations, or trying our hands for future
    pack-objects optimizations.