Re: [PATCH] Avoid infinite loop in malformed packfiles

From: Jeff King <peff@peff.net>
Date: Aug 31, 2020, 19:23 UTC
Message-ID: <20200831192302.GA2819760@coredump.intra.peff.net>
In-Reply-To: <xmqqk0xehj38.fsf@gitster.c.googlers.com>

On Mon, Aug 31, 2020 at 09:32:27AM -0700, Junio C Hamano wrote:

Show 12 quoted lines

> > A related point is that delta chains might be composed of both types. If
> > we don't differentiate between the two types, then the limit is clearly
> > total chain length. If we do, then is the limit the total number of
> > ref-deltas found in the current lookup, or is it the number of
> > consecutive ref-deltas? I guess it would have to be the former if our
> > goal is to catch cycles (since a cycle could include an ofs-delta, as
> > long as a ref-delta is the part that forms the loop).
> 
> Ah, OK, you've thought about it already.
> 
> I wonder we can just count both and limit the chain length to the
> total number of objects in the pack we are currently looking at?

That's an interesting suggestion. Within a single pack, it does prevent cycles, and it does so without needing a separate knob, which is nice.

As you note, it only works as long as packs aren't thin. That shouldn't matter for the current scheme (where all on-disk packs are self-contained with respect to deltas), but I do wonder if we'll eventually want to support on-disk thin packs (coupled with a multi-pack-index, that eliminates most of the reason that one needs repack existing objects; it's probably a necessary step in scaling to repos with hundreds of millions of objects). We could still auto-bound it with the total number of packed objects in the repository, though.

Show 6 quoted lines

> It
> guarantees to catch any cycle as long as pack is not thin, but is
> that too lenient and likely to bust the stack while counting?  On
> the other side of the coin, we saw 10000 as a hard-coded limit in
> the patch, but do we know 10000 is low enough that most boxes have
> no trouble recursing that deep?

I don't think we have to worry about stack size. We already ran into stack-busting problems with non-broken cases. ;) That led to 790d96c023 (sha1_file: remove recursion in packed_object_info, 2013-03-25) using its own stack.

I do wonder about CPU, though. We might have tens of millions of objects in a single pack file. How long does it take to convince ourselves we're cycling (even if the cycle itself might only involve a handful of objects)? I'm not sure we care too much about this being a fast operation (after all, the point is that it should never happen and we're just trying not to spin forever). But if it takes 60 minutes to detect the cycle, from a user's perspective that might not be any different than an infinite loop.

-Peff