* regression in multi-threaded git-pack-index @ 2013-03-15 22:42 Stefan Zager 2013-03-16 11:41 ` Jeff King 2013-03-19 15:41 ` regression in multi-threaded git-pack-index Thomas Rast 0 siblings, 2 replies; 51+ messages in thread From: Stefan Zager @ 2013-03-15 22:42 UTC (permalink / raw) To: git 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-15 22:42 regression in multi-threaded git-pack-index Stefan Zager @ 2013-03-16 11:41 ` Jeff King 2013-03-16 12:38 ` Duy Nguyen 2013-03-19 8:17 ` Thomas Rast 2013-03-19 15:41 ` regression in multi-threaded git-pack-index Thomas Rast 1 sibling, 2 replies; 51+ messages in thread From: Jeff King @ 2013-03-16 11:41 UTC (permalink / raw) To: Stefan Zager; +Cc: git 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-16 11:41 ` Jeff King @ 2013-03-16 12:38 ` Duy Nguyen 2013-03-19 8:17 ` Thomas Rast 1 sibling, 0 replies; 51+ messages in thread From: Duy Nguyen @ 2013-03-16 12:38 UTC (permalink / raw) To: Stefan Zager; +Cc: Jeff King, git 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-16 11:41 ` Jeff King 2013-03-16 12:38 ` Duy Nguyen @ 2013-03-19 8:17 ` Thomas Rast 2013-03-19 9:30 ` Jeff King 2013-03-19 12:35 ` regression in multi-threaded git-pack-index Duy Nguyen 1 sibling, 2 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-19 8:17 UTC (permalink / raw) To: Jeff King; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 8:17 ` Thomas Rast @ 2013-03-19 9:30 ` Jeff King 2013-03-19 9:59 ` Jeff King 2013-03-19 12:35 ` regression in multi-threaded git-pack-index Duy Nguyen 1 sibling, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 9:30 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 9:30 ` Jeff King @ 2013-03-19 9:59 ` Jeff King 2013-03-19 10:08 ` Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 9:59 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 9:59 ` Jeff King @ 2013-03-19 10:08 ` Jeff King 2013-03-19 10:24 ` Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 10:08 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 10:08 ` Jeff King @ 2013-03-19 10:24 ` Jeff King 2013-03-19 10:29 ` Thomas Rast 2013-03-19 10:58 ` [PATCH] index-pack: always zero-initialize object_entry list Jeff King 0 siblings, 2 replies; 51+ messages in thread From: Jeff King @ 2013-03-19 10:24 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 10:24 ` Jeff King @ 2013-03-19 10:29 ` Thomas Rast 2013-03-19 10:33 ` Jeff King 2013-03-19 10:58 ` [PATCH] index-pack: always zero-initialize object_entry list Jeff King 1 sibling, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 10:29 UTC (permalink / raw) To: Jeff King Cc: Thomas Rast, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 10:29 ` Thomas Rast @ 2013-03-19 10:33 ` Jeff King 2013-03-19 10:45 ` Thomas Rast 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 10:33 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 10:33 ` Jeff King @ 2013-03-19 10:45 ` Thomas Rast 2013-03-19 10:47 ` Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 10:45 UTC (permalink / raw) To: Jeff King; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 10:45 ` Thomas Rast @ 2013-03-19 10:47 ` Jeff King 0 siblings, 0 replies; 51+ messages in thread From: Jeff King @ 2013-03-19 10:47 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH] index-pack: always zero-initialize object_entry list 2013-03-19 10:24 ` Jeff King 2013-03-19 10:29 ` Thomas Rast @ 2013-03-19 10:58 ` Jeff King 2013-03-19 15:33 ` Thomas Rast 1 sibling, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 10:58 UTC (permalink / raw) To: Thomas Rast Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: always zero-initialize object_entry list 2013-03-19 10:58 ` [PATCH] index-pack: always zero-initialize object_entry list Jeff King @ 2013-03-19 15:33 ` Thomas Rast 2013-03-19 15:43 ` Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 15:33 UTC (permalink / raw) To: Jeff King Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: always zero-initialize object_entry list 2013-03-19 15:33 ` Thomas Rast @ 2013-03-19 15:43 ` Jeff King 2013-03-19 15:52 ` Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 15:43 UTC (permalink / raw) To: Thomas Rast Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: always zero-initialize object_entry list 2013-03-19 15:43 ` Jeff King @ 2013-03-19 15:52 ` Jeff King 2013-03-19 16:17 ` [PATCH v2] " Jeff King 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-19 15:52 UTC (permalink / raw) To: Thomas Rast Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-19 15:52 ` Jeff King @ 2013-03-19 16:17 ` Jeff King 2013-03-19 16:27 ` Thomas Rast 2013-03-20 19:12 ` Eric Sunshine 0 siblings, 2 replies; 51+ messages in thread From: Jeff King @ 2013-03-19 16:17 UTC (permalink / raw) To: Thomas Rast Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-19 16:17 ` [PATCH v2] " Jeff King @ 2013-03-19 16:27 ` Thomas Rast 2013-03-19 17:13 ` Junio C Hamano 2013-03-20 19:12 ` Eric Sunshine 1 sibling, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 16:27 UTC (permalink / raw) To: Jeff King Cc: Junio C Hamano, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-19 16:27 ` Thomas Rast @ 2013-03-19 17:13 ` Junio C Hamano 0 siblings, 0 replies; 51+ messages in thread From: Junio C Hamano @ 2013-03-19 17:13 UTC (permalink / raw) To: Thomas Rast Cc: Jeff King, Stefan Zager, git, Nguyễn Thái Ngọc Duy 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. ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-19 16:17 ` [PATCH v2] " Jeff King 2013-03-19 16:27 ` Thomas Rast @ 2013-03-20 19:12 ` Eric Sunshine 2013-03-20 19:13 ` Jeff King 1 sibling, 1 reply; 51+ messages in thread From: Eric Sunshine @ 2013-03-20 19:12 UTC (permalink / raw) To: Jeff King Cc: Thomas Rast, Junio C Hamano, Stefan Zager, Git List, Nguyễn Thái Ngọc 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. ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-20 19:12 ` Eric Sunshine @ 2013-03-20 19:13 ` Jeff King 2013-03-20 19:14 ` Eric Sunshine 0 siblings, 1 reply; 51+ messages in thread From: Jeff King @ 2013-03-20 19:13 UTC (permalink / raw) To: Eric Sunshine Cc: Thomas Rast, Junio C Hamano, Stefan Zager, Git List, Nguyễn Thái Ngọc 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: always zero-initialize object_entry list 2013-03-20 19:13 ` Jeff King @ 2013-03-20 19:14 ` Eric Sunshine 0 siblings, 0 replies; 51+ messages in thread From: Eric Sunshine @ 2013-03-20 19:14 UTC (permalink / raw) To: Jeff King Cc: Thomas Rast, Junio C Hamano, Stefan Zager, Git List, Nguyễn Thái Ngọc 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 8:17 ` Thomas Rast 2013-03-19 9:30 ` Jeff King @ 2013-03-19 12:35 ` Duy Nguyen 2013-03-19 13:01 ` [PATCH] index-pack: protect deepest_delta in multithread code Nguyễn Thái Ngọc Duy 1 sibling, 1 reply; 51+ messages in thread From: Duy Nguyen @ 2013-03-19 12:35 UTC (permalink / raw) To: Thomas Rast; +Cc: Jeff King, Stefan Zager, git 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH] index-pack: protect deepest_delta in multithread code 2013-03-19 12:35 ` regression in multi-threaded git-pack-index Duy Nguyen @ 2013-03-19 13:01 ` Nguyễn Thái Ngọc Duy 2013-03-19 13:25 ` Jeff King 2013-03-19 13:50 ` Thomas Rast 0 siblings, 2 replies; 51+ messages in thread From: Nguyễn Thái Ngọc Duy @ 2013-03-19 13:01 UTC (permalink / raw) To: git Cc: Junio C Hamano, Jeff King, Thomas Rast, Stefan Zager, 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: protect deepest_delta in multithread code 2013-03-19 13:01 ` [PATCH] index-pack: protect deepest_delta in multithread code Nguyễn Thái Ngọc Duy @ 2013-03-19 13:25 ` Jeff King 2013-03-19 13:50 ` Thomas Rast 1 sibling, 0 replies; 51+ messages in thread From: Jeff King @ 2013-03-19 13:25 UTC (permalink / raw) To: Nguyễn Thái Ngọc Duy Cc: git, Junio C Hamano, Thomas Rast, Stefan Zager 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: protect deepest_delta in multithread code 2013-03-19 13:01 ` [PATCH] index-pack: protect deepest_delta in multithread code Nguyễn Thái Ngọc Duy 2013-03-19 13:25 ` Jeff King @ 2013-03-19 13:50 ` Thomas Rast 2013-03-19 14:07 ` Duy Nguyen 1 sibling, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 13:50 UTC (permalink / raw) To: Nguyễn Thái Ngọc Duy Cc: git, Junio C Hamano, Jeff King, Thomas Rast, Stefan Zager 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH] index-pack: protect deepest_delta in multithread code 2013-03-19 13:50 ` Thomas Rast @ 2013-03-19 14:07 ` Duy Nguyen 2013-03-19 14:16 ` [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock Thomas Rast 0 siblings, 1 reply; 51+ messages in thread From: Duy Nguyen @ 2013-03-19 14:07 UTC (permalink / raw) To: Thomas Rast; +Cc: git, Junio C Hamano, Jeff King, Stefan Zager 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock 2013-03-19 14:07 ` Duy Nguyen @ 2013-03-19 14:16 ` Thomas Rast 2013-03-19 15:53 ` Junio C Hamano 0 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 14:16 UTC (permalink / raw) To: Nguyễn Thái Ngọc Duy Cc: git, Junio C Hamano, Jeff King, Stefan Zager 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock 2013-03-19 14:16 ` [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock Thomas Rast @ 2013-03-19 15:53 ` Junio C Hamano 0 siblings, 0 replies; 51+ messages in thread From: Junio C Hamano @ 2013-03-19 15:53 UTC (permalink / raw) To: Thomas Rast Cc: Nguyễn Thái Ngọc Duy, git, Jeff King, Stefan Zager 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. ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-15 22:42 regression in multi-threaded git-pack-index Stefan Zager 2013-03-16 11:41 ` Jeff King @ 2013-03-19 15:41 ` Thomas Rast 2013-03-19 15:45 ` Thomas Rast 1 sibling, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 15:41 UTC (permalink / raw) To: Stefan Zager Cc: git, Jeff King, Nguyễn Thái Ngọc Duy, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 15:41 ` regression in multi-threaded git-pack-index Thomas Rast @ 2013-03-19 15:45 ` Thomas Rast 2013-03-19 16:11 ` Thomas Rast 0 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 15:45 UTC (permalink / raw) To: Thomas Rast Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 15:45 ` Thomas Rast @ 2013-03-19 16:11 ` Thomas Rast 2013-03-19 17:58 ` Junio C Hamano 2013-03-20 1:17 ` regression in multi-threaded git-pack-index Duy Nguyen 0 siblings, 2 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-19 16:11 UTC (permalink / raw) To: Thomas Rast Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 16:11 ` Thomas Rast @ 2013-03-19 17:58 ` Junio C Hamano 2013-03-19 22:08 ` [PATCH] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-20 1:17 ` regression in multi-threaded git-pack-index Duy Nguyen 1 sibling, 1 reply; 51+ messages in thread From: Junio C Hamano @ 2013-03-19 17:58 UTC (permalink / raw) To: Thomas Rast Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy 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(); ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH] sha1_file: remove recursion in packed_object_info 2013-03-19 17:58 ` Junio C Hamano @ 2013-03-19 22:08 ` Thomas Rast 2013-03-20 16:47 ` Junio C Hamano 0 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-19 22:08 UTC (permalink / raw) To: Junio C Hamano Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH] sha1_file: remove recursion in packed_object_info 2013-03-19 22:08 ` [PATCH] sha1_file: remove recursion in packed_object_info Thomas Rast @ 2013-03-20 16:47 ` Junio C Hamano 2013-03-25 9:27 ` thomas 0 siblings, 1 reply; 51+ messages in thread From: Junio C Hamano @ 2013-03-20 16:47 UTC (permalink / raw) To: Thomas Rast Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy 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. ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH] sha1_file: remove recursion in packed_object_info 2013-03-20 16:47 ` Junio C Hamano @ 2013-03-25 9:27 ` thomas 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast ` (2 more replies) 0 siblings, 3 replies; 51+ messages in thread From: thomas @ 2013-03-25 9:27 UTC (permalink / raw) To: Junio C Hamano Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info 2013-03-25 9:27 ` thomas @ 2013-03-25 18:07 ` Thomas Rast 2013-03-25 18:07 ` [PATCH v2 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast ` (3 more replies) 2013-03-25 18:17 ` [PATCH] sha1_file: remove recursion in packed_object_info Junio C Hamano 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2 siblings, 4 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-25 18:07 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v2 1/3] sha1_file: remove recursion in packed_object_info 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast @ 2013-03-25 18:07 ` Thomas Rast 2013-03-25 18:07 ` [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast ` (2 subsequent siblings) 3 siblings, 0 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-25 18:07 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-25 18:07 ` [PATCH v2 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast @ 2013-03-25 18:07 ` Thomas Rast 2013-03-25 23:15 ` Junio C Hamano 2013-03-25 18:07 ` [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast 2013-03-26 3:37 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Nicolas Pitre 3 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-25 18:07 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry 2013-03-25 18:07 ` [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast @ 2013-03-25 23:15 ` Junio C Hamano 2013-03-26 11:09 ` thomas 0 siblings, 1 reply; 51+ messages in thread From: Junio C Hamano @ 2013-03-25 23:15 UTC (permalink / raw) To: Thomas Rast Cc: git, Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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; ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry 2013-03-25 23:15 ` Junio C Hamano @ 2013-03-26 11:09 ` thomas 0 siblings, 0 replies; 51+ messages in thread From: thomas @ 2013-03-26 11:09 UTC (permalink / raw) To: Junio C Hamano Cc: git, Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-25 18:07 ` [PATCH v2 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-25 18:07 ` [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast @ 2013-03-25 18:07 ` Thomas Rast 2013-03-25 23:19 ` Junio C Hamano 2013-03-26 3:37 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Nicolas Pitre 3 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-25 18:07 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry 2013-03-25 18:07 ` [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast @ 2013-03-25 23:19 ` Junio C Hamano 0 siblings, 0 replies; 51+ messages in thread From: Junio C Hamano @ 2013-03-25 23:19 UTC (permalink / raw) To: Thomas Rast Cc: git, Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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; > } ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast ` (2 preceding siblings ...) 2013-03-25 18:07 ` [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast @ 2013-03-26 3:37 ` Nicolas Pitre 3 siblings, 0 replies; 51+ messages in thread From: Nicolas Pitre @ 2013-03-26 3:37 UTC (permalink / raw) To: Thomas Rast Cc: git, Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: [PATCH] sha1_file: remove recursion in packed_object_info 2013-03-25 9:27 ` thomas 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast @ 2013-03-25 18:17 ` Junio C Hamano 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2 siblings, 0 replies; 51+ messages in thread From: Junio C Hamano @ 2013-03-25 18:17 UTC (permalink / raw) To: thomas Cc: Stefan Zager, git, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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. ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info 2013-03-25 9:27 ` thomas 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-25 18:17 ` [PATCH] sha1_file: remove recursion in packed_object_info Junio C Hamano @ 2013-03-27 20:03 ` Thomas Rast 2013-03-27 20:03 ` [PATCH v3 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast ` (2 more replies) 2 siblings, 3 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-27 20:03 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano, 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
* [PATCH v3 1/3] sha1_file: remove recursion in packed_object_info 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast @ 2013-03-27 20:03 ` Thomas Rast 2013-03-27 20:03 ` [PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast 2013-03-27 20:03 ` [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast 2 siblings, 0 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-27 20:03 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* [PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-27 20:03 ` [PATCH v3 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast @ 2013-03-27 20:03 ` Thomas Rast 2013-03-27 20:03 ` [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast 2 siblings, 0 replies; 51+ messages in thread From: Thomas Rast @ 2013-03-27 20:03 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-27 20:03 ` [PATCH v3 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-27 20:03 ` [PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast @ 2013-03-27 20:03 ` Thomas Rast 2013-03-27 20:29 ` Junio C Hamano 2 siblings, 1 reply; 51+ messages in thread From: Thomas Rast @ 2013-03-27 20:03 UTC (permalink / raw) To: git Cc: Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre, Junio C Hamano 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 ^ permalink raw reply related [flat|nested] 51+ messages in thread
* Re: [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry 2013-03-27 20:03 ` [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast @ 2013-03-27 20:29 ` Junio C Hamano 0 siblings, 0 replies; 51+ messages in thread From: Junio C Hamano @ 2013-03-27 20:29 UTC (permalink / raw) To: Thomas Rast Cc: git, Stefan Zager, Jeff King, Nguyễn Thái Ngọc Duy, Nicolas Pitre 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; > } ^ permalink raw reply [flat|nested] 51+ messages in thread
* Re: regression in multi-threaded git-pack-index 2013-03-19 16:11 ` Thomas Rast 2013-03-19 17:58 ` Junio C Hamano @ 2013-03-20 1:17 ` Duy Nguyen 1 sibling, 0 replies; 51+ messages in thread From: Duy Nguyen @ 2013-03-20 1:17 UTC (permalink / raw) To: Thomas Rast; +Cc: Stefan Zager, git, Jeff King, Junio C Hamano 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 ^ permalink raw reply [flat|nested] 51+ messages in thread
end of thread, other threads:[~2013-03-27 20:30 UTC | newest] Thread overview: 51+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2013-03-15 22:42 regression in multi-threaded git-pack-index Stefan Zager 2013-03-16 11:41 ` Jeff King 2013-03-16 12:38 ` Duy Nguyen 2013-03-19 8:17 ` Thomas Rast 2013-03-19 9:30 ` Jeff King 2013-03-19 9:59 ` Jeff King 2013-03-19 10:08 ` Jeff King 2013-03-19 10:24 ` Jeff King 2013-03-19 10:29 ` Thomas Rast 2013-03-19 10:33 ` Jeff King 2013-03-19 10:45 ` Thomas Rast 2013-03-19 10:47 ` Jeff King 2013-03-19 10:58 ` [PATCH] index-pack: always zero-initialize object_entry list Jeff King 2013-03-19 15:33 ` Thomas Rast 2013-03-19 15:43 ` Jeff King 2013-03-19 15:52 ` Jeff King 2013-03-19 16:17 ` [PATCH v2] " Jeff King 2013-03-19 16:27 ` Thomas Rast 2013-03-19 17:13 ` Junio C Hamano 2013-03-20 19:12 ` Eric Sunshine 2013-03-20 19:13 ` Jeff King 2013-03-20 19:14 ` Eric Sunshine 2013-03-19 12:35 ` regression in multi-threaded git-pack-index Duy Nguyen 2013-03-19 13:01 ` [PATCH] index-pack: protect deepest_delta in multithread code Nguyễn Thái Ngọc Duy 2013-03-19 13:25 ` Jeff King 2013-03-19 13:50 ` Thomas Rast 2013-03-19 14:07 ` Duy Nguyen 2013-03-19 14:16 ` [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock Thomas Rast 2013-03-19 15:53 ` Junio C Hamano 2013-03-19 15:41 ` regression in multi-threaded git-pack-index Thomas Rast 2013-03-19 15:45 ` Thomas Rast 2013-03-19 16:11 ` Thomas Rast 2013-03-19 17:58 ` Junio C Hamano 2013-03-19 22:08 ` [PATCH] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-20 16:47 ` Junio C Hamano 2013-03-25 9:27 ` thomas 2013-03-25 18:07 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-25 18:07 ` [PATCH v2 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-25 18:07 ` [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast 2013-03-25 23:15 ` Junio C Hamano 2013-03-26 11:09 ` thomas 2013-03-25 18:07 ` [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast 2013-03-25 23:19 ` Junio C Hamano 2013-03-26 3:37 ` [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info Nicolas Pitre 2013-03-25 18:17 ` [PATCH] sha1_file: remove recursion in packed_object_info Junio C Hamano 2013-03-27 20:03 ` [PATCH v3 0/3] Recursion-free unpack_entry and packed_object_info Thomas Rast 2013-03-27 20:03 ` [PATCH v3 1/3] sha1_file: remove recursion in packed_object_info Thomas Rast 2013-03-27 20:03 ` [PATCH v3 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry Thomas Rast 2013-03-27 20:03 ` [PATCH v3 3/3] sha1_file: remove recursion in unpack_entry Thomas Rast 2013-03-27 20:29 ` Junio C Hamano 2013-03-20 1:17 ` regression in multi-threaded git-pack-index Duy Nguyen
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.