Subject: Re: [PATCH] sha1_file: remove recursion in packed_object_info

From: thomas <[email-masked]>
Date: Mon, 25 Mar 2013 10:27:16 +0100

Junio C Hamano <[email-masked]> writes:

> Thomas Rast <[email-masked]> writes:
>
>> So here's a nonrecursive version.  Dijkstra is probably turning over
>> in his grave as we speak.
>>
>> I *think* I actually got it right.
>
> You seem to have lost the "if we cannot get delta base, this object
> is BAD" check where you measure the size of a deltified object,
> which would correspond to this check:
>
>> -static int packed_delta_info(struct packed_git *p,
>> -			     struct pack_window **w_curs,
>> -			     off_t curpos,
>> -			     enum object_type type,
>> -			     off_t obj_offset,
>> -			     unsigned long *sizep)
>> -{
>> -	off_t base_offset;
>> -
>> -	base_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);
>> -	if (!base_offset)
>> -		return OBJ_BAD;

True, I'll think about this.

> The following comment is also lost but...
>
>> -	/* We choose to only get the type of the base object and
>> -	 * ignore potentially corrupt pack file that expects the delta
>> -	 * based on a base with a wrong size.  This saves tons of
>> -	 * inflate() calls.
>> -	 */
>> -	if (sizep) {
>> -		*sizep = get_size_from_delta(p, w_curs, curpos);
>> -		if (*sizep == 0)
>> -			type = OBJ_BAD;
>
> ... is this check correct?  There is an equivalent check at the
> beginning of the new packed_object_info() to error out a deltified
> result.  Why is an object whose size is 0 bad?

Cc'ing Nicolas, but I think there are several reasons:

If it's a delta, then according to docs[1] it starts with the SHA1 of
the base object, plus the deflated data.  So it is at least 20 bytes.

If it's not a delta, then it must start with '<type> <size>\0', which
even after compression cannot possibly be 0 bytes.

Either way, get_size_from_delta() also uses 0 as the error return.

> The stack/recursion is used _only_ for error recovery, no?  If we do
> not care about retrying with a different copy of an object we find
> in the delta chain, we can just update obj_offset with base_offset
> and keep digging.  It almost makes me wonder if a logical follow-up
> to this patch may be to do so, and rewrite the error recovery
> codepath to just mark the bad copy and jump back to the very top,
> retrying everything from scratch.

I totally agree.  I'll try this again -- my last attempt just didn't
work out...

[1]  Documentation/technical/pack-format.txt

-- 
Thomas Rast
trast@{inf,student}.ethz.ch