Re: [PATCH] sha1_file: remove recursion in packed_object_info
- From
Junio C Hamano <gitster@pobox.com>
- Date
- Mar 20, 2013, 16:47 UTC
- Message-ID
- <7vtxo6f27l.fsf@alter.siamese.dyndns.org>
- In-Reply-To
- <c5fc1d2040544965ad3cc09e7b82b6013f06b7fa.1363729774.git.trast@student.ethz.ch>
Thomas Rast <trast@student.ethz.ch> 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:
Show 12 quoted lines
> -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;The following comment is also lost but...
Show 9 quoted lines
> - /* 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?
This comes from 3d77d8774fc1 (make packed_object_info() resilient to pack corruptions, 2008-10-29), and I tend to trust Nico more than I do myself. I must be missing something obvious, but it appears to me that the only thing that keeps us from triggering a false positive is that we do not even attempt to deltify anything smaller than 50 bytes, and create_delta() refuses to create a delta to produce an empty data. But a hand-crafted packfile could certainly record such a delta, no?
Show 10 quoted lines
> The task of the two functions is not all that hard to describe without > any recursion, however. It proceeds in three steps: > > - determine the representation type and size, based on the outermost > object (delta or not) > > - follow through the delta chain, if any > > - determine the object type from what is found at the end of the delta > chain
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. Eventually we would run out bad copies of the problematic object and would report an error, or find a good copy and return the type.