regression in multi-threaded git-pack-index

regression in multi-threaded git-pack-index

[Stefan Zager]

We have uncovered a regression in this commit:

b8a2486f1524947f232f657e9f2ebf44e3e7a243

The symptom is that 'git fetch' dies with:

error: index-pack died of signal 10
fatal: index-pack failed

I have only been able to reproduce it on a Mac thus far; will try ubuntu next.  We can make it go away by running:

git config pack.threads 1

To reproduce it, download this working copy:

http://commondatastorage.googleapis.com/chromium-browser-snapshots/tmp/src.git.tar.gz

Then:

tar xvfz src.git.tar.gz
cd src.git
git fetch origin refs/heads/lkgr

(That is the shortest reproduction I could come up with; sorry).

Thanks,

Stefan

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:

> We have uncovered a regression in this commit:
> 
> b8a2486f1524947f232f657e9f2ebf44e3e7a243
> 
> The symptom is that 'git fetch' dies with:
> 
> error: index-pack died of signal 10
> fatal: index-pack failed
> 
> I have only been able to reproduce it on a Mac thus far; will try
> ubuntu next.  We can make it go away by running:
> 
> git config pack.threads 1

I couldn't reproduce the problem on Linux with the instructions you
gave. I did try running it under valgrind and it produced:

  ==2380== Conditional jump or move depends on uninitialised value(s)
  ==2380==    at 0x441631: resolve_delta (index-pack.c:837)
  ==2380==    by 0x4419D6: find_unresolved_deltas_1 (index-pack.c:898)
  ==2380==    by 0x441A45: find_unresolved_deltas (index-pack.c:914)
  ==2380==    by 0x4427CA: fix_unresolved_deltas (index-pack.c:1232)
  ==2380==    by 0x4421F5: conclude_pack (index-pack.c:1111)
  ==2380==    by 0x443A5C: cmd_index_pack (index-pack.c:1604)
  ==2380==    by 0x4058A2: run_builtin (git.c:281)
  ==2380==    by 0x405A35: handle_internal_command (git.c:443)
  ==2380==    by 0x405C01: main (git.c:532)

but the line in question is:

  if (deepest_delta < delta_obj->delta_depth)

And in the debugger, both of those variables appear to have sane values
(nor should either impacted by the patch you bisected to). On top of
that, running with pack.threads=1 produces the same error. So I think it
may be a false positive from valgrind, and unrelated to your issue.

Other than that, it seems to run fine for me.

-Peff

Re: regression in multi-threaded git-pack-index

[Duy Nguyen]

On Sat, Mar 16, 2013 at 6:41 PM, Jeff King <peff@peff.net> wrote:
> On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:
>
>> We have uncovered a regression in this commit:
>>
>> b8a2486f1524947f232f657e9f2ebf44e3e7a243

What version did you test? We used to have problems with multithreaded
index-pack on cywgin because its pread implementation is not
thread-safe, see c0f8654 (index-pack: Disable threading on cygwin -
2012-06-26). Not sure if we fall into the same path on Mac, or this is
something else..

>>
>> The symptom is that 'git fetch' dies with:
>>
>> error: index-pack died of signal 10
>> fatal: index-pack failed

I guess it won't help much, but what if you enable coredump and get a
stack trace from it?

>>
>> I have only been able to reproduce it on a Mac thus far; will try
>> ubuntu next.  We can make it go away by running:
>>
>> git config pack.threads 1
-- 
Duy

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

Jeff King <peff@peff.net> writes:

> On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:
>
>> We have uncovered a regression in this commit:
>> 
>> b8a2486f1524947f232f657e9f2ebf44e3e7a243
>> 
>> The symptom is that 'git fetch' dies with:
>> 
>> error: index-pack died of signal 10
>> fatal: index-pack failed
>> 
>> I have only been able to reproduce it on a Mac thus far; will try
>> ubuntu next.  We can make it go away by running:
>> 
>> git config pack.threads 1
>
> I couldn't reproduce the problem on Linux with the instructions you
> gave. I did try running it under valgrind and it produced:
>
>   ==2380== Conditional jump or move depends on uninitialised value(s)
>   ==2380==    at 0x441631: resolve_delta (index-pack.c:837)
>   ==2380==    by 0x4419D6: find_unresolved_deltas_1 (index-pack.c:898)
>   ==2380==    by 0x441A45: find_unresolved_deltas (index-pack.c:914)
>   ==2380==    by 0x4427CA: fix_unresolved_deltas (index-pack.c:1232)
>   ==2380==    by 0x4421F5: conclude_pack (index-pack.c:1111)
>   ==2380==    by 0x443A5C: cmd_index_pack (index-pack.c:1604)
>   ==2380==    by 0x4058A2: run_builtin (git.c:281)
>   ==2380==    by 0x405A35: handle_internal_command (git.c:443)
>   ==2380==    by 0x405C01: main (git.c:532)
>
> but the line in question is:
>
>   if (deepest_delta < delta_obj->delta_depth)
>
> And in the debugger, both of those variables appear to have sane values
> (nor should either impacted by the patch you bisected to). On top of
> that, running with pack.threads=1 produces the same error. So I think it
> may be a false positive from valgrind, and unrelated to your issue.

I find that somewhat unlikely, for two reasons: memcheck is actually
quite good at finding uninitialized memory use, it just isn't that good
at distinguishing if it makes a difference.  Most false positives are of
the "loading an entire word and discarding most of it" kind.

Second, the thread-debugging valgrind tools (drd and helgrind) also
complain about exactly this line:

DRD says:

  ==20987== Thread 4:
  ==20987== Conflicting load by thread 4 at 0x007a70d0 size 4
  ==20987==    at 0x43A783: resolve_delta (index-pack.c:837)
  ==20987==    by 0x43A94F: find_unresolved_deltas (index-pack.c:898)
  ==20987==    by 0x43B0F8: threaded_second_pass (index-pack.c:945)
  ==20987==    by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)
  ==20987==    by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)
  ==20987== Allocation context: BSS section of /home/thomas/.local/bin/git
  ==20987== Other segment start (thread 2)
  ==20987==    at 0x4C30A1F: pthread_mutex_unlock (drd_pthread_intercepts.c:665)
  ==20987==    by 0x43B06E: threaded_second_pass (index-pack.c:122)
  ==20987==    by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)
  ==20987==    by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)
  ==20987== Other segment end (thread 2)
  ==20987==    at 0x5436AE3: ??? (in /lib64/libpthread-2.15.so)
  ==20987==    by 0x439C76: unpack_data.constprop.8 (index-pack.c:528)
  ==20987==    by 0x439EA7: get_base_data (index-pack.c:571)
  ==20987==    by 0x43A7B4: resolve_delta (index-pack.c:841)
  ==20987==    by 0x43A94F: find_unresolved_deltas (index-pack.c:898)
  ==20987==    by 0x43B0F8: threaded_second_pass (index-pack.c:945)
  ==20987==    by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)
  ==20987==    by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)


helgrind says:

  ==21160== Possible data race during read of size 4 at 0x7A70D0 by thread #3
  ==21160== Locks held: none
  ==21160==    at 0x43A783: resolve_delta (index-pack.c:837)
  ==21160==    by 0x43A94F: find_unresolved_deltas (index-pack.c:898)
  ==21160==    by 0x43B0F8: threaded_second_pass (index-pack.c:945)
  ==21160==    by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)
  ==21160==    by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)
  ==21160== 
  ==21160== This conflicts with a previous write of size 4 by thread #2
  ==21160== Locks held: none
  ==21160==    at 0x43A78E: resolve_delta (index-pack.c:838)
  ==21160==    by 0x43A94F: find_unresolved_deltas (index-pack.c:898)
  ==21160==    by 0x43B0F8: threaded_second_pass (index-pack.c:945)
  ==21160==    by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)
  ==21160==    by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)


You were apparently just lucky in catching it before it was even
initialized.

I can reproduce the above warnings with

  valgrind --tool=helgrind --trace-children=yes git index-pack <any_pack>

i.e., it does not seem to depend on the pack (sample size 3, packs
looked at were from my git.git).

Duy, what was the reasoning why resolve_delta() does not need to hold
locks when it looks when it looks at deepest_delta?  My coffee levels
aren't up to this task yet.  It certainly seems extremely dubious to me,
as the code uses the global deepest_delta in threaded sections.  You can
probably argue that the load/store is atomic on most(?) platforms, but
you get no guarantees that deepest_delta at any time in fact holds the
maximum value of delta_obj->delta_depth.


Furthermore there's another warning shown by helgrind:

  ==21160== Possible data race during write of size 4 at 0x7A7060 by thread #2
  ==21160== Locks held: 1, at address 0x7A70E0
  ==21160==    at 0x43A840: resolve_delta (index-pack.c:853)
  ==21160==    by 0x43A94F: find_unresolved_deltas (index-pack.c:898)
  ==21160==    by 0x43B0F8: threaded_second_pass (index-pack.c:945)
  ==21160==    by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)
  ==21160==    by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)
  ==21160== 
  ==21160== This conflicts with a previous read of size 4 by thread #3
  ==21160== Locks held: 1, at address 0x7A7080
  ==21160==    at 0x43AFC8: threaded_second_pass (index-pack.c:955)
  ==21160==    by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)
  ==21160==    by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)

That one really seems to be a false positive in the sense that
threaded_second_pass() doesn't really care if it gets a bad value for
nr_resolved_deltas.  The only thing that matters is that the counter
increment is done with counter_mutex held.

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

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 09:17:32AM +0100, Thomas Rast wrote:

> > but the line in question is:
> >
> >   if (deepest_delta < delta_obj->delta_depth)
> >
> > And in the debugger, both of those variables appear to have sane values
> > (nor should either impacted by the patch you bisected to). On top of
> > that, running with pack.threads=1 produces the same error. So I think it
> > may be a false positive from valgrind, and unrelated to your issue.
> 
> I find that somewhat unlikely, for two reasons: memcheck is actually
> quite good at finding uninitialized memory use, it just isn't that good
> at distinguishing if it makes a difference.  Most false positives are of
> the "loading an entire word and discarding most of it" kind.

Yes, that has been my experience with valgrind false positives, too. But
if this is a real problem, it may be different from the OP's issue. It
seems to trigger for me in v1.7.10, before Duy's threading patches. It
does not seem to be in v1.7.5. I'm bisecting now.

-Peff

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 05:30:34AM -0400, Jeff King wrote:

> On Tue, Mar 19, 2013 at 09:17:32AM +0100, Thomas Rast wrote:
> 
> > > but the line in question is:
> > >
> > >   if (deepest_delta < delta_obj->delta_depth)
> > >
> > > And in the debugger, both of those variables appear to have sane values
> > > (nor should either impacted by the patch you bisected to). On top of
> > > that, running with pack.threads=1 produces the same error. So I think it
> > > may be a false positive from valgrind, and unrelated to your issue.
> > 
> > I find that somewhat unlikely, for two reasons: memcheck is actually
> > quite good at finding uninitialized memory use, it just isn't that good
> > at distinguishing if it makes a difference.  Most false positives are of
> > the "loading an entire word and discarding most of it" kind.
> 
> Yes, that has been my experience with valgrind false positives, too. But
> if this is a real problem, it may be different from the OP's issue. It
> seems to trigger for me in v1.7.10, before Duy's threading patches. It
> does not seem to be in v1.7.5. I'm bisecting now.

Hmph. It bisects to Junio's d1a0ed1 (index-pack: show histogram when
emulating "verify-pack -v", 2011-06-03), which introduces those lines.
The deepest_delta variable is static, so by definition it is always
initialized to something. So I guess some objects may not have
delta_depth set. Still looking.

-Peff

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 05:59:43AM -0400, Jeff King wrote:

> > Yes, that has been my experience with valgrind false positives, too. But
> > if this is a real problem, it may be different from the OP's issue. It
> > seems to trigger for me in v1.7.10, before Duy's threading patches. It
> > does not seem to be in v1.7.5. I'm bisecting now.
> 
> Hmph. It bisects to Junio's d1a0ed1 (index-pack: show histogram when
> emulating "verify-pack -v", 2011-06-03), which introduces those lines.
> The deepest_delta variable is static, so by definition it is always
> initialized to something. So I guess some objects may not have
> delta_depth set. Still looking.

I'm doubly confused now. The commit in question introduces this:

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index aa3c9c6..ed4c3bb 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -70,6 +70,7 @@ static off_t consumed_bytes;
 static unsigned char input_buffer[4096];
 static unsigned int input_offset, input_len;
 static off_t consumed_bytes;
+static unsigned deepest_delta;
 static git_SHA_CTX input_ctx;
 static uint32_t input_crc32;
 static int input_fd, output_fd, pack_fd;
@@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,
 
 	delta_obj->real_type = base->obj->real_type;
 	delta_obj->delta_depth = base->obj->delta_depth + 1;
+	if (deepest_delta < delta_obj->delta_depth)
+		deepest_delta = delta_obj->delta_depth;
 	delta_obj->base_object_no = base->obj - objects;
 	delta_data = get_data_from_pack(delta_obj);
 	base_data = get_base_data(base);

and valgrind reports an uninitialized value in the conditional. But we
can see that deepest_delta is static, and therefore always has some
value. And delta_obj->delta_depth is set in the line above. So both
should have some known value, unless they are computed from unknown
values. In that case, shouldn't valgrind have previously noticed when we
accessed those unknown values?

-Peff

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 06:08:00AM -0400, Jeff King wrote:

> @@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,
>  
>  	delta_obj->real_type = base->obj->real_type;
>  	delta_obj->delta_depth = base->obj->delta_depth + 1;
> +	if (deepest_delta < delta_obj->delta_depth)
> +		deepest_delta = delta_obj->delta_depth;
>  	delta_obj->base_object_no = base->obj - objects;
>  	delta_data = get_data_from_pack(delta_obj);
>  	base_data = get_base_data(base);
> 
> and valgrind reports an uninitialized value in the conditional. But we
> can see that deepest_delta is static, and therefore always has some
> value. And delta_obj->delta_depth is set in the line above. So both
> should have some known value, unless they are computed from unknown
> values. In that case, shouldn't valgrind have previously noticed when we
> accessed those unknown values?

Ah, indeed. Putting:

  fprintf(stderr, "%lu\n", base->obj->delta_depth);

before the conditional reveals that base->obj->delta_depth is
uninitialized, which is the real problem. I'm sure there is some
perfectly logical explanation for why valgrind can't detect its use
during the assignment, but I'm not sure what it is.

At any rate, doing this:

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index ed4c3bb..73686af 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -538,6 +538,8 @@ static void resolve_delta(struct object_entry *delta_obj,
 	void *base_data, *delta_data;
 
 	delta_obj->real_type = base->obj->real_type;
+	if (!is_delta_type(base->obj->type))
+		base->obj->delta_depth = 0;
 	delta_obj->delta_depth = base->obj->delta_depth + 1;
 	if (deepest_delta < delta_obj->delta_depth)
 		deepest_delta = delta_obj->delta_depth;

makes the warning go away. It looks like the delta_depth value was
introduced in 38a4556 (index-pack: start learning to emulate
"verify-pack -v", 2011-06-03), and it used only for showing the chain
depths with --verify-stat. So it is almost certainly not related to
Stefan's original problem, but it does mean we've probably been
computing bogus chain lengths.

There may be a more reasonable place to set base->obj->delta_depth than
right here; I'll see if I can cook up a real patch.

-Peff

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

Jeff King <peff@peff.net> writes:

> On Tue, Mar 19, 2013 at 06:08:00AM -0400, Jeff King wrote:
>
>> @@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,
>>  
>>  	delta_obj->real_type = base->obj->real_type;
>>  	delta_obj->delta_depth = base->obj->delta_depth + 1;
>> +	if (deepest_delta < delta_obj->delta_depth)
>> +		deepest_delta = delta_obj->delta_depth;
>>  	delta_obj->base_object_no = base->obj - objects;
>>  	delta_data = get_data_from_pack(delta_obj);
>>  	base_data = get_base_data(base);
>> 
>> and valgrind reports an uninitialized value in the conditional. But we
>> can see that deepest_delta is static, and therefore always has some
>> value. And delta_obj->delta_depth is set in the line above. So both
>> should have some known value, unless they are computed from unknown
>> values. In that case, shouldn't valgrind have previously noticed when we
>> accessed those unknown values?
>
> Ah, indeed. Putting:
>
>   fprintf(stderr, "%lu\n", base->obj->delta_depth);
>
> before the conditional reveals that base->obj->delta_depth is
> uninitialized, which is the real problem. I'm sure there is some
> perfectly logical explanation for why valgrind can't detect its use
> during the assignment, but I'm not sure what it is.

That's simply because you would get far too much noise.  It only reports
an uninitialized value when it actually gets used in a conditional or
for output (syscalls), which is when they matter.

You can use --track-origins=yes to see where the undefined value came
from, but it's veeeery slow.

> It looks like the delta_depth value was
> introduced in 38a4556 (index-pack: start learning to emulate
> "verify-pack -v", 2011-06-03), and it used only for showing the chain
> depths with --verify-stat. So it is almost certainly not related to
> Stefan's original problem, but it does mean we've probably been
> computing bogus chain lengths.

Nice catch!

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

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 11:29:36AM +0100, Thomas Rast wrote:

> > Ah, indeed. Putting:
> >
> >   fprintf(stderr, "%lu\n", base->obj->delta_depth);
> >
> > before the conditional reveals that base->obj->delta_depth is
> > uninitialized, which is the real problem. I'm sure there is some
> > perfectly logical explanation for why valgrind can't detect its use
> > during the assignment, but I'm not sure what it is.
> 
> That's simply because you would get far too much noise.  It only reports
> an uninitialized value when it actually gets used in a conditional or
> for output (syscalls), which is when they matter.

Would it? I would think any computation you start with an undefined
value would be suspect (and you would want to know about it as soon as
possible, before the tainted value gets output). I was assuming it was a
performance issue or something.

> You can use --track-origins=yes to see where the undefined value came
> from, but it's veeeery slow.

It's pretty slow either way. :) I do have --track-origins on, but the
origin is this:

  objects = xrealloc(objects,
                     (nr_objects + nr_unresolved + 1)
                     * sizeof(*objects));

which is not very helpful. It's _somewhere_ in the list of objects...:)

-Peff

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

Jeff King <peff@peff.net> writes:

> On Tue, Mar 19, 2013 at 11:29:36AM +0100, Thomas Rast wrote:
>
>> > Ah, indeed. Putting:
>> >
>> >   fprintf(stderr, "%lu\n", base->obj->delta_depth);
>> >
>> > before the conditional reveals that base->obj->delta_depth is
>> > uninitialized, which is the real problem. I'm sure there is some
>> > perfectly logical explanation for why valgrind can't detect its use
>> > during the assignment, but I'm not sure what it is.
>> 
>> That's simply because you would get far too much noise.  It only reports
>> an uninitialized value when it actually gets used in a conditional or
>> for output (syscalls), which is when they matter.
>
> Would it? I would think any computation you start with an undefined
> value would be suspect (and you would want to know about it as soon as
> possible, before the tainted value gets output). I was assuming it was a
> performance issue or something.

Now consider

  // somewhere on the stack
  struct foo {
    char c;
    int i;
  } a, b;
  a.c = a.i = 0;

  memcpy(&b, &a, sizeof(struct foo));

The compiler could legitimately leave the padding between c and i
uninitialized, and with your proposed "early" reporting the memcpy would
complain.

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

Re: regression in multi-threaded git-pack-index

[Jeff King]

On Tue, Mar 19, 2013 at 11:45:56AM +0100, Thomas Rast wrote:

> Now consider
> 
>   // somewhere on the stack
>   struct foo {
>     char c;
>     int i;
>   } a, b;
>   a.c = a.i = 0;
> 
>   memcpy(&b, &a, sizeof(struct foo));
> 
> The compiler could legitimately leave the padding between c and i
> uninitialized, and with your proposed "early" reporting the memcpy would
> complain.

Ah, good point. And valgrind does not have any way of knowing what is
padding and what is not, since it sees only the compiled contents.
Probably llvm's memory checker support could do a better job there.

-Peff

[PATCH] index-pack: always zero-initialize object_entry list

[Jeff King]

Commit 38a4556 (index-pack: start learning to emulate
"verify-pack -v", 2011-06-03) added a "delta_depth" counter
to each "struct object_entry". Initially, all object entries
have their depth set to 0; in resolve_delta, we then set the
depth of each delta to "base + 1". Base entries never have
their depth touched, and remain at 0.

To ensure that all depths start at 0, that commit changed
calls to xmalloc the object_entry list into calls to
xcalloc.  However, it forgot that we grow the list with
xrealloc later. These extra entries are used when we add an
object from elsewhere pack to complete a thin pack. If we
add a non-delta object, its depth value will just be
uninitialized heap data.

This patch fixes it by zero-initializing entries we add to
the objects list via the xrealloc.

Signed-off-by: Jeff King <peff@peff.net>
---
Another solution would be to say "only look at delta_depth
if the object is a delta"; we follow that rule already in
the output histogram code path, but just do not when
checking a delta's base. So it would similarly be a
one-liner.  But I think given the switch to xcalloc in the
original patch, the intent was to just always zero each
object, as I described above.

This would be more readable if we had an "xrecalloc" or
similar, which realloc'd a pointer and set just the _new_
space to zeros. I do not recall ever hearing of such a
function, though. I figured since it is a one-off, it is
simpler to just say what we mean with memset here than
invent a new allocation function that will leave people
scratching their heads about its semantics.

 builtin/index-pack.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 43d364b..ca62443 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -1107,6 +1107,8 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha
 		objects = xrealloc(objects,
 				   (nr_objects + nr_unresolved + 1)
 				   * sizeof(*objects));
+		memset(objects + nr_objects, 0,
+		       (nr_unresolved + 1) * sizeof(*objects));
 		f = sha1fd(output_fd, curr_pack);
 		fix_unresolved_deltas(f, nr_unresolved);
 		sprintf(msg, _("completed with %d local objects"),
-- 
1.8.2.4.g2ed830d

Re: regression in multi-threaded git-pack-index

[Duy Nguyen]

On Tue, Mar 19, 2013 at 3:17 PM, Thomas Rast <trast@student.ethz.ch> wrote:
>> but the line in question is:
>>
>>   if (deepest_delta < delta_obj->delta_depth)
>>
>...
>
> Duy, what was the reasoning why resolve_delta() does not need to hold
> locks when it looks when it looks at deepest_delta?  My coffee levels
> aren't up to this task yet.  It certainly seems extremely dubious to me,
> as the code uses the global deepest_delta in threaded sections.  You can
> probably argue that the load/store is atomic on most(?) platforms, but
> you get no guarantees that deepest_delta at any time in fact holds the
> maximum value of delta_obj->delta_depth.

Now that I have had dinner (and energy restored), the explanation
might be because I missed it. resolve_delta() deals with data in
delta_obj and does not share global state, except this one and
nr_resolved_deltas. The latter is protected. I guess we could protect
this one with a mutex. But only do so when "--verify" is specified

if (stat) {
   lock();
   if (deepest_delta < delta_obj->delta_depth)
      deepest_delta = delta_obj->delta_depth;
   unlock();
}

so that we don't need to hold/release lock when index-pack is run.
-- 
Duy

[PATCH] index-pack: protect deepest_delta in multithread code

[Nguyễn Thái Ngọc Duy]

deepest_delta is a global variable but is updated without protection
in resolve_delta(), a multithreaded function. Add a new mutex for it,
but only protect and update when it's actually used (i.e. show_stat is
non-zero).

Another variable that will not be updated is delta_depth in "struct
object_entry" as it's only useful when show_stat is 1. Putting it in
"if (show_stat)" makes it clearer.

The local variable "stat" is renamed to "show_stat" after moving to
global scope because the name "stat" conflicts with stat(2) syscall.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin/index-pack.c | 30 +++++++++++++++++++++++-------
 1 file changed, 23 insertions(+), 7 deletions(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 43d364b..9cfd6e7 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -78,6 +78,7 @@ static int nr_threads;
 static int from_stdin;
 static int strict;
 static int verbose;
+static int show_stat;
 
 static struct progress *progress;
 
@@ -108,6 +109,10 @@ static pthread_mutex_t work_mutex;
 #define work_lock()		lock_mutex(&work_mutex)
 #define work_unlock()		unlock_mutex(&work_mutex)
 
+static pthread_mutex_t deepest_delta_mutex;
+#define deepest_delta_lock()	lock_mutex(&deepest_delta_mutex)
+#define deepest_delta_unlock()	unlock_mutex(&deepest_delta_mutex)
+
 static pthread_key_t key;
 
 static inline void lock_mutex(pthread_mutex_t *mutex)
@@ -130,6 +135,8 @@ static void init_thread(void)
 	init_recursive_mutex(&read_mutex);
 	pthread_mutex_init(&counter_mutex, NULL);
 	pthread_mutex_init(&work_mutex, NULL);
+	if (show_stat)
+		pthread_mutex_init(&deepest_delta_mutex, NULL);
 	pthread_key_create(&key, NULL);
 	thread_data = xcalloc(nr_threads, sizeof(*thread_data));
 	threads_active = 1;
@@ -143,6 +150,8 @@ static void cleanup_thread(void)
 	pthread_mutex_destroy(&read_mutex);
 	pthread_mutex_destroy(&counter_mutex);
 	pthread_mutex_destroy(&work_mutex);
+	if (show_stat)
+		pthread_mutex_destroy(&deepest_delta_mutex);
 	pthread_key_delete(key);
 	free(thread_data);
 }
@@ -158,6 +167,9 @@ static void cleanup_thread(void)
 #define work_lock()
 #define work_unlock()
 
+#define deepest_delta_lock()
+#define deepest_delta_unlock()
+
 #endif
 
 
@@ -833,9 +845,13 @@ static void resolve_delta(struct object_entry *delta_obj,
 	void *base_data, *delta_data;
 
 	delta_obj->real_type = base->obj->real_type;
-	delta_obj->delta_depth = base->obj->delta_depth + 1;
-	if (deepest_delta < delta_obj->delta_depth)
-		deepest_delta = delta_obj->delta_depth;
+	if (show_stat) {
+		delta_obj->delta_depth = base->obj->delta_depth + 1;
+		deepest_delta_lock();
+		if (deepest_delta < delta_obj->delta_depth)
+			deepest_delta = delta_obj->delta_depth;
+		deepest_delta_unlock();
+	}
 	delta_obj->base_object_no = base->obj - objects;
 	delta_data = get_data_from_pack(delta_obj);
 	base_data = get_base_data(base);
@@ -1462,7 +1478,7 @@ static void show_pack_info(int stat_only)
 
 int cmd_index_pack(int argc, const char **argv, const char *prefix)
 {
-	int i, fix_thin_pack = 0, verify = 0, stat_only = 0, stat = 0;
+	int i, fix_thin_pack = 0, verify = 0, stat_only = 0;
 	const char *curr_pack, *curr_index;
 	const char *index_name = NULL, *pack_name = NULL;
 	const char *keep_name = NULL, *keep_msg = NULL;
@@ -1495,10 +1511,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 				verify = 1;
 			} else if (!strcmp(arg, "--verify-stat")) {
 				verify = 1;
-				stat = 1;
+				show_stat = 1;
 			} else if (!strcmp(arg, "--verify-stat-only")) {
 				verify = 1;
-				stat = 1;
+				show_stat = 1;
 				stat_only = 1;
 			} else if (!strcmp(arg, "--keep")) {
 				keep_msg = "";
@@ -1606,7 +1622,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)
 	if (strict)
 		check_objects();
 
-	if (stat)
+	if (show_stat)
 		show_pack_info(stat_only);
 
 	idx_objects = xmalloc((nr_objects) * sizeof(struct pack_idx_entry *));
-- 
1.8.2.83.gc99314b

Re: [PATCH] index-pack: protect deepest_delta in multithread code

[Jeff King]

On Tue, Mar 19, 2013 at 08:01:15PM +0700, Nguyen Thai Ngoc Duy wrote:

> deepest_delta is a global variable but is updated without protection
> in resolve_delta(), a multithreaded function. Add a new mutex for it,
> but only protect and update when it's actually used (i.e. show_stat is
> non-zero).

This makes sense to me.

> Another variable that will not be updated is delta_depth in "struct
> object_entry" as it's only useful when show_stat is 1. Putting it in
> "if (show_stat)" makes it clearer.

Having just read through this code for the first time, I agree that
having the "if (show_stat)" would have made it a lot more clear under
what conditions and for what purpose the delta_depth flag was being
used.

>  builtin/index-pack.c | 30 +++++++++++++++++++++++-------
>  1 file changed, 23 insertions(+), 7 deletions(-)

Patch looks good to me. Thanks.

-Peff

Re: [PATCH] index-pack: protect deepest_delta in multithread code

[Thomas Rast]

Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:

> deepest_delta is a global variable but is updated without protection
> in resolve_delta(), a multithreaded function. Add a new mutex for it,
> but only protect and update when it's actually used (i.e. show_stat is
> non-zero).
>
> Another variable that will not be updated is delta_depth in "struct
> object_entry" as it's only useful when show_stat is 1. Putting it in
> "if (show_stat)" makes it clearer.
>
> The local variable "stat" is renamed to "show_stat" after moving to
> global scope because the name "stat" conflicts with stat(2) syscall.

Looks good to me, too.  However, I think it would still be less magical
if we had the below too.  It also silences helgrind.

-- >8 --
Subject: [PATCH] index-pack: guard nr_resolved_deltas reads by lock

The threaded parts of index-pack increment the number of resolved
deltas in nr_resolved_deltas guarded by counter_mutex.  However, the
per-thread outer loop accessed nr_resolved_deltas without any locks.

This is not wrong as such, since it doesn't matter all that much
whether we get an outdated value.  However, unless someone proves that
this one lock makes all the performance difference, it would be much
cleaner to guard _all_ accesses to the variable with the lock.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 builtin/index-pack.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index b3fee45..6be99e2 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -968,7 +968,9 @@ static void *threaded_second_pass(void *data)
 	for (;;) {
 		int i;
 		work_lock();
+		counter_lock();
 		display_progress(progress, nr_resolved_deltas);
+		counter_unlock();
 		while (nr_dispatched < nr_objects &&
 		       is_delta_type(objects[nr_dispatched].type))
 			nr_dispatched++;
-- 
1.8.2.487.g725f6bb


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

Re: [PATCH] index-pack: protect deepest_delta in multithread code

[Duy Nguyen]

On Tue, Mar 19, 2013 at 8:50 PM, Thomas Rast <trast@student.ethz.ch> wrote:
> -- >8 --
> Subject: [PATCH] index-pack: guard nr_resolved_deltas reads by lock
>
> The threaded parts of index-pack increment the number of resolved
> deltas in nr_resolved_deltas guarded by counter_mutex.  However, the
> per-thread outer loop accessed nr_resolved_deltas without any locks.
>
> This is not wrong as such, since it doesn't matter all that much
> whether we get an outdated value.  However, unless someone proves that
> this one lock makes all the performance difference, it would be much
> cleaner to guard _all_ accesses to the variable with the lock.
>
> Signed-off-by: Thomas Rast <trast@student.ethz.ch>
> ---
>  builtin/index-pack.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index b3fee45..6be99e2 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -968,7 +968,9 @@ static void *threaded_second_pass(void *data)
>         for (;;) {
>                 int i;
>                 work_lock();
> +               counter_lock();
>                 display_progress(progress, nr_resolved_deltas);
> +               counter_unlock();
>                 while (nr_dispatched < nr_objects &&
>                        is_delta_type(objects[nr_dispatched].type))
>                         nr_dispatched++;

I'm pretty sure futex will make this cheap. The only thing I don't
like here is the double locking (work_lock then counter_lock) is an
invitation for potential deadlocks (not now, but who now what can
change later). I think you could move work_lock(); down after
counter_unlock() so we hold one lock at a time.
-- 
Duy

[PATCH v2] index-pack: guard nr_resolved_deltas reads by lock

[Thomas Rast]

The threaded parts of index-pack increment the number of resolved
deltas in nr_resolved_deltas guarded by counter_mutex.  However, the
per-thread outer loop accessed nr_resolved_deltas without any locks.

This is not wrong as such, since it doesn't matter all that much
whether we get an outdated value.  However, unless someone proves that
this one lock makes all the performance difference, it would be much
cleaner to guard _all_ accesses to the variable with the lock.

The only such use is display_progress() in the threaded section (all
others are in the conclude_pack() callchain outside the threaded
part).  To make it obvious that it cannot deadlock, move it out of
work_mutex.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

> The only thing I don't
> like here is the double locking (work_lock then counter_lock) is an
> invitation for potential deadlocks (not now, but who now what can
> change later). I think you could move work_lock(); down after
> counter_unlock() so we hold one lock at a time.

Good point.


 builtin/index-pack.c | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index b3fee45..a481f54 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -967,8 +967,10 @@ static void *threaded_second_pass(void *data)
 	set_thread_data(data);
 	for (;;) {
 		int i;
-		work_lock();
+		counter_lock();
 		display_progress(progress, nr_resolved_deltas);
+		counter_unlock();
+		work_lock();
 		while (nr_dispatched < nr_objects &&
 		       is_delta_type(objects[nr_dispatched].type))
 			nr_dispatched++;
-- 
1.8.2.490.gc3bbe62

Re: [PATCH] index-pack: always zero-initialize object_entry list

[Thomas Rast]

Jeff King <peff@peff.net> writes:

> Commit 38a4556 (index-pack: start learning to emulate
> "verify-pack -v", 2011-06-03) added a "delta_depth" counter
> to each "struct object_entry". Initially, all object entries
> have their depth set to 0; in resolve_delta, we then set the
> depth of each delta to "base + 1". Base entries never have
> their depth touched, and remain at 0.

This patch causes index-pack to fail on the pack that triggered the
whole discussion.  More in a minute in another side thread, but
meanwhile: NAK until we understand what is really going on here.

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

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

szager@google.com (Stefan Zager) writes:

> We have uncovered a regression in this commit:
>
> b8a2486f1524947f232f657e9f2ebf44e3e7a243
>
> The symptom is that 'git fetch' dies with:
>
> error: index-pack died of signal 10
> fatal: index-pack failed

So after that fun detour into threading issues, I have actually managed
to reproduce this problem on OS X even with the three in-flight patches
already applied.

I reduced the issue to this file:

  http://thomasrast.ch/download/broken-pack

on which you can run this command in the repo that Stefan provided:

  git index-pack --keep --stdin -v --pack_header=2,50757 <broken-pack

I got the file by patching fetch-pack.c to pipe the pack to 'dd
of=broken-pack' instead of index-pack, as I couldn't find any other way
of getting at the data stream before index-pack ruins it.

The funny thing about it is that I get this on OS X:

  $ git index-pack --keep --stdin -v --pack_header=2,50757 <borked
  Receiving objects: 100% (50757/50757), 24.52 MiB | 23.91 MiB/s, done.
  Bus error: 10tas:  24% (10194/42272)

(notice the error) and also

  $ gdb --args $(which git)
  GNU gdb 6.3.50-20050815 (Apple version gdb-1705) (Fri Jul  1 10:50:06 UTC 2011)
  Copyright 2004 Free Software Foundation, Inc.
  GDB is free software, covered by the GNU General Public License, and you are
  welcome to change it and/or distribute copies of it under certain conditions.
  Type "show copying" to see the conditions.
  There is absolutely no warranty for GDB.  Type "show warranty" for details.
  This GDB was configured as "x86_64-apple-darwin"...Reading symbols for shared libraries .... done

  (gdb) r index-pack --keep --stdin -v --pack_header=2,50757 <borked
  Starting program: /Users/trast/.local/bin/git index-pack --keep --stdin -v --pack_header=2,50757 <borked
  Reading symbols for shared libraries +++........................ done
  Receiving objects: 100% (50757/50757), 24.52 MiB | 13.06 MiB/s, done.
  Resolving deltas:  25% (10568/42272)   
  Program received signal EXC_BAD_ACCESS, Could not access memory.
  Reason: KERN_PROTECTION_FAILURE at address: 0x000000014484dfe8
  [Switching to process 96573 thread 0x10f]
  0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0, offset=69638148, left=0x0) at sha1_file.c:866
  866             if (!win || !in_window(win, offset)) {

This seems to be a SIGBUS triggered by stack overflow, largely based on
the observation that

  (gdb) p &p
  $6 = (struct packed_git **) 0x144748058

I can't see anything wrong with the values as such, but if you have good
ideas what I should ask of that debugger, I'm keeping the session
around.

Furthermore, if I run the same command on linux in the provided repo, I
get this instead:

  $ git index-pack --fix-thin --keep --stdin -v --pack_header=2,50757 <../broken-pack
  Receiving objects: 100% (50757/50757), 24.52 MiB | 18.84 MiB/s, done.
  Resolving deltas: 100% (42272/42272), completed with 8264 local objects.
  pack    1cd9880470ea812835edde58e8d7752818dc1ead

But when I do it with Peff's patch applied, I get:

  $ git index-pack --fix-thin --keep --stdin -v --pack_header=2,50757 <../broken-pack
  Empfange Objekte: 100% (50757/50757), 24.52 MiB | 17.92 MiB/s, done.
  git: builtin/index-pack.c:897: find_unresolved_deltas_1: Assertion `child->real_type == OBJ_OFS_DELTA' failed.
  Aborted

I think the patch is probably still good as it stands, but there's some
underlying breakage going on that hides the problem if we don't clear
that memory...

I'm still looking, but I wanted to get this -- and in particular the
pack -- out for you to play with ;-)

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

Re: [PATCH] index-pack: always zero-initialize object_entry list

[Jeff King]

On Tue, Mar 19, 2013 at 04:33:42PM +0100, Thomas Rast wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Commit 38a4556 (index-pack: start learning to emulate
> > "verify-pack -v", 2011-06-03) added a "delta_depth" counter
> > to each "struct object_entry". Initially, all object entries
> > have their depth set to 0; in resolve_delta, we then set the
> > depth of each delta to "base + 1". Base entries never have
> > their depth touched, and remain at 0.
> 
> This patch causes index-pack to fail on the pack that triggered the
> whole discussion.  More in a minute in another side thread, but
> meanwhile: NAK until we understand what is really going on here.

Odd; that's what I was testing with, and it worked fine.

Let me double-check that I didn't screw up my tests. I initially did
something more like:

  if (is_delta_type(base->obj->type))
          delta_obj->delta_depth = base->obj->delta_depth + 1;
  else
          delta_obj->delta_depth = 1;

and I'm wondering if I screwed up testing the revised version.

-Peff

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

Thomas Rast <trast@student.ethz.ch> writes:

>   (gdb) r index-pack --keep --stdin -v --pack_header=2,50757 <borked
>   Starting program: /Users/trast/.local/bin/git index-pack --keep
> --stdin -v --pack_header=2,50757 <borked
>   Reading symbols for shared libraries +++........................ done
>   Receiving objects: 100% (50757/50757), 24.52 MiB | 13.06 MiB/s, done.
>   Resolving deltas:  25% (10568/42272)   
>   Program received signal EXC_BAD_ACCESS, Could not access memory.
>   Reason: KERN_PROTECTION_FAILURE at address: 0x000000014484dfe8
>   [Switching to process 96573 thread 0x10f]
>   0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0,
> offset=69638148, left=0x0) at sha1_file.c:866
>   866             if (!win || !in_window(win, offset)) {
>
> This seems to be a SIGBUS triggered by stack overflow, largely based on
> the observation that
>
>   (gdb) p &p
>   $6 = (struct packed_git **) 0x144748058

Actually, scratch that; the stack depth is the same no matter what
ulimits I put (up to 64MB).  Roughly speaking

  (gdb) bt 10
  #0  0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0, offset=69638148, left=0x0) at sha1_file.c:866
  #1  0x000000010018180c in get_delta_base (p=0x100500f30, w_curs=0x14484e1a0, curpos=0x14484e138, type=OBJ_OFS_DELTA, delta_obj_offset=69638146) at sha1_file.c:1609
  #2  0x00000001001819e6 in packed_delta_info (p=0x100500f30, w_curs=0x14484e1a0, curpos=69638148, type=OBJ_OFS_DELTA, obj_offset=69638146, sizep=0x0) at sha1_file.c:1655
  #3  0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638146, sizep=0x0, rtype=0x0) at sha1_file.c:1727
  #4  0x0000000100181a25 in packed_delta_info (p=0x100500f30, w_curs=0x14484e2a0, curpos=69638193, type=OBJ_OFS_DELTA, obj_offset=69638190, sizep=0x0) at sha1_file.c:1658
  #5  0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638190, sizep=0x0, rtype=0x0) at sha1_file.c:1727
  #6  0x0000000100181a25 in packed_delta_info (p=0x100500f30, w_curs=0x14484e3a0, curpos=69638240, type=OBJ_OFS_DELTA, obj_offset=69638237, sizep=0x0) at sha1_file.c:1658
  #7  0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638237, sizep=0x0, rtype=0x0) at sha1_file.c:1727
  #8  0x0000000100181a25 in packed_delta_info (p=0x100500f30, w_curs=0x14484e4a0, curpos=69638285, type=OBJ_OFS_DELTA, obj_offset=69638282, sizep=0x0) at sha1_file.c:1658
  #9  0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638282, sizep=0x0, rtype=0x0) at sha1_file.c:1727
  (More stack frames follow...)
  (gdb) bt -10
  #4088 0x00000001001835f9 in sha1_object_info_extended (sha1=0x1011b0900 "D=L\022eO����}�r\fW\036F�Q\\Q;t�8", oi=0x1448cdc50) at sha1_file.c:2264
  #4089 0x00000001001836eb in sha1_object_info (sha1=0x1011b0900 "D=L\022eO����}�r\fW\036F�Q\\Q;t�8", sizep=0x1448cdd28) at sha1_file.c:2286
  #4090 0x0000000100053c44 in sha1_object (data=0x146002400, obj_entry=0x0, size=1992, type=OBJ_TREE, sha1=0x1011b0900 "D=L\022eO����}�r\fW\036F�Q\\Q;t�8") at index-pack.c:722
  #4091 0x000000010005457f in resolve_delta (delta_obj=0x1011b0900, base=0x144e00000, result=0x144e00040) at index-pack.c:866
  #4092 0x00000001000548b6 in find_unresolved_deltas_1 (base=0x144e00000, prev_base=0x0) at index-pack.c:914
  #4093 0x0000000100054947 in find_unresolved_deltas (base=0x144e00000) at index-pack.c:930
  #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961
  #4095 0x0000000100054ba5 in threaded_second_pass (data=0x100537dd0) at index-pack.c:984
  #4096 0x00007fff8ec8b8bf in _pthread_start ()
  #4097 0x00007fff8ec8eb75 in thread_start ()

That leaves me stumped as to the cause of that SIGBUS, however.

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

Re: [PATCH] index-pack: always zero-initialize object_entry list

[Jeff King]

On Tue, Mar 19, 2013 at 11:43:53AM -0400, Jeff King wrote:

> On Tue, Mar 19, 2013 at 04:33:42PM +0100, Thomas Rast wrote:
> 
> > Jeff King <peff@peff.net> writes:
> > 
> > > Commit 38a4556 (index-pack: start learning to emulate
> > > "verify-pack -v", 2011-06-03) added a "delta_depth" counter
> > > to each "struct object_entry". Initially, all object entries
> > > have their depth set to 0; in resolve_delta, we then set the
> > > depth of each delta to "base + 1". Base entries never have
> > > their depth touched, and remain at 0.
> > 
> > This patch causes index-pack to fail on the pack that triggered the
> > whole discussion.  More in a minute in another side thread, but
> > meanwhile: NAK until we understand what is really going on here.
> 
> Odd; that's what I was testing with, and it worked fine.

Ah, interesting. I built the fix on top of d1a0ed1, the first commit
that shows the problem. And it works fine there. But when it is
forward-ported to the current master, it breaks as you saw.

More bisection fun.

-Peff

Re: [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> The threaded parts of index-pack increment the number of resolved
> deltas in nr_resolved_deltas guarded by counter_mutex.  However, the
> per-thread outer loop accessed nr_resolved_deltas without any locks.
>
> This is not wrong as such, since it doesn't matter all that much
> whether we get an outdated value.  However, unless someone proves that
> this one lock makes all the performance difference, it would be much
> cleaner to guard _all_ accesses to the variable with the lock.
>
> The only such use is display_progress() in the threaded section (all
> others are in the conclude_pack() callchain outside the threaded
> part).  To make it obvious that it cannot deadlock, move it out of
> work_mutex.
>
> Signed-off-by: Thomas Rast <trast@student.ethz.ch>
> ---
>
>> The only thing I don't
>> like here is the double locking (work_lock then counter_lock) is an
>> invitation for potential deadlocks (not now, but who now what can
>> change later). I think you could move work_lock(); down after
>> counter_unlock() so we hold one lock at a time.
>
> Good point.

Thanks guys for fixing my mess with these two patches.

Re: regression in multi-threaded git-pack-index

[Thomas Rast]

Thomas Rast <trast@student.ethz.ch> writes:

> Thomas Rast <trast@student.ethz.ch> writes:
>
>>   (gdb) r index-pack --keep --stdin -v --pack_header=2,50757 <borked
>>   Starting program: /Users/trast/.local/bin/git index-pack --keep
>> --stdin -v --pack_header=2,50757 <borked
>>   Reading symbols for shared libraries +++........................ done
>>   Receiving objects: 100% (50757/50757), 24.52 MiB | 13.06 MiB/s, done.
>>   Resolving deltas:  25% (10568/42272)   
>>   Program received signal EXC_BAD_ACCESS, Could not access memory.
>>   Reason: KERN_PROTECTION_FAILURE at address: 0x000000014484dfe8
>>   [Switching to process 96573 thread 0x10f]
>>   0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0,
>> offset=69638148, left=0x0) at sha1_file.c:866
>>   866             if (!win || !in_window(win, offset)) {
>>
>> This seems to be a SIGBUS triggered by stack overflow, largely based on
>> the observation that
>>
>>   (gdb) p &p
>>   $6 = (struct packed_git **) 0x144748058
>
> Actually, scratch that; the stack depth is the same no matter what
> ulimits I put (up to 64MB).

Actually scratch that again.  It *is* a stack overflow, except that this
is a thread stack, for which the OS X defaults are 512kB apparently, as
opposed to 2MB on linux.

To wit:

  (gdb) p &p
  $11 = (struct packed_git **) 0x14484e058
  (gdb) bt -5
  #4093 0x0000000100054947 in find_unresolved_deltas (base=0x144e00000) at index-pack.c:930
  #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961
  #4095 0x0000000100054ba5 in threaded_second_pass (data=0x100537dd0) at index-pack.c:984
  #4096 0x00007fff8ec8b8bf in _pthread_start ()
  #4097 0x00007fff8ec8eb75 in thread_start ()
  (gdb) f 4094
  #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961
  961             find_unresolved_deltas(base_obj);
  (gdb) p &obj
  $12 = (struct object_entry **) 0x1448cdec8
  (gdb) p 0x14484e058-0x1448cdec8
  $13 = -523888
  (gdb) p 512*1024
  $14 = 524288

And indeed the following patch fixes it.  Sounds like the delta
unpacking needs a rewrite to support stackless operation.  Sigh.

diff --git i/builtin/index-pack.c w/builtin/index-pack.c
index 6be99e2..f73291f 100644
--- i/builtin/index-pack.c
+++ w/builtin/index-pack.c
@@ -1075,13 +1075,17 @@ static void resolve_deltas(void)
 	nr_dispatched = 0;
 	if (nr_threads > 1 || getenv("GIT_FORCE_THREADS")) {
 		init_thread();
+		pthread_attr_t attr;
+		pthread_attr_init(&attr);
+		pthread_attr_setstacksize(&attr, 2*1024*1024);
 		for (i = 0; i < nr_threads; i++) {
-			int ret = pthread_create(&thread_data[i].thread, NULL,
+			int ret = pthread_create(&thread_data[i].thread, &attr,
 						 threaded_second_pass, thread_data + i);
 			if (ret)
 				die(_("unable to create thread: %s"),
 				    strerror(ret));
 		}
+		pthread_attr_destroy(&attr);
 		for (i = 0; i < nr_threads; i++)
 			pthread_join(thread_data[i].thread, NULL);
 		cleanup_thread();


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

[PATCH v2] index-pack: always zero-initialize object_entry list

[Jeff King]

On Tue, Mar 19, 2013 at 11:52:44AM -0400, Jeff King wrote:

> > > > Commit 38a4556 (index-pack: start learning to emulate
> > > > "verify-pack -v", 2011-06-03) added a "delta_depth" counter
> > > > to each "struct object_entry". Initially, all object entries
> > > > have their depth set to 0; in resolve_delta, we then set the
> > > > depth of each delta to "base + 1". Base entries never have
> > > > their depth touched, and remain at 0.
> > > 
> > > This patch causes index-pack to fail on the pack that triggered the
> > > whole discussion.  More in a minute in another side thread, but
> > > meanwhile: NAK until we understand what is really going on here.
> > 
> > Odd; that's what I was testing with, and it worked fine.
> 
> Ah, interesting. I built the fix on top of d1a0ed1, the first commit
> that shows the problem. And it works fine there. But when it is
> forward-ported to the current master, it breaks as you saw.
> 
> More bisection fun.

So after bisecting, I realize that it is indeed broken on top of
d1a0ed1. I have no idea why I didn't notice that before; I'm guessing it
was because I was running it under valgrind and paying attention only to
valgrind errors.

Anyway, the problem is simple and stupid. The original object array is
not nr_objects item long; it is (nr_objects + 1) long, though I'm not
clear why (1-indexing?). So my previous patch was zeroing the final
entry, which was supposed to contain actual data. Oops.

Here's the corrected patch.

-- >8 --
Subject: [PATCH] index-pack: always zero-initialize object_entry list

Commit 38a4556 (index-pack: start learning to emulate
"verify-pack -v", 2011-06-03) added a "delta_depth" counter
to each "struct object_entry". Initially, all object entries
have their depth set to 0; in resolve_delta, we then set the
depth of each delta to "base + 1". Base entries never have
their depth touched, and remain at 0.

To ensure that all depths start at 0, that commit changed
calls to xmalloc the object_entry list into calls to
xcalloc.  However, it forgot that we grow the list with
xrealloc later. These extra entries are used when we add an
object from elsewhere pack to complete a thin pack. If we
add a non-delta object, its depth value will just be
uninitialized heap data.

This patch fixes it by zero-initializing entries we add to
the objects list via the xrealloc.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/index-pack.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/builtin/index-pack.c b/builtin/index-pack.c
index 43d364b..5860085 100644
--- a/builtin/index-pack.c
+++ b/builtin/index-pack.c
@@ -1107,6 +1107,8 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha
 		objects = xrealloc(objects,
 				   (nr_objects + nr_unresolved + 1)
 				   * sizeof(*objects));
+		memset(objects + nr_objects + 1, 0,
+		       nr_unresolved * sizeof(*objects));
 		f = sha1fd(output_fd, curr_pack);
 		fix_unresolved_deltas(f, nr_unresolved);
 		sprintf(msg, _("completed with %d local objects"),
-- 
1.8.2.22.g4863f63

Re: [PATCH v2] index-pack: always zero-initialize object_entry list

[Thomas Rast]

Jeff King <peff@peff.net> writes:

> On Tue, Mar 19, 2013 at 11:52:44AM -0400, Jeff King wrote:
>
>> > > > Commit 38a4556 (index-pack: start learning to emulate
>> > > > "verify-pack -v", 2011-06-03) added a "delta_depth" counter
>> > > > to each "struct object_entry". Initially, all object entries
>> > > > have their depth set to 0; in resolve_delta, we then set the
>> > > > depth of each delta to "base + 1". Base entries never have
>> > > > their depth touched, and remain at 0.
>> > > 
>> > > This patch causes index-pack to fail on the pack that triggered the
>> > > whole discussion.  More in a minute in another side thread, but
>> > > meanwhile: NAK until we understand what is really going on here.
>> > 
>> > Odd; that's what I was testing with, and it worked fine.
>> 
>> Ah, interesting. I built the fix on top of d1a0ed1, the first commit
>> that shows the problem. And it works fine there. But when it is
>> forward-ported to the current master, it breaks as you saw.
>> 
>> More bisection fun.
>
> So after bisecting, I realize that it is indeed broken on top of
> d1a0ed1. I have no idea why I didn't notice that before; I'm guessing it
> was because I was running it under valgrind and paying attention only to
> valgrind errors.
>
> Anyway, the problem is simple and stupid. The original object array is
> not nr_objects item long; it is (nr_objects + 1) long, though I'm not
> clear why (1-indexing?).

It apparently relates to the use of .idx.offset to compute the "next"
offset, cf. append_obj_to_pack():

	struct object_entry *obj = &objects[nr_objects++];
   ...
	obj[1].idx.offset = obj[0].idx.offset + n;
	obj[1].idx.offset += write_compressed(f, buf, size);

So you trashed the offset of the first object after all the objects that
are actually *in* the patch.

And with that: ACK.

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

Re: [PATCH v2] index-pack: always zero-initialize object_entry list

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> It apparently relates to the use of .idx.offset to compute the "next"
> offset, cf. append_obj_to_pack():
>
> 	struct object_entry *obj = &objects[nr_objects++];
>    ...
> 	obj[1].idx.offset = obj[0].idx.offset + n;
> 	obj[1].idx.offset += write_compressed(f, buf, size);
>
> So you trashed the offset of the first object after all the objects that
> are actually *in* the patch.
>
> And with that: ACK.

Ahh, I also was scratching my head about that +1 thing.  After all,
the +1 in the argument to xrealloc() was already a clue.

Thanks both for digging to the bottom of this one.

Re: regression in multi-threaded git-pack-index

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Actually scratch that again.  It *is* a stack overflow, except that this
> is a thread stack, for which the OS X defaults are 512kB apparently, as
> opposed to 2MB on linux.
> ...
> And indeed the following patch fixes it.  Sounds like the delta
> unpacking needs a rewrite to support stackless operation.  Sigh.

Yikes.  Thanks for digging it to the bottom.

I am not sure if I want to carry this patch in its current form,
though.  As this episode demonstrates, no default is good enough for
everybody, and I am not sure if a configuration variable is a good
way to go, either.

>
> diff --git i/builtin/index-pack.c w/builtin/index-pack.c
> index 6be99e2..f73291f 100644
> --- i/builtin/index-pack.c
> +++ w/builtin/index-pack.c
> @@ -1075,13 +1075,17 @@ static void resolve_deltas(void)
>  	nr_dispatched = 0;
>  	if (nr_threads > 1 || getenv("GIT_FORCE_THREADS")) {
>  		init_thread();
> +		pthread_attr_t attr;
> +		pthread_attr_init(&attr);
> +		pthread_attr_setstacksize(&attr, 2*1024*1024);
>  		for (i = 0; i < nr_threads; i++) {
> -			int ret = pthread_create(&thread_data[i].thread, NULL,
> +			int ret = pthread_create(&thread_data[i].thread, &attr,
>  						 threaded_second_pass, thread_data + i);
>  			if (ret)
>  				die(_("unable to create thread: %s"),
>  				    strerror(ret));
>  		}
> +		pthread_attr_destroy(&attr);
>  		for (i = 0; i < nr_threads; i++)
>  			pthread_join(thread_data[i].thread, NULL);
>  		cleanup_thread();

[PATCH] sha1_file: remove recursion in packed_object_info

[Thomas Rast]

packed_object_info() and packed_delta_info() were mutually recursive.
The former would handle ordinary types and defer deltas to the latter;
the latter would use the former to resolve the delta base.

This arrangement, however, leads to trouble with threaded index-pack
and long delta chains on platforms where thread stacks are small, as
happened on OS X (512kB thread stacks by default) with the chromium
repo.

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 only complication stems from the error recovery.  If parsing fails
at any step, we want to mark that object (within the pack) as bad and
try getting the corresponding SHA1 from elsewhere.  If that also
fails, we want to repeat this process back up the delta chain until we
find a reasonable solution or conclude that there is no way to
reconstruct the object.  (This is conveniently checked by t5303.)

To achieve that within the pack, we keep track of the entire delta
chain in a stack.  When things go sour, we process that stack from the
top, marking entries as bad and attempting to re-resolve by sha1.  To
avoid excessive malloc(), the stack starts out with a small
stack-allocated array.  The choice of 64 is based on the default of
pack.depth, which is 50, in the hope that it covers "most" delta
chains without any need for malloc().

It's much harder to make the actual re-resolving by sha1 nonrecursive,
so we skip that.  If you can't afford *that* recursion, your
corruption problems are more serious than your stack size problems.

Reported-by: Stefan Zager <szager@google.com>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---

Junio C Hamano <gitster@pobox.com> writes:

> Thomas Rast <trast@student.ethz.ch> writes:
> 
> > Actually scratch that again.  It *is* a stack overflow, except that this
> > is a thread stack, for which the OS X defaults are 512kB apparently, as
> > opposed to 2MB on linux.
> > ...
> > And indeed the following patch fixes it.  Sounds like the delta
> > unpacking needs a rewrite to support stackless operation.  Sigh.
> 
> Yikes.  Thanks for digging it to the bottom.

So here's a nonrecursive version.  Dijkstra is probably turning over
in his grave as we speak.

I *think* I actually got it right.  It passes tests in any case. ;-)

The sad part is, after all the effort it still bombs out in the same
place because of the very similar recursion in unpack_entry().  I'll
save that for another day.


 sha1_file.c | 132 +++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 81 insertions(+), 51 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 16967d3..54e92a2 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1639,50 +1639,6 @@ static off_t get_delta_base(struct packed_git *p,
 	return base_offset;
 }
 
-/* forward declaration for a mutually recursive function */
-static int packed_object_info(struct packed_git *p, off_t offset,
-			      unsigned long *sizep, int *rtype);
-
-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;
-	type = packed_object_info(p, base_offset, NULL, NULL);
-	if (type <= OBJ_NONE) {
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return OBJ_BAD;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		mark_bad_packed_object(p, base_sha1);
-		type = sha1_object_info(base_sha1, NULL);
-		if (type <= OBJ_NONE)
-			return OBJ_BAD;
-	}
-
-	/* 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;
-	}
-
-	return type;
-}
-
 int unpack_object_header(struct packed_git *p,
 			 struct pack_window **w_curs,
 			 off_t *curpos,
@@ -1709,6 +1665,25 @@ int unpack_object_header(struct packed_git *p,
 	return type;
 }
 
+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)
+{
+	int type;
+	struct revindex_entry *revidx;
+	const unsigned char *sha1;
+	revidx = find_pack_revindex(p, obj_offset);
+	if (!revidx)
+		return OBJ_BAD;
+	sha1 = nth_packed_object_sha1(p, revidx->nr);
+	mark_bad_packed_object(p, sha1);
+	type = sha1_object_info(sha1, NULL);
+	if (type <= OBJ_NONE)
+		return OBJ_BAD;
+	return type;
+}
+
+
+#define POI_STACK_PREALLOC 64
+
 static int packed_object_info(struct packed_git *p, off_t obj_offset,
 			      unsigned long *sizep, int *rtype)
 {
@@ -1716,31 +1691,86 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,
 	unsigned long size;
 	off_t curpos = obj_offset;
 	enum object_type type;
+	off_t small_poi_stack[POI_STACK_PREALLOC];
+	off_t *poi_stack = small_poi_stack;
+	int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
 
 	type = unpack_object_header(p, &w_curs, &curpos, &size);
+
 	if (rtype)
 		*rtype = type; /* representation type */
 
+	if (sizep) {
+		if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+			off_t tmp_pos = curpos;
+			get_delta_base(p, &w_curs, &tmp_pos, type, obj_offset);
+			*sizep = get_size_from_delta(p, &w_curs, tmp_pos);
+			if (*sizep == 0) {
+				type = OBJ_BAD;
+				goto out;
+			}
+		} else {
+			*sizep = size;
+		}
+	}
+
+	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+		off_t base_offset;
+		/* Push the object we're going to leave behind */
+		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
+			poi_stack_alloc = alloc_nr(poi_stack_nr);
+			poi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);
+			memcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);
+		} else {
+			ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
+		}
+		poi_stack[poi_stack_nr++] = obj_offset;
+		/* If parsing the base offset fails, just unwind */
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset)
+			goto unwind;
+		curpos = obj_offset = base_offset;
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type <= OBJ_NONE) {
+			/* If getting the base itself fails, we first
+			 * retry the base, otherwise unwind */
+			type = retry_bad_packed_offset(p, base_offset);
+			if (type > OBJ_NONE)
+				goto out;
+			goto unwind;
+		}
+	}
+
 	switch (type) {
-	case OBJ_OFS_DELTA:
-	case OBJ_REF_DELTA:
-		type = packed_delta_info(p, &w_curs, curpos,
-					 type, obj_offset, sizep);
-		break;
+	case OBJ_BAD:
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		if (sizep)
-			*sizep = size;
 		break;
 	default:
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
 		      type, (uintmax_t)obj_offset, p->pack_name);
 		type = OBJ_BAD;
 	}
+
+out:
+	if (poi_stack != small_poi_stack)
+		free(poi_stack);
 	unuse_pack(&w_curs);
 	return type;
+
+unwind:
+	while (poi_stack_nr) {
+		obj_offset = poi_stack[poi_stack_nr--];
+		type = retry_bad_packed_offset(p, obj_offset);
+		if (type > OBJ_NONE)
+			goto out;
+	}
+	if (poi_stack != small_poi_stack)
+		free(poi_stack);
+	unuse_pack(&w_curs);
+	return OBJ_BAD;
 }
 
 static void *unpack_compressed_entry(struct packed_git *p,
-- 
1.8.2.490.g25051b0

Re: regression in multi-threaded git-pack-index

[Duy Nguyen]

On Tue, Mar 19, 2013 at 11:11 PM, Thomas Rast <trast@student.ethz.ch> wrote:
> Actually scratch that again.  It *is* a stack overflow, except that this
> is a thread stack, for which the OS X defaults are 512kB apparently, as
> opposed to 2MB on linux.

Thanks. I was scratching my head last night wondering if there was
unprotected access to the object database and probably would have
continued this morning.
-- 
Duy

Re: [PATCH] sha1_file: remove recursion in packed_object_info

[Junio C Hamano]

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:

> -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...

> -	/* 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?

> 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.

Re: [PATCH v2] index-pack: always zero-initialize object_entry list

[Eric Sunshine]

On Tue, Mar 19, 2013 at 12:17 PM, Jeff King <peff@peff.net> wrote:
> To ensure that all depths start at 0, that commit changed
> calls to xmalloc the object_entry list into calls to
> xcalloc.  However, it forgot that we grow the list with
> xrealloc later. These extra entries are used when we add an
> object from elsewhere pack to complete a thin pack. If we

s/elsewhere pack/pack/

> add a non-delta object, its depth value will just be
> uninitialized heap data.

Re: [PATCH v2] index-pack: always zero-initialize object_entry list

[Jeff King]

On Wed, Mar 20, 2013 at 03:12:07PM -0400, Eric Sunshine wrote:

> On Tue, Mar 19, 2013 at 12:17 PM, Jeff King <peff@peff.net> wrote:
> > To ensure that all depths start at 0, that commit changed
> > calls to xmalloc the object_entry list into calls to
> > xcalloc.  However, it forgot that we grow the list with
> > xrealloc later. These extra entries are used when we add an
> > object from elsewhere pack to complete a thin pack. If we
> 
> s/elsewhere pack/pack/

I think it is supposed to be s/elsewhere pack/elsewhere/.

Thanks for noticing.

-Peff

Re: [PATCH v2] index-pack: always zero-initialize object_entry list

[Eric Sunshine]

On Wed, Mar 20, 2013 at 3:13 PM, Jeff King <peff@peff.net> wrote:
> On Wed, Mar 20, 2013 at 03:12:07PM -0400, Eric Sunshine wrote:
>
>> On Tue, Mar 19, 2013 at 12:17 PM, Jeff King <peff@peff.net> wrote:
>> > To ensure that all depths start at 0, that commit changed
>> > calls to xmalloc the object_entry list into calls to
>> > xcalloc.  However, it forgot that we grow the list with
>> > xrealloc later. These extra entries are used when we add an
>> > object from elsewhere pack to complete a thin pack. If we
>>
>> s/elsewhere pack/pack/
>
> I think it is supposed to be s/elsewhere pack/elsewhere/.

Sorry, yes.

-- ES

Re: [PATCH] sha1_file: remove recursion in packed_object_info

[thomas]

Junio C Hamano <gitster@pobox.com> writes:

> 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:
>
>> -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

[PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info

[Thomas Rast]

This is a fixed version of the initial patch, plus a two-patch
implementation of a recursion-free unpack_entry.  (I narrowly resisted
using "unrecursify" to describe it.)

I wrote:

> Junio C Hamano <gitster@pobox.com> writes:
>
>> 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...

Now I remember why it wasn't possible: we would have to go through the
blacklists at every iteration, whereas now we only check them in the
initial lookups.

I'm not sure it makes that much sense.  If we need to shave off some
speed in these functions, I would rather:

- write packed_object_info so that it runs with constant space, and
  restarts another implementation _with_ the recovery stack if it hits
  a problem;

- write unpack_entry so that it reuses the stack.  It can't do so by
  using a static buffer because it needs to be reentrant in the error
  case.


Thomas Rast (3):
  sha1_file: remove recursion in packed_object_info
  Refactor parts of in_delta_base_cache/cache_or_unpack_entry
  sha1_file: remove recursion in unpack_entry

 sha1_file.c | 411 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 266 insertions(+), 145 deletions(-)

-- 
1.8.2.266.g8176668

[PATCH v2 1/3] sha1_file: remove recursion in packed_object_info

[Thomas Rast]

packed_object_info() and packed_delta_info() were mutually recursive.
The former would handle ordinary types and defer deltas to the latter;
the latter would use the former to resolve the delta base.

This arrangement, however, leads to trouble with threaded index-pack
and long delta chains on platforms where thread stacks are small, as
happened on OS X (512kB thread stacks by default) with the chromium
repo.

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 only complication stems from the error recovery.  If parsing fails
at any step, we want to mark that object (within the pack) as bad and
try getting the corresponding SHA1 from elsewhere.  If that also
fails, we want to repeat this process back up the delta chain until we
find a reasonable solution or conclude that there is no way to
reconstruct the object.  (This is conveniently checked by t5303.)

To achieve that within the pack, we keep track of the entire delta
chain in a stack.  When things go sour, we process that stack from the
top, marking entries as bad and attempting to re-resolve by sha1.  To
avoid excessive malloc(), the stack starts out with a small
stack-allocated array.  The choice of 64 is based on the default of
pack.depth, which is 50, in the hope that it covers "most" delta
chains without any need for malloc().

It's much harder to make the actual re-resolving by sha1 nonrecursive,
so we skip that.  If you can't afford *that* recursion, your
corruption problems are more serious than your stack size problems.

Reported-by: Stefan Zager <szager@google.com>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 135 +++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 84 insertions(+), 51 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 40b2329..71877a7 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1560,50 +1560,6 @@ static off_t get_delta_base(struct packed_git *p,
 	return base_offset;
 }
 
-/* forward declaration for a mutually recursive function */
-static int packed_object_info(struct packed_git *p, off_t offset,
-			      unsigned long *sizep, int *rtype);
-
-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;
-	type = packed_object_info(p, base_offset, NULL, NULL);
-	if (type <= OBJ_NONE) {
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return OBJ_BAD;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		mark_bad_packed_object(p, base_sha1);
-		type = sha1_object_info(base_sha1, NULL);
-		if (type <= OBJ_NONE)
-			return OBJ_BAD;
-	}
-
-	/* 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;
-	}
-
-	return type;
-}
-
 int unpack_object_header(struct packed_git *p,
 			 struct pack_window **w_curs,
 			 off_t *curpos,
@@ -1630,6 +1586,25 @@ int unpack_object_header(struct packed_git *p,
 	return type;
 }
 
+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)
+{
+	int type;
+	struct revindex_entry *revidx;
+	const unsigned char *sha1;
+	revidx = find_pack_revindex(p, obj_offset);
+	if (!revidx)
+		return OBJ_BAD;
+	sha1 = nth_packed_object_sha1(p, revidx->nr);
+	mark_bad_packed_object(p, sha1);
+	type = sha1_object_info(sha1, NULL);
+	if (type <= OBJ_NONE)
+		return OBJ_BAD;
+	return type;
+}
+
+
+#define POI_STACK_PREALLOC 64
+
 static int packed_object_info(struct packed_git *p, off_t obj_offset,
 			      unsigned long *sizep, int *rtype)
 {
@@ -1637,31 +1612,89 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,
 	unsigned long size;
 	off_t curpos = obj_offset;
 	enum object_type type;
+	off_t small_poi_stack[POI_STACK_PREALLOC];
+	off_t *poi_stack = small_poi_stack;
+	int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
 
 	type = unpack_object_header(p, &w_curs, &curpos, &size);
+
 	if (rtype)
 		*rtype = type; /* representation type */
 
+	if (sizep) {
+		if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+			off_t tmp_pos = curpos;
+			off_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,
+							   type, obj_offset);
+			if (!base_offset) {
+				type = OBJ_BAD;
+				goto out;
+			}
+			*sizep = get_size_from_delta(p, &w_curs, tmp_pos);
+			if (*sizep == 0) {
+				type = OBJ_BAD;
+				goto out;
+			}
+		} else {
+			*sizep = size;
+		}
+	}
+
+	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+		off_t base_offset;
+		/* Push the object we're going to leave behind */
+		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
+			poi_stack_alloc = alloc_nr(poi_stack_nr);
+			poi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);
+			memcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);
+		} else {
+			ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
+		}
+		poi_stack[poi_stack_nr++] = obj_offset;
+		/* If parsing the base offset fails, just unwind */
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset)
+			goto unwind;
+		curpos = obj_offset = base_offset;
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type <= OBJ_NONE) {
+			/* If getting the base itself fails, we first
+			 * retry the base, otherwise unwind */
+			type = retry_bad_packed_offset(p, base_offset);
+			if (type > OBJ_NONE)
+				goto out;
+			goto unwind;
+		}
+	}
+
 	switch (type) {
-	case OBJ_OFS_DELTA:
-	case OBJ_REF_DELTA:
-		type = packed_delta_info(p, &w_curs, curpos,
-					 type, obj_offset, sizep);
-		break;
+	case OBJ_BAD:
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		if (sizep)
-			*sizep = size;
 		break;
 	default:
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
 		      type, (uintmax_t)obj_offset, p->pack_name);
 		type = OBJ_BAD;
 	}
+
+out:
+	if (poi_stack != small_poi_stack)
+		free(poi_stack);
 	unuse_pack(&w_curs);
 	return type;
+
+unwind:
+	while (poi_stack_nr) {
+		obj_offset = poi_stack[--poi_stack_nr];
+		type = retry_bad_packed_offset(p, obj_offset);
+		if (type > OBJ_NONE)
+			goto out;
+	}
+	type = OBJ_BAD;
+	goto out;
 }
 
 static void *unpack_compressed_entry(struct packed_git *p,
-- 
1.8.2.266.g8176668

[PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry

[Thomas Rast]

The delta base cache lookup and test were shared.  Refactor them;
we'll need both parts again.  Also, we'll use the clearing routine
later.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 32 insertions(+), 13 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 71877a7..bd054d1 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1756,32 +1756,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
 	return hash % MAX_DELTA_CACHE;
 }
 
-static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
+static struct delta_base_cache_entry *
+get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
 {
 	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
+	return delta_base_cache + hash;
+}
+
+static int cmp_delta_base_cache_entry(struct delta_base_cache_entry *ent,
+				      struct packed_git *p, off_t base_offset)
+{
 	return (ent->data && ent->p == p && ent->base_offset == base_offset);
 }
 
+static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
+{
+	struct delta_base_cache_entry *ent;
+	ent = get_delta_base_cache_entry(p, base_offset);
+	return cmp_delta_base_cache_entry(ent, p, base_offset);
+}
+
+static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)
+{
+	ent->data = NULL;
+	ent->lru.next->prev = ent->lru.prev;
+	ent->lru.prev->next = ent->lru.next;
+	delta_base_cached -= ent->size;
+}
+
 static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 	unsigned long *base_size, enum object_type *type, int keep_cache)
 {
+	struct delta_base_cache_entry *ent;
 	void *ret;
-	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
 
-	ret = ent->data;
-	if (!ret || ent->p != p || ent->base_offset != base_offset)
+	ent = get_delta_base_cache_entry(p, base_offset);
+
+	if (!cmp_delta_base_cache_entry(ent, p, base_offset))
 		return unpack_entry(p, base_offset, type, base_size);
 
-	if (!keep_cache) {
-		ent->data = NULL;
-		ent->lru.next->prev = ent->lru.prev;
-		ent->lru.prev->next = ent->lru.next;
-		delta_base_cached -= ent->size;
-	} else {
+	ret = ent->data;
+
+	if (!keep_cache)
+		clear_delta_base_cache_entry(ent);
+	else
 		ret = xmemdupz(ent->data, ent->size);
-	}
 	*type = ent->type;
 	*base_size = ent->size;
 	return ret;
-- 
1.8.2.266.g8176668

[PATCH v2 3/3] sha1_file: remove recursion in unpack_entry

[Thomas Rast]

Similar to the recursion in packed_object_info(), this leads to
problems on stack-space-constrained systems in the presence of long
delta chains.

We proceed in three phases:

1. Dig through the delta chain, saving each delta object's offsets and
   size on an ad-hoc stack.

2. Unpack the base object at the bottom.

3. Apply the deltas from the stack.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 150 insertions(+), 81 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index bd054d1..1b685b9 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1864,68 +1864,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 static void *read_object(const unsigned char *sha1, enum object_type *type,
 			 unsigned long *size);
 
-static void *unpack_delta_entry(struct packed_git *p,
-				struct pack_window **w_curs,
-				off_t curpos,
-				unsigned long delta_size,
-				off_t obj_offset,
-				enum object_type *type,
-				unsigned long *sizep)
-{
-	void *delta_data, *result, *base;
-	unsigned long base_size;
-	off_t base_offset;
-
-	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
-	if (!base_offset) {
-		error("failed to validate delta base reference "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		return NULL;
-	}
-	unuse_pack(w_curs);
-	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
-	if (!base) {
-		/*
-		 * We're probably in deep shit, but let's try to fetch
-		 * the required base anyway from another pack or loose.
-		 * This is costly but should happen only in the presence
-		 * of a corrupted pack, and is better than failing outright.
-		 */
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return NULL;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		error("failed to read delta base object %s"
-		      " at offset %"PRIuMAX" from %s",
-		      sha1_to_hex(base_sha1), (uintmax_t)base_offset,
-		      p->pack_name);
-		mark_bad_packed_object(p, base_sha1);
-		base = read_object(base_sha1, type, &base_size);
-		if (!base)
-			return NULL;
-	}
-
-	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
-	if (!delta_data) {
-		error("failed to unpack compressed delta "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		free(base);
-		return NULL;
-	}
-	result = patch_delta(base, base_size,
-			     delta_data, delta_size,
-			     sizep);
-	if (!result)
-		die("failed to apply delta");
-	free(delta_data);
-	add_delta_base_cache(p, base_offset, base, base_size, *type);
-	return result;
-}
-
 static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 {
 	static FILE *log_file;
@@ -1946,48 +1884,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 
 int do_check_packed_object_crc;
 
+#define UNPACK_ENTRY_STACK_PREALLOC 64
+struct unpack_entry_stack_ent {
+	off_t obj_offset;
+	off_t curpos;
+	unsigned long size;
+};
+
 void *unpack_entry(struct packed_git *p, off_t obj_offset,
-		   enum object_type *type, unsigned long *sizep)
+		   enum object_type *final_type, unsigned long *final_size)
 {
 	struct pack_window *w_curs = NULL;
 	off_t curpos = obj_offset;
-	void *data;
+	void *data = NULL;
+	unsigned long size;
+	enum object_type type;
+	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
+	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
+	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
+	int base_from_cache = 0;
 
 	if (log_pack_access)
 		write_pack_access_log(p, obj_offset);
 
-	if (do_check_packed_object_crc && p->index_version > 1) {
-		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-		unsigned long len = revidx[1].offset - obj_offset;
-		if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
-			const unsigned char *sha1 =
-				nth_packed_object_sha1(p, revidx->nr);
-			error("bad packed object CRC for %s",
-			      sha1_to_hex(sha1));
-			mark_bad_packed_object(p, sha1);
-			unuse_pack(&w_curs);
-			return NULL;
+	/* PHASE 1: drill down to the innermost base object */
+	for (;;) {
+		off_t base_offset;
+		int i;
+		struct delta_base_cache_entry *ent;
+
+		if (do_check_packed_object_crc && p->index_version > 1) {
+			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
+			unsigned long len = revidx[1].offset - obj_offset;
+			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
+				const unsigned char *sha1 =
+					nth_packed_object_sha1(p, revidx->nr);
+				error("bad packed object CRC for %s",
+				      sha1_to_hex(sha1));
+				mark_bad_packed_object(p, sha1);
+				unuse_pack(&w_curs);
+				return NULL;
+			}
+		}
+
+		ent = get_delta_base_cache_entry(p, curpos);
+		if (cmp_delta_base_cache_entry(ent, p, curpos)) {
+			type = ent->type;
+			data = ent->data;
+			size = ent->size;
+			clear_delta_base_cache_entry(ent);
+			base_from_cache = 1;
+			break;
+		}
+
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
+			break;
+
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset) {
+			error("failed to validate delta base reference "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			/* bail to phase 2, in hopes of recovery */
+			data = NULL;
+			break;
 		}
+
+		/* push object, proceed to base */
+		if (delta_stack_nr >= delta_stack_alloc
+		    && delta_stack == small_delta_stack) {
+			delta_stack_alloc = alloc_nr(delta_stack_nr);
+			delta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);
+			memcpy(delta_stack, small_delta_stack,
+			       sizeof(*delta_stack)*delta_stack_nr);
+		} else {
+			ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
+		}
+		i = delta_stack_nr++;
+		delta_stack[i].obj_offset = obj_offset;
+		delta_stack[i].curpos = curpos;
+		delta_stack[i].size = size;
+
+		curpos = obj_offset = base_offset;
 	}
 
-	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
-	switch (*type) {
+	/* PHASE 2: handle the base */
+	switch (type) {
 	case OBJ_OFS_DELTA:
 	case OBJ_REF_DELTA:
-		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
-					  obj_offset, type, sizep);
+		if (data)
+			die("BUG in unpack_entry: left loop at a valid delta");
 		break;
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
+		if (!base_from_cache)
+			data = unpack_compressed_entry(p, &w_curs, curpos, size);
 		break;
 	default:
 		data = NULL;
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
-		      *type, (uintmax_t)obj_offset, p->pack_name);
+		      type, (uintmax_t)obj_offset, p->pack_name);
 	}
+
+	/* PHASE 3: apply deltas in order */
+
+	/* invariants:
+	 *   'data' holds the base data, or NULL if there was corruption
+	 */
+	while (delta_stack_nr) {
+		void *delta_data;
+		void *base = data;
+		unsigned long delta_size, base_size = size;
+		int i;
+
+		data = NULL;
+
+		if (base)
+			add_delta_base_cache(p, obj_offset, base, base_size, type);
+
+		if (!base) {
+			/*
+			 * We're probably in deep shit, but let's try to fetch
+			 * the required base anyway from another pack or loose.
+			 * This is costly but should happen only in the presence
+			 * of a corrupted pack, and is better than failing outright.
+			 */
+			struct revindex_entry *revidx;
+			const unsigned char *base_sha1;
+			revidx = find_pack_revindex(p, obj_offset);
+			if (revidx) {
+				base_sha1 = nth_packed_object_sha1(p, revidx->nr);
+				error("failed to read delta base object %s"
+				      " at offset %"PRIuMAX" from %s",
+				      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
+				      p->pack_name);
+				mark_bad_packed_object(p, base_sha1);
+				base = read_object(base_sha1, &type, &base_size);
+			}
+		}
+
+		i = --delta_stack_nr;
+		obj_offset = delta_stack[i].obj_offset;
+		curpos = delta_stack[i].curpos;
+		delta_size = delta_stack[i].size;
+
+		if (!base)
+			continue;
+
+		delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
+
+		if (!delta_data) {
+			error("failed to unpack compressed delta "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			free(base);
+			data = NULL;
+			continue;
+		}
+
+		data = patch_delta(base, base_size,
+				   delta_data, delta_size,
+				   &size);
+		if (!data)
+			die("failed to apply delta");
+
+		free (delta_data);
+	}
+
+	*final_type = type;
+	*final_size = size;
+
 	unuse_pack(&w_curs);
 	return data;
 }
-- 
1.8.2.266.g8176668

Re: [PATCH] sha1_file: remove recursion in packed_object_info

[Junio C Hamano]

thomas <trast@student.ethz.ch> writes:

> Junio C Hamano <gitster@pobox.com> writes:
>
>> 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.

get_size_from_delta() grabs the size, the number you would get in
the third parameter of read_sha1_file(), of the result of applying
the delta we are looking at.  The part that stores this information
is called the "compressed delta data" in the document you are
looking at.

The function you want to look at is patch_delta(), where it grabs
two such sizes from the delta stream with get_delta_hdr_size().

A delta stream begins with:

    * preimage length, expressed as a 7-bit-per-byte varint;
    * postimage length, expressed as a 7-bit-per-byte varint;

followed by number of records, each prefixed by a command byte.

    * Command byte with its 8th bit set records source offset and
      size (max 32 and 24 bits, respectively---other 7 bits in the
      command byte tells us how large the offset and size are) and
      tells us to insert a copy of that region at the current point.

    * Command byte between 1-127 (inclusive) tells us to add that
      many bytes that follow the command byte from the delta stream
      at the current point.

    * Command byte 0 is an error.

And get_size_from_delta() skips the preimage length, grabs postimage
length and returns the latter.  It is how we decide how many bytes
we need to allocate to hold the result of applying the delta.

> 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.

Yes, that is why I said "is this check correct?".  As I already
said, I think the only two things that protects us from creating a
delta whose postimage size is 0 are the fact that we do not even
attempt to deltify anything smaller than 50 bytes in pack-objects,
and create_delta() refuses to create a delta to produce an empty
postimage.

Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> The delta base cache lookup and test were shared.  Refactor them;
> we'll need both parts again.  Also, we'll use the clearing routine
> later.
>
> Signed-off-by: Thomas Rast <trast@student.ethz.ch>
> ---

Looks like a very straight-forward rewrite.

The only little concern I may have is this cmp_* function tells us
"I found it!" by returning true, which is counter-intuitive to the
readers of the caller (not the callee).

I think it makes sense to compare delta-base-cache entries only for
equality, so eq-delta-base-cache-entry might be a better name for
it, perhaps?

>  sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------
>  1 file changed, 32 insertions(+), 13 deletions(-)
>
> diff --git a/sha1_file.c b/sha1_file.c
> index 71877a7..bd054d1 100644
> --- a/sha1_file.c
> +++ b/sha1_file.c
> @@ -1756,32 +1756,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
>  	return hash % MAX_DELTA_CACHE;
>  }
>  
> -static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
> +static struct delta_base_cache_entry *
> +get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
>  {
>  	unsigned long hash = pack_entry_hash(p, base_offset);
> -	struct delta_base_cache_entry *ent = delta_base_cache + hash;
> +	return delta_base_cache + hash;
> +}
> +
> +static int cmp_delta_base_cache_entry(struct delta_base_cache_entry *ent,
> +				      struct packed_git *p, off_t base_offset)
> +{
>  	return (ent->data && ent->p == p && ent->base_offset == base_offset);
>  }
>  
> +static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
> +{
> +	struct delta_base_cache_entry *ent;
> +	ent = get_delta_base_cache_entry(p, base_offset);
> +	return cmp_delta_base_cache_entry(ent, p, base_offset);
> +}
> +
> +static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)
> +{
> +	ent->data = NULL;
> +	ent->lru.next->prev = ent->lru.prev;
> +	ent->lru.prev->next = ent->lru.next;
> +	delta_base_cached -= ent->size;
> +}
> +
>  static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
>  	unsigned long *base_size, enum object_type *type, int keep_cache)
>  {
> +	struct delta_base_cache_entry *ent;
>  	void *ret;
> -	unsigned long hash = pack_entry_hash(p, base_offset);
> -	struct delta_base_cache_entry *ent = delta_base_cache + hash;
>  
> -	ret = ent->data;
> -	if (!ret || ent->p != p || ent->base_offset != base_offset)
> +	ent = get_delta_base_cache_entry(p, base_offset);
> +
> +	if (!cmp_delta_base_cache_entry(ent, p, base_offset))
>  		return unpack_entry(p, base_offset, type, base_size);
>  
> -	if (!keep_cache) {
> -		ent->data = NULL;
> -		ent->lru.next->prev = ent->lru.prev;
> -		ent->lru.prev->next = ent->lru.next;
> -		delta_base_cached -= ent->size;
> -	} else {
> +	ret = ent->data;
> +
> +	if (!keep_cache)
> +		clear_delta_base_cache_entry(ent);
> +	else
>  		ret = xmemdupz(ent->data, ent->size);
> -	}
>  	*type = ent->type;
>  	*base_size = ent->size;
>  	return ret;

Re: [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Similar to the recursion in packed_object_info(), this leads to
> problems on stack-space-constrained systems in the presence of long
> delta chains.
>
> We proceed in three phases:
>
> 1. Dig through the delta chain, saving each delta object's offsets and
>    size on an ad-hoc stack.
>
> 2. Unpack the base object at the bottom.
>
> 3. Apply the deltas from the stack.
>
> Signed-off-by: Thomas Rast <trast@student.ethz.ch>

The above made me nervous but you are not pushing the actual delta
data on the stack, so the patch looks good from a quick scan.

Thanks.  Will queue.

> ---
>  sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------
>  1 file changed, 150 insertions(+), 81 deletions(-)
>
> diff --git a/sha1_file.c b/sha1_file.c
> index bd054d1..1b685b9 100644
> --- a/sha1_file.c
> +++ b/sha1_file.c
> @@ -1864,68 +1864,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
>  static void *read_object(const unsigned char *sha1, enum object_type *type,
>  			 unsigned long *size);
>  
> -static void *unpack_delta_entry(struct packed_git *p,
> -				struct pack_window **w_curs,
> -				off_t curpos,
> -				unsigned long delta_size,
> -				off_t obj_offset,
> -				enum object_type *type,
> -				unsigned long *sizep)
> -{
> -	void *delta_data, *result, *base;
> -	unsigned long base_size;
> -	off_t base_offset;
> -
> -	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
> -	if (!base_offset) {
> -		error("failed to validate delta base reference "
> -		      "at offset %"PRIuMAX" from %s",
> -		      (uintmax_t)curpos, p->pack_name);
> -		return NULL;
> -	}
> -	unuse_pack(w_curs);
> -	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
> -	if (!base) {
> -		/*
> -		 * We're probably in deep shit, but let's try to fetch
> -		 * the required base anyway from another pack or loose.
> -		 * This is costly but should happen only in the presence
> -		 * of a corrupted pack, and is better than failing outright.
> -		 */
> -		struct revindex_entry *revidx;
> -		const unsigned char *base_sha1;
> -		revidx = find_pack_revindex(p, base_offset);
> -		if (!revidx)
> -			return NULL;
> -		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
> -		error("failed to read delta base object %s"
> -		      " at offset %"PRIuMAX" from %s",
> -		      sha1_to_hex(base_sha1), (uintmax_t)base_offset,
> -		      p->pack_name);
> -		mark_bad_packed_object(p, base_sha1);
> -		base = read_object(base_sha1, type, &base_size);
> -		if (!base)
> -			return NULL;
> -	}
> -
> -	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
> -	if (!delta_data) {
> -		error("failed to unpack compressed delta "
> -		      "at offset %"PRIuMAX" from %s",
> -		      (uintmax_t)curpos, p->pack_name);
> -		free(base);
> -		return NULL;
> -	}
> -	result = patch_delta(base, base_size,
> -			     delta_data, delta_size,
> -			     sizep);
> -	if (!result)
> -		die("failed to apply delta");
> -	free(delta_data);
> -	add_delta_base_cache(p, base_offset, base, base_size, *type);
> -	return result;
> -}
> -
>  static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
>  {
>  	static FILE *log_file;
> @@ -1946,48 +1884,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
>  
>  int do_check_packed_object_crc;
>  
> +#define UNPACK_ENTRY_STACK_PREALLOC 64
> +struct unpack_entry_stack_ent {
> +	off_t obj_offset;
> +	off_t curpos;
> +	unsigned long size;
> +};
> +
>  void *unpack_entry(struct packed_git *p, off_t obj_offset,
> -		   enum object_type *type, unsigned long *sizep)
> +		   enum object_type *final_type, unsigned long *final_size)
>  {
>  	struct pack_window *w_curs = NULL;
>  	off_t curpos = obj_offset;
> -	void *data;
> +	void *data = NULL;
> +	unsigned long size;
> +	enum object_type type;
> +	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
> +	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
> +	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
> +	int base_from_cache = 0;
>  
>  	if (log_pack_access)
>  		write_pack_access_log(p, obj_offset);
>  
> -	if (do_check_packed_object_crc && p->index_version > 1) {
> -		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
> -		unsigned long len = revidx[1].offset - obj_offset;
> -		if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
> -			const unsigned char *sha1 =
> -				nth_packed_object_sha1(p, revidx->nr);
> -			error("bad packed object CRC for %s",
> -			      sha1_to_hex(sha1));
> -			mark_bad_packed_object(p, sha1);
> -			unuse_pack(&w_curs);
> -			return NULL;
> +	/* PHASE 1: drill down to the innermost base object */
> +	for (;;) {
> +		off_t base_offset;
> +		int i;
> +		struct delta_base_cache_entry *ent;
> +
> +		if (do_check_packed_object_crc && p->index_version > 1) {
> +			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
> +			unsigned long len = revidx[1].offset - obj_offset;
> +			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
> +				const unsigned char *sha1 =
> +					nth_packed_object_sha1(p, revidx->nr);
> +				error("bad packed object CRC for %s",
> +				      sha1_to_hex(sha1));
> +				mark_bad_packed_object(p, sha1);
> +				unuse_pack(&w_curs);
> +				return NULL;
> +			}
> +		}
> +
> +		ent = get_delta_base_cache_entry(p, curpos);
> +		if (cmp_delta_base_cache_entry(ent, p, curpos)) {
> +			type = ent->type;
> +			data = ent->data;
> +			size = ent->size;
> +			clear_delta_base_cache_entry(ent);
> +			base_from_cache = 1;
> +			break;
> +		}
> +
> +		type = unpack_object_header(p, &w_curs, &curpos, &size);
> +		if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
> +			break;
> +
> +		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
> +		if (!base_offset) {
> +			error("failed to validate delta base reference "
> +			      "at offset %"PRIuMAX" from %s",
> +			      (uintmax_t)curpos, p->pack_name);
> +			/* bail to phase 2, in hopes of recovery */
> +			data = NULL;
> +			break;
>  		}
> +
> +		/* push object, proceed to base */
> +		if (delta_stack_nr >= delta_stack_alloc
> +		    && delta_stack == small_delta_stack) {
> +			delta_stack_alloc = alloc_nr(delta_stack_nr);
> +			delta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);
> +			memcpy(delta_stack, small_delta_stack,
> +			       sizeof(*delta_stack)*delta_stack_nr);
> +		} else {
> +			ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
> +		}
> +		i = delta_stack_nr++;
> +		delta_stack[i].obj_offset = obj_offset;
> +		delta_stack[i].curpos = curpos;
> +		delta_stack[i].size = size;
> +
> +		curpos = obj_offset = base_offset;
>  	}
>  
> -	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
> -	switch (*type) {
> +	/* PHASE 2: handle the base */
> +	switch (type) {
>  	case OBJ_OFS_DELTA:
>  	case OBJ_REF_DELTA:
> -		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
> -					  obj_offset, type, sizep);
> +		if (data)
> +			die("BUG in unpack_entry: left loop at a valid delta");
>  		break;
>  	case OBJ_COMMIT:
>  	case OBJ_TREE:
>  	case OBJ_BLOB:
>  	case OBJ_TAG:
> -		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
> +		if (!base_from_cache)
> +			data = unpack_compressed_entry(p, &w_curs, curpos, size);
>  		break;
>  	default:
>  		data = NULL;
>  		error("unknown object type %i at offset %"PRIuMAX" in %s",
> -		      *type, (uintmax_t)obj_offset, p->pack_name);
> +		      type, (uintmax_t)obj_offset, p->pack_name);
>  	}
> +
> +	/* PHASE 3: apply deltas in order */
> +
> +	/* invariants:
> +	 *   'data' holds the base data, or NULL if there was corruption
> +	 */
> +	while (delta_stack_nr) {
> +		void *delta_data;
> +		void *base = data;
> +		unsigned long delta_size, base_size = size;
> +		int i;
> +
> +		data = NULL;
> +
> +		if (base)
> +			add_delta_base_cache(p, obj_offset, base, base_size, type);
> +
> +		if (!base) {
> +			/*
> +			 * We're probably in deep shit, but let's try to fetch
> +			 * the required base anyway from another pack or loose.
> +			 * This is costly but should happen only in the presence
> +			 * of a corrupted pack, and is better than failing outright.
> +			 */
> +			struct revindex_entry *revidx;
> +			const unsigned char *base_sha1;
> +			revidx = find_pack_revindex(p, obj_offset);
> +			if (revidx) {
> +				base_sha1 = nth_packed_object_sha1(p, revidx->nr);
> +				error("failed to read delta base object %s"
> +				      " at offset %"PRIuMAX" from %s",
> +				      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
> +				      p->pack_name);
> +				mark_bad_packed_object(p, base_sha1);
> +				base = read_object(base_sha1, &type, &base_size);
> +			}
> +		}
> +
> +		i = --delta_stack_nr;
> +		obj_offset = delta_stack[i].obj_offset;
> +		curpos = delta_stack[i].curpos;
> +		delta_size = delta_stack[i].size;
> +
> +		if (!base)
> +			continue;
> +
> +		delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
> +
> +		if (!delta_data) {
> +			error("failed to unpack compressed delta "
> +			      "at offset %"PRIuMAX" from %s",
> +			      (uintmax_t)curpos, p->pack_name);
> +			free(base);
> +			data = NULL;
> +			continue;
> +		}
> +
> +		data = patch_delta(base, base_size,
> +				   delta_data, delta_size,
> +				   &size);
> +		if (!data)
> +			die("failed to apply delta");
> +
> +		free (delta_data);
> +	}
> +
> +	*final_type = type;
> +	*final_size = size;
> +
>  	unuse_pack(&w_curs);
>  	return data;
>  }

Re: [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info

[Nicolas Pitre]

On Mon, 25 Mar 2013, Thomas Rast wrote:

> This is a fixed version of the initial patch, plus a two-patch
> implementation of a recursion-free unpack_entry.  (I narrowly resisted
> using "unrecursify" to describe it.)

Hmmm... the intention is sensible and the patches look sane, however I 
don't have my brain wrapped around this code as I used to, so I might 
be missing something.


Nicolas

Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry

[thomas]

Junio C Hamano <gitster@pobox.com> writes:

> Thomas Rast <trast@student.ethz.ch> writes:
>
>> The delta base cache lookup and test were shared.  Refactor them;
>> we'll need both parts again.  Also, we'll use the clearing routine
>> later.
>>
>> Signed-off-by: Thomas Rast <trast@student.ethz.ch>
>> ---
>
> Looks like a very straight-forward rewrite.
>
> The only little concern I may have is this cmp_* function tells us
> "I found it!" by returning true, which is counter-intuitive to the
> readers of the caller (not the callee).
>
> I think it makes sense to compare delta-base-cache entries only for
> equality, so eq-delta-base-cache-entry might be a better name for
> it, perhaps?

True.  I'll resend.

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

[PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info

[Thomas Rast]

From: Thomas Rast <trast@inf.ethz.ch>

Almost the same as last time.  Changed: the rename suggested by Junio

> The only little concern I may have is this cmp_* function tells us
> "I found it!" by returning true, which is counter-intuitive to the
> readers of the caller (not the callee).
> 
> I think it makes sense to compare delta-base-cache entries only for
> equality, so eq-delta-base-cache-entry might be a better name for
> it, perhaps?

and a small reword to patch 3's commit message to make it clearer at
which stage we unpack the deltas.


Thomas Rast (3):
  sha1_file: remove recursion in packed_object_info
  Refactor parts of in_delta_base_cache/cache_or_unpack_entry
  sha1_file: remove recursion in unpack_entry

 sha1_file.c | 411 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 266 insertions(+), 145 deletions(-)

-- 
1.8.2.344.g1440b22

[PATCH v3 1/3] sha1_file: remove recursion in packed_object_info

[Thomas Rast]

packed_object_info() and packed_delta_info() were mutually recursive.
The former would handle ordinary types and defer deltas to the latter;
the latter would use the former to resolve the delta base.

This arrangement, however, leads to trouble with threaded index-pack
and long delta chains on platforms where thread stacks are small, as
happened on OS X (512kB thread stacks by default) with the chromium
repo.

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 only complication stems from the error recovery.  If parsing fails
at any step, we want to mark that object (within the pack) as bad and
try getting the corresponding SHA1 from elsewhere.  If that also
fails, we want to repeat this process back up the delta chain until we
find a reasonable solution or conclude that there is no way to
reconstruct the object.  (This is conveniently checked by t5303.)

To achieve that within the pack, we keep track of the entire delta
chain in a stack.  When things go sour, we process that stack from the
top, marking entries as bad and attempting to re-resolve by sha1.  To
avoid excessive malloc(), the stack starts out with a small
stack-allocated array.  The choice of 64 is based on the default of
pack.depth, which is 50, in the hope that it covers "most" delta
chains without any need for malloc().

It's much harder to make the actual re-resolving by sha1 nonrecursive,
so we skip that.  If you can't afford *that* recursion, your
corruption problems are more serious than your stack size problems.

Reported-by: Stefan Zager <szager@google.com>
Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 135 +++++++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 84 insertions(+), 51 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 16967d3..2c8b549 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1639,50 +1639,6 @@ static off_t get_delta_base(struct packed_git *p,
 	return base_offset;
 }
 
-/* forward declaration for a mutually recursive function */
-static int packed_object_info(struct packed_git *p, off_t offset,
-			      unsigned long *sizep, int *rtype);
-
-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;
-	type = packed_object_info(p, base_offset, NULL, NULL);
-	if (type <= OBJ_NONE) {
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return OBJ_BAD;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		mark_bad_packed_object(p, base_sha1);
-		type = sha1_object_info(base_sha1, NULL);
-		if (type <= OBJ_NONE)
-			return OBJ_BAD;
-	}
-
-	/* 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;
-	}
-
-	return type;
-}
-
 int unpack_object_header(struct packed_git *p,
 			 struct pack_window **w_curs,
 			 off_t *curpos,
@@ -1709,6 +1665,25 @@ int unpack_object_header(struct packed_git *p,
 	return type;
 }
 
+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)
+{
+	int type;
+	struct revindex_entry *revidx;
+	const unsigned char *sha1;
+	revidx = find_pack_revindex(p, obj_offset);
+	if (!revidx)
+		return OBJ_BAD;
+	sha1 = nth_packed_object_sha1(p, revidx->nr);
+	mark_bad_packed_object(p, sha1);
+	type = sha1_object_info(sha1, NULL);
+	if (type <= OBJ_NONE)
+		return OBJ_BAD;
+	return type;
+}
+
+
+#define POI_STACK_PREALLOC 64
+
 static int packed_object_info(struct packed_git *p, off_t obj_offset,
 			      unsigned long *sizep, int *rtype)
 {
@@ -1716,31 +1691,89 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,
 	unsigned long size;
 	off_t curpos = obj_offset;
 	enum object_type type;
+	off_t small_poi_stack[POI_STACK_PREALLOC];
+	off_t *poi_stack = small_poi_stack;
+	int poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;
 
 	type = unpack_object_header(p, &w_curs, &curpos, &size);
+
 	if (rtype)
 		*rtype = type; /* representation type */
 
+	if (sizep) {
+		if (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+			off_t tmp_pos = curpos;
+			off_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,
+							   type, obj_offset);
+			if (!base_offset) {
+				type = OBJ_BAD;
+				goto out;
+			}
+			*sizep = get_size_from_delta(p, &w_curs, tmp_pos);
+			if (*sizep == 0) {
+				type = OBJ_BAD;
+				goto out;
+			}
+		} else {
+			*sizep = size;
+		}
+	}
+
+	while (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {
+		off_t base_offset;
+		/* Push the object we're going to leave behind */
+		if (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {
+			poi_stack_alloc = alloc_nr(poi_stack_nr);
+			poi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);
+			memcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);
+		} else {
+			ALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);
+		}
+		poi_stack[poi_stack_nr++] = obj_offset;
+		/* If parsing the base offset fails, just unwind */
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset)
+			goto unwind;
+		curpos = obj_offset = base_offset;
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type <= OBJ_NONE) {
+			/* If getting the base itself fails, we first
+			 * retry the base, otherwise unwind */
+			type = retry_bad_packed_offset(p, base_offset);
+			if (type > OBJ_NONE)
+				goto out;
+			goto unwind;
+		}
+	}
+
 	switch (type) {
-	case OBJ_OFS_DELTA:
-	case OBJ_REF_DELTA:
-		type = packed_delta_info(p, &w_curs, curpos,
-					 type, obj_offset, sizep);
-		break;
+	case OBJ_BAD:
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		if (sizep)
-			*sizep = size;
 		break;
 	default:
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
 		      type, (uintmax_t)obj_offset, p->pack_name);
 		type = OBJ_BAD;
 	}
+
+out:
+	if (poi_stack != small_poi_stack)
+		free(poi_stack);
 	unuse_pack(&w_curs);
 	return type;
+
+unwind:
+	while (poi_stack_nr) {
+		obj_offset = poi_stack[--poi_stack_nr];
+		type = retry_bad_packed_offset(p, obj_offset);
+		if (type > OBJ_NONE)
+			goto out;
+	}
+	type = OBJ_BAD;
+	goto out;
 }
 
 static void *unpack_compressed_entry(struct packed_git *p,
-- 
1.8.2.344.g1440b22

[PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry

[Thomas Rast]

The delta base cache lookup and test were shared.  Refactor them;
we'll need both parts again.  Also, we'll use the clearing routine
later.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 32 insertions(+), 13 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index 2c8b549..da41f51 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1835,32 +1835,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)
 	return hash % MAX_DELTA_CACHE;
 }
 
-static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
+static struct delta_base_cache_entry *
+get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)
 {
 	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
+	return delta_base_cache + hash;
+}
+
+static int eq_delta_base_cache_entry(struct delta_base_cache_entry *ent,
+				     struct packed_git *p, off_t base_offset)
+{
 	return (ent->data && ent->p == p && ent->base_offset == base_offset);
 }
 
+static int in_delta_base_cache(struct packed_git *p, off_t base_offset)
+{
+	struct delta_base_cache_entry *ent;
+	ent = get_delta_base_cache_entry(p, base_offset);
+	return eq_delta_base_cache_entry(ent, p, base_offset);
+}
+
+static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)
+{
+	ent->data = NULL;
+	ent->lru.next->prev = ent->lru.prev;
+	ent->lru.prev->next = ent->lru.next;
+	delta_base_cached -= ent->size;
+}
+
 static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,
 	unsigned long *base_size, enum object_type *type, int keep_cache)
 {
+	struct delta_base_cache_entry *ent;
 	void *ret;
-	unsigned long hash = pack_entry_hash(p, base_offset);
-	struct delta_base_cache_entry *ent = delta_base_cache + hash;
 
-	ret = ent->data;
-	if (!ret || ent->p != p || ent->base_offset != base_offset)
+	ent = get_delta_base_cache_entry(p, base_offset);
+
+	if (!eq_delta_base_cache_entry(ent, p, base_offset))
 		return unpack_entry(p, base_offset, type, base_size);
 
-	if (!keep_cache) {
-		ent->data = NULL;
-		ent->lru.next->prev = ent->lru.prev;
-		ent->lru.prev->next = ent->lru.next;
-		delta_base_cached -= ent->size;
-	} else {
+	ret = ent->data;
+
+	if (!keep_cache)
+		clear_delta_base_cache_entry(ent);
+	else
 		ret = xmemdupz(ent->data, ent->size);
-	}
 	*type = ent->type;
 	*base_size = ent->size;
 	return ret;
-- 
1.8.2.344.g1440b22

[PATCH v3 3/3] sha1_file: remove recursion in unpack_entry

[Thomas Rast]

Similar to the recursion in packed_object_info(), this leads to
problems on stack-space-constrained systems in the presence of long
delta chains.

We proceed in three phases:

1. Dig through the delta chain, saving each delta object's offsets and
   size on an ad-hoc stack.

2. Unpack the base object at the bottom.

3. Unpack and apply the deltas from the stack.

Signed-off-by: Thomas Rast <trast@student.ethz.ch>
---
 sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 150 insertions(+), 81 deletions(-)

diff --git a/sha1_file.c b/sha1_file.c
index da41f51..f9191aa 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1943,68 +1943,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
 static void *read_object(const unsigned char *sha1, enum object_type *type,
 			 unsigned long *size);
 
-static void *unpack_delta_entry(struct packed_git *p,
-				struct pack_window **w_curs,
-				off_t curpos,
-				unsigned long delta_size,
-				off_t obj_offset,
-				enum object_type *type,
-				unsigned long *sizep)
-{
-	void *delta_data, *result, *base;
-	unsigned long base_size;
-	off_t base_offset;
-
-	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
-	if (!base_offset) {
-		error("failed to validate delta base reference "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		return NULL;
-	}
-	unuse_pack(w_curs);
-	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
-	if (!base) {
-		/*
-		 * We're probably in deep shit, but let's try to fetch
-		 * the required base anyway from another pack or loose.
-		 * This is costly but should happen only in the presence
-		 * of a corrupted pack, and is better than failing outright.
-		 */
-		struct revindex_entry *revidx;
-		const unsigned char *base_sha1;
-		revidx = find_pack_revindex(p, base_offset);
-		if (!revidx)
-			return NULL;
-		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
-		error("failed to read delta base object %s"
-		      " at offset %"PRIuMAX" from %s",
-		      sha1_to_hex(base_sha1), (uintmax_t)base_offset,
-		      p->pack_name);
-		mark_bad_packed_object(p, base_sha1);
-		base = read_object(base_sha1, type, &base_size);
-		if (!base)
-			return NULL;
-	}
-
-	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
-	if (!delta_data) {
-		error("failed to unpack compressed delta "
-		      "at offset %"PRIuMAX" from %s",
-		      (uintmax_t)curpos, p->pack_name);
-		free(base);
-		return NULL;
-	}
-	result = patch_delta(base, base_size,
-			     delta_data, delta_size,
-			     sizep);
-	if (!result)
-		die("failed to apply delta");
-	free(delta_data);
-	add_delta_base_cache(p, base_offset, base, base_size, *type);
-	return result;
-}
-
 static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 {
 	static FILE *log_file;
@@ -2025,48 +1963,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
 
 int do_check_packed_object_crc;
 
+#define UNPACK_ENTRY_STACK_PREALLOC 64
+struct unpack_entry_stack_ent {
+	off_t obj_offset;
+	off_t curpos;
+	unsigned long size;
+};
+
 void *unpack_entry(struct packed_git *p, off_t obj_offset,
-		   enum object_type *type, unsigned long *sizep)
+		   enum object_type *final_type, unsigned long *final_size)
 {
 	struct pack_window *w_curs = NULL;
 	off_t curpos = obj_offset;
-	void *data;
+	void *data = NULL;
+	unsigned long size;
+	enum object_type type;
+	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
+	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
+	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
+	int base_from_cache = 0;
 
 	if (log_pack_access)
 		write_pack_access_log(p, obj_offset);
 
-	if (do_check_packed_object_crc && p->index_version > 1) {
-		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
-		unsigned long len = revidx[1].offset - obj_offset;
-		if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
-			const unsigned char *sha1 =
-				nth_packed_object_sha1(p, revidx->nr);
-			error("bad packed object CRC for %s",
-			      sha1_to_hex(sha1));
-			mark_bad_packed_object(p, sha1);
-			unuse_pack(&w_curs);
-			return NULL;
+	/* PHASE 1: drill down to the innermost base object */
+	for (;;) {
+		off_t base_offset;
+		int i;
+		struct delta_base_cache_entry *ent;
+
+		if (do_check_packed_object_crc && p->index_version > 1) {
+			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
+			unsigned long len = revidx[1].offset - obj_offset;
+			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
+				const unsigned char *sha1 =
+					nth_packed_object_sha1(p, revidx->nr);
+				error("bad packed object CRC for %s",
+				      sha1_to_hex(sha1));
+				mark_bad_packed_object(p, sha1);
+				unuse_pack(&w_curs);
+				return NULL;
+			}
+		}
+
+		ent = get_delta_base_cache_entry(p, curpos);
+		if (eq_delta_base_cache_entry(ent, p, curpos)) {
+			type = ent->type;
+			data = ent->data;
+			size = ent->size;
+			clear_delta_base_cache_entry(ent);
+			base_from_cache = 1;
+			break;
+		}
+
+		type = unpack_object_header(p, &w_curs, &curpos, &size);
+		if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
+			break;
+
+		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
+		if (!base_offset) {
+			error("failed to validate delta base reference "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			/* bail to phase 2, in hopes of recovery */
+			data = NULL;
+			break;
 		}
+
+		/* push object, proceed to base */
+		if (delta_stack_nr >= delta_stack_alloc
+		    && delta_stack == small_delta_stack) {
+			delta_stack_alloc = alloc_nr(delta_stack_nr);
+			delta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);
+			memcpy(delta_stack, small_delta_stack,
+			       sizeof(*delta_stack)*delta_stack_nr);
+		} else {
+			ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
+		}
+		i = delta_stack_nr++;
+		delta_stack[i].obj_offset = obj_offset;
+		delta_stack[i].curpos = curpos;
+		delta_stack[i].size = size;
+
+		curpos = obj_offset = base_offset;
 	}
 
-	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
-	switch (*type) {
+	/* PHASE 2: handle the base */
+	switch (type) {
 	case OBJ_OFS_DELTA:
 	case OBJ_REF_DELTA:
-		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
-					  obj_offset, type, sizep);
+		if (data)
+			die("BUG in unpack_entry: left loop at a valid delta");
 		break;
 	case OBJ_COMMIT:
 	case OBJ_TREE:
 	case OBJ_BLOB:
 	case OBJ_TAG:
-		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
+		if (!base_from_cache)
+			data = unpack_compressed_entry(p, &w_curs, curpos, size);
 		break;
 	default:
 		data = NULL;
 		error("unknown object type %i at offset %"PRIuMAX" in %s",
-		      *type, (uintmax_t)obj_offset, p->pack_name);
+		      type, (uintmax_t)obj_offset, p->pack_name);
 	}
+
+	/* PHASE 3: apply deltas in order */
+
+	/* invariants:
+	 *   'data' holds the base data, or NULL if there was corruption
+	 */
+	while (delta_stack_nr) {
+		void *delta_data;
+		void *base = data;
+		unsigned long delta_size, base_size = size;
+		int i;
+
+		data = NULL;
+
+		if (base)
+			add_delta_base_cache(p, obj_offset, base, base_size, type);
+
+		if (!base) {
+			/*
+			 * We're probably in deep shit, but let's try to fetch
+			 * the required base anyway from another pack or loose.
+			 * This is costly but should happen only in the presence
+			 * of a corrupted pack, and is better than failing outright.
+			 */
+			struct revindex_entry *revidx;
+			const unsigned char *base_sha1;
+			revidx = find_pack_revindex(p, obj_offset);
+			if (revidx) {
+				base_sha1 = nth_packed_object_sha1(p, revidx->nr);
+				error("failed to read delta base object %s"
+				      " at offset %"PRIuMAX" from %s",
+				      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
+				      p->pack_name);
+				mark_bad_packed_object(p, base_sha1);
+				base = read_object(base_sha1, &type, &base_size);
+			}
+		}
+
+		i = --delta_stack_nr;
+		obj_offset = delta_stack[i].obj_offset;
+		curpos = delta_stack[i].curpos;
+		delta_size = delta_stack[i].size;
+
+		if (!base)
+			continue;
+
+		delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
+
+		if (!delta_data) {
+			error("failed to unpack compressed delta "
+			      "at offset %"PRIuMAX" from %s",
+			      (uintmax_t)curpos, p->pack_name);
+			free(base);
+			data = NULL;
+			continue;
+		}
+
+		data = patch_delta(base, base_size,
+				   delta_data, delta_size,
+				   &size);
+		if (!data)
+			die("failed to apply delta");
+
+		free (delta_data);
+	}
+
+	*final_type = type;
+	*final_size = size;
+
 	unuse_pack(&w_curs);
 	return data;
 }
-- 
1.8.2.344.g1440b22

Re: [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry

[Junio C Hamano]

Thomas Rast <trast@student.ethz.ch> writes:

> Similar to the recursion in packed_object_info(), this leads to
> problems on stack-space-constrained systems in the presence of long
> delta chains.
>
> We proceed in three phases:
>
> 1. Dig through the delta chain, saving each delta object's offsets and
>    size on an ad-hoc stack.
>
> 2. Unpack the base object at the bottom.
>
> 3. Unpack and apply the deltas from the stack.
>
> Signed-off-by: Thomas Rast <trast@student.ethz.ch>
> ---

Sounds sensible.

Do we keep the packfiles open that hold the deltas involved in the
chain so that they won't be removed by a concurrent repack?  I do
not think this rewrite changes anything with respect to that access
pattern, though.

Will replace and merge to 'next'.  Thanks.

>  sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------
>  1 file changed, 150 insertions(+), 81 deletions(-)
>
> diff --git a/sha1_file.c b/sha1_file.c
> index da41f51..f9191aa 100644
> --- a/sha1_file.c
> +++ b/sha1_file.c
> @@ -1943,68 +1943,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,
>  static void *read_object(const unsigned char *sha1, enum object_type *type,
>  			 unsigned long *size);
>  
> -static void *unpack_delta_entry(struct packed_git *p,
> -				struct pack_window **w_curs,
> -				off_t curpos,
> -				unsigned long delta_size,
> -				off_t obj_offset,
> -				enum object_type *type,
> -				unsigned long *sizep)
> -{
> -	void *delta_data, *result, *base;
> -	unsigned long base_size;
> -	off_t base_offset;
> -
> -	base_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);
> -	if (!base_offset) {
> -		error("failed to validate delta base reference "
> -		      "at offset %"PRIuMAX" from %s",
> -		      (uintmax_t)curpos, p->pack_name);
> -		return NULL;
> -	}
> -	unuse_pack(w_curs);
> -	base = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);
> -	if (!base) {
> -		/*
> -		 * We're probably in deep shit, but let's try to fetch
> -		 * the required base anyway from another pack or loose.
> -		 * This is costly but should happen only in the presence
> -		 * of a corrupted pack, and is better than failing outright.
> -		 */
> -		struct revindex_entry *revidx;
> -		const unsigned char *base_sha1;
> -		revidx = find_pack_revindex(p, base_offset);
> -		if (!revidx)
> -			return NULL;
> -		base_sha1 = nth_packed_object_sha1(p, revidx->nr);
> -		error("failed to read delta base object %s"
> -		      " at offset %"PRIuMAX" from %s",
> -		      sha1_to_hex(base_sha1), (uintmax_t)base_offset,
> -		      p->pack_name);
> -		mark_bad_packed_object(p, base_sha1);
> -		base = read_object(base_sha1, type, &base_size);
> -		if (!base)
> -			return NULL;
> -	}
> -
> -	delta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);
> -	if (!delta_data) {
> -		error("failed to unpack compressed delta "
> -		      "at offset %"PRIuMAX" from %s",
> -		      (uintmax_t)curpos, p->pack_name);
> -		free(base);
> -		return NULL;
> -	}
> -	result = patch_delta(base, base_size,
> -			     delta_data, delta_size,
> -			     sizep);
> -	if (!result)
> -		die("failed to apply delta");
> -	free(delta_data);
> -	add_delta_base_cache(p, base_offset, base, base_size, *type);
> -	return result;
> -}
> -
>  static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
>  {
>  	static FILE *log_file;
> @@ -2025,48 +1963,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)
>  
>  int do_check_packed_object_crc;
>  
> +#define UNPACK_ENTRY_STACK_PREALLOC 64
> +struct unpack_entry_stack_ent {
> +	off_t obj_offset;
> +	off_t curpos;
> +	unsigned long size;
> +};
> +
>  void *unpack_entry(struct packed_git *p, off_t obj_offset,
> -		   enum object_type *type, unsigned long *sizep)
> +		   enum object_type *final_type, unsigned long *final_size)
>  {
>  	struct pack_window *w_curs = NULL;
>  	off_t curpos = obj_offset;
> -	void *data;
> +	void *data = NULL;
> +	unsigned long size;
> +	enum object_type type;
> +	struct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];
> +	struct unpack_entry_stack_ent *delta_stack = small_delta_stack;
> +	int delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;
> +	int base_from_cache = 0;
>  
>  	if (log_pack_access)
>  		write_pack_access_log(p, obj_offset);
>  
> -	if (do_check_packed_object_crc && p->index_version > 1) {
> -		struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
> -		unsigned long len = revidx[1].offset - obj_offset;
> -		if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
> -			const unsigned char *sha1 =
> -				nth_packed_object_sha1(p, revidx->nr);
> -			error("bad packed object CRC for %s",
> -			      sha1_to_hex(sha1));
> -			mark_bad_packed_object(p, sha1);
> -			unuse_pack(&w_curs);
> -			return NULL;
> +	/* PHASE 1: drill down to the innermost base object */
> +	for (;;) {
> +		off_t base_offset;
> +		int i;
> +		struct delta_base_cache_entry *ent;
> +
> +		if (do_check_packed_object_crc && p->index_version > 1) {
> +			struct revindex_entry *revidx = find_pack_revindex(p, obj_offset);
> +			unsigned long len = revidx[1].offset - obj_offset;
> +			if (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {
> +				const unsigned char *sha1 =
> +					nth_packed_object_sha1(p, revidx->nr);
> +				error("bad packed object CRC for %s",
> +				      sha1_to_hex(sha1));
> +				mark_bad_packed_object(p, sha1);
> +				unuse_pack(&w_curs);
> +				return NULL;
> +			}
> +		}
> +
> +		ent = get_delta_base_cache_entry(p, curpos);
> +		if (eq_delta_base_cache_entry(ent, p, curpos)) {
> +			type = ent->type;
> +			data = ent->data;
> +			size = ent->size;
> +			clear_delta_base_cache_entry(ent);
> +			base_from_cache = 1;
> +			break;
> +		}
> +
> +		type = unpack_object_header(p, &w_curs, &curpos, &size);
> +		if (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)
> +			break;
> +
> +		base_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);
> +		if (!base_offset) {
> +			error("failed to validate delta base reference "
> +			      "at offset %"PRIuMAX" from %s",
> +			      (uintmax_t)curpos, p->pack_name);
> +			/* bail to phase 2, in hopes of recovery */
> +			data = NULL;
> +			break;
>  		}
> +
> +		/* push object, proceed to base */
> +		if (delta_stack_nr >= delta_stack_alloc
> +		    && delta_stack == small_delta_stack) {
> +			delta_stack_alloc = alloc_nr(delta_stack_nr);
> +			delta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);
> +			memcpy(delta_stack, small_delta_stack,
> +			       sizeof(*delta_stack)*delta_stack_nr);
> +		} else {
> +			ALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);
> +		}
> +		i = delta_stack_nr++;
> +		delta_stack[i].obj_offset = obj_offset;
> +		delta_stack[i].curpos = curpos;
> +		delta_stack[i].size = size;
> +
> +		curpos = obj_offset = base_offset;
>  	}
>  
> -	*type = unpack_object_header(p, &w_curs, &curpos, sizep);
> -	switch (*type) {
> +	/* PHASE 2: handle the base */
> +	switch (type) {
>  	case OBJ_OFS_DELTA:
>  	case OBJ_REF_DELTA:
> -		data = unpack_delta_entry(p, &w_curs, curpos, *sizep,
> -					  obj_offset, type, sizep);
> +		if (data)
> +			die("BUG in unpack_entry: left loop at a valid delta");
>  		break;
>  	case OBJ_COMMIT:
>  	case OBJ_TREE:
>  	case OBJ_BLOB:
>  	case OBJ_TAG:
> -		data = unpack_compressed_entry(p, &w_curs, curpos, *sizep);
> +		if (!base_from_cache)
> +			data = unpack_compressed_entry(p, &w_curs, curpos, size);
>  		break;
>  	default:
>  		data = NULL;
>  		error("unknown object type %i at offset %"PRIuMAX" in %s",
> -		      *type, (uintmax_t)obj_offset, p->pack_name);
> +		      type, (uintmax_t)obj_offset, p->pack_name);
>  	}
> +
> +	/* PHASE 3: apply deltas in order */
> +
> +	/* invariants:
> +	 *   'data' holds the base data, or NULL if there was corruption
> +	 */
> +	while (delta_stack_nr) {
> +		void *delta_data;
> +		void *base = data;
> +		unsigned long delta_size, base_size = size;
> +		int i;
> +
> +		data = NULL;
> +
> +		if (base)
> +			add_delta_base_cache(p, obj_offset, base, base_size, type);
> +
> +		if (!base) {
> +			/*
> +			 * We're probably in deep shit, but let's try to fetch
> +			 * the required base anyway from another pack or loose.
> +			 * This is costly but should happen only in the presence
> +			 * of a corrupted pack, and is better than failing outright.
> +			 */
> +			struct revindex_entry *revidx;
> +			const unsigned char *base_sha1;
> +			revidx = find_pack_revindex(p, obj_offset);
> +			if (revidx) {
> +				base_sha1 = nth_packed_object_sha1(p, revidx->nr);
> +				error("failed to read delta base object %s"
> +				      " at offset %"PRIuMAX" from %s",
> +				      sha1_to_hex(base_sha1), (uintmax_t)obj_offset,
> +				      p->pack_name);
> +				mark_bad_packed_object(p, base_sha1);
> +				base = read_object(base_sha1, &type, &base_size);
> +			}
> +		}
> +
> +		i = --delta_stack_nr;
> +		obj_offset = delta_stack[i].obj_offset;
> +		curpos = delta_stack[i].curpos;
> +		delta_size = delta_stack[i].size;
> +
> +		if (!base)
> +			continue;
> +
> +		delta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);
> +
> +		if (!delta_data) {
> +			error("failed to unpack compressed delta "
> +			      "at offset %"PRIuMAX" from %s",
> +			      (uintmax_t)curpos, p->pack_name);
> +			free(base);
> +			data = NULL;
> +			continue;
> +		}
> +
> +		data = patch_delta(base, base_size,
> +				   delta_data, delta_size,
> +				   &size);
> +		if (!data)
> +			die("failed to apply delta");
> +
> +		free (delta_data);
> +	}
> +
> +	*final_type = type;
> +	*final_size = size;
> +
>  	unuse_pack(&w_curs);
>  	return data;
>  }