Re: [PATCH v3 0/2] pack-objects mru

From: Jeff King <peff@peff.net>
Date: Aug 11, 2016, 04:48 UTC
Message-ID: <20160811044809.ep22lybdyfzmx4pl@sigill.intra.peff.net>
In-Reply-To: <xmqqbn107epz.fsf@gitster.mtv.corp.google.com>

On Wed, Aug 10, 2016 at 09:47:52AM -0700, Junio C Hamano wrote:

Show 15 quoted lines

> Jeff King <peff@peff.net> writes:
> 
> >> This is not new with this change, but I am not quite sure what in
> >> the current code prevents us from busting the delta limit for reused
> >> ones, though.
> >
> > I think in the current code you are limited by the depth you might find
> > in a single existing pack (since we never reuse cross-pack deltas).
> 
> Sorry for going deeper in the tangent, but I vaguely recall raising
> it long time ago as a potential issue that delta reuse out of an
> original pack created with deep delta chain may bust a delta chain
> limit when repacking with shorter delta chain limit; I just do not
> remember where that discussion went (i.e. decided to be a non-issue?
> we added code to avoid it? etc.)

Digging on the list and in the history, I found your e4c9327 (pack-objects: avoid delta chains that are too long., 2006-02-17). That approach went away with Nico's 898b14c (pack-objects: rework check_delta_limit usage, 2007-04-16), which I think is where we are at today.

I found the patches for both on the list, but no interesting discussion.

It looks like 898b14c does the depth check dynamically in find_delta. So we would not build on a too-long chain, but I do not see anything that prevents us from creating a too-long chain purely out of reused deltas.

Which means that even without my patches, repacking with a shorter delta chain does not guarantee you do not have a longer chain. And mine introduces a potential "packs * max_depth" problem (I also think check_delta_limit could recurse very deeply if given a pathologically weird pack that has insane delta limits, but presumably we would just run out of stack and crash, which seems like an OK outcome for such maliciousness).

I guess it would not be that hard to break the reused chains as part of the DFS search I introduced (we are recursing already; just stop recursing and break when we hit the max-depth).

Show 17 quoted lines

> > However, I think with cross-pack deltas, you could have a situation
> > like:
> >
> >   pack 1: A -> B -> C
> >   pack 2: C -> D -> E
> >
> > and pick A and B from the first pack, and C, D, and E from the second.
> > Then you end up with:
> >
> >   A -> B -> C -> D -> E
> >
> > in the output. IOW, I think the absolute worst case chain is the
> > max_depth times the number of packs.
> 
> Also if pack1 and pack2 were created with depth limit of 3 and we
> are repacking with depth limit of 2, then we are busting the limit
> already with or without cross-pack chaining, I would think.

Right, though that is at least bounded to "what you packed with before", which people do not usually change (OTOH, we accept packs from random strangers via the protocol).

-Peff