{"thread":{"id":"33193","subject":"regression in multi-threaded git-pack-index","startedAt":"2013-03-15T22:42:40Z","lastAt":"2013-03-26T11:09:59Z","messageCount":46,"participants":["Stefan Zager","Jeff King","Duy Nguyen","Thomas Rast","Nguyễn Thái Ngọc Duy","Junio C Hamano","Eric Sunshine","thomas","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"211422","messageId":"20130315224240.50AA340839@wince.sfo.corp.google.com","threadId":"33193","inReplyTo":null,"subject":"regression in multi-threaded git-pack-index","fromName":"Stefan Zager","fromEmail":"szager@google.com","sentAt":"2013-03-15T22:42:40Z","receivedAt":"2013-03-15T22:42:40Z","isPatch":false,"sender":{"key":"szager@google.com","avatar":null},"body":"We have uncovered a regression in this commit:\n\nb8a2486f1524947f232f657e9f2ebf44e3e7a243\n\nThe symptom is that 'git fetch' dies with:\n\nerror: index-pack died of signal 10\nfatal: index-pack failed\n\nI have only been able to reproduce it on a Mac thus far; will try ubuntu next. We can make it go away by running:\n\ngit config pack.threads 1\n\nTo reproduce it, download this working copy:\n\nhttp://commondatastorage.googleapis.com/chromium-browser-snapshots/tmp/src.git.tar.gz\n\nThen:\n\ntar xvfz src.git.tar.gz\ncd src.git\ngit fetch origin refs/heads/lkgr\n\n(That is the shortest reproduction I could come up with; sorry).\n\nThanks,\n\nStefan\n"},{"id":"211453","messageId":"20130316114118.GA1940@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130315224240.50AA340839@wince.sfo.corp.google.com","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-16T11:41:19Z","receivedAt":"2013-03-16T11:41:19Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:\n\n> We have uncovered a regression in this commit:\n> \n> b8a2486f1524947f232f657e9f2ebf44e3e7a243\n> \n> The symptom is that 'git fetch' dies with:\n> \n> error: index-pack died of signal 10\n> fatal: index-pack failed\n> \n> I have only been able to reproduce it on a Mac thus far; will try\n> ubuntu next. We can make it go away by running:\n> \n> git config pack.threads 1\n\nI couldn't reproduce the problem on Linux with the instructions you\ngave. I did try running it under valgrind and it produced:\n\n ==2380== Conditional jump or move depends on uninitialised value(s)\n ==2380== at 0x441631: resolve_delta (index-pack.c:837)\n ==2380== by 0x4419D6: find_unresolved_deltas_1 (index-pack.c:898)\n ==2380== by 0x441A45: find_unresolved_deltas (index-pack.c:914)\n ==2380== by 0x4427CA: fix_unresolved_deltas (index-pack.c:1232)\n ==2380== by 0x4421F5: conclude_pack (index-pack.c:1111)\n ==2380== by 0x443A5C: cmd_index_pack (index-pack.c:1604)\n ==2380== by 0x4058A2: run_builtin (git.c:281)\n ==2380== by 0x405A35: handle_internal_command (git.c:443)\n ==2380== by 0x405C01: main (git.c:532)\n\nbut the line in question is:\n\n if (deepest_delta < delta_obj->delta_depth)\n\nAnd in the debugger, both of those variables appear to have sane values\n(nor should either impacted by the patch you bisected to). On top of\nthat, running with pack.threads=1 produces the same error. So I think it\nmay be a false positive from valgrind, and unrelated to your issue.\n\nOther than that, it seems to run fine for me.\n\n-Peff\n"},{"id":"211456","messageId":"CACsJy8D9zwwij9DDrug_tvp2_zrXG7RGcZBbKzpHu1T5iQdxZg@mail.gmail.com","threadId":"33193","inReplyTo":"20130316114118.GA1940@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-16T12:38:40Z","receivedAt":"2013-03-16T12:38:40Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Sat, Mar 16, 2013 at 6:41 PM, Jeff King wrote:\n> On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:\n>\n>> We have uncovered a regression in this commit:\n>>\n>> b8a2486f1524947f232f657e9f2ebf44e3e7a243\n\nWhat version did you test? We used to have problems with multithreaded\nindex-pack on cywgin because its pread implementation is not\nthread-safe, see c0f8654 (index-pack: Disable threading on cygwin -\n2012-06-26). Not sure if we fall into the same path on Mac, or this is\nsomething else..\n\n>>\n>> The symptom is that 'git fetch' dies with:\n>>\n>> error: index-pack died of signal 10\n>> fatal: index-pack failed\n\nI guess it won't help much, but what if you enable coredump and get a\nstack trace from it?\n\n>>\n>> I have only been able to reproduce it on a Mac thus far; will try\n>> ubuntu next. We can make it go away by running:\n>>\n>> git config pack.threads 1\n-- \nDuy\n"},{"id":"211642","messageId":"87fvzrajmr.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130316114118.GA1940@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T08:17:32Z","receivedAt":"2013-03-19T08:17:32Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Fri, Mar 15, 2013 at 03:42:40PM -0700, Stefan Zager wrote:\n>\n>> We have uncovered a regression in this commit:\n>> \n>> b8a2486f1524947f232f657e9f2ebf44e3e7a243\n>> \n>> The symptom is that 'git fetch' dies with:\n>> \n>> error: index-pack died of signal 10\n>> fatal: index-pack failed\n>> \n>> I have only been able to reproduce it on a Mac thus far; will try\n>> ubuntu next. We can make it go away by running:\n>> \n>> git config pack.threads 1\n>\n> I couldn't reproduce the problem on Linux with the instructions you\n> gave. I did try running it under valgrind and it produced:\n>\n> ==2380== Conditional jump or move depends on uninitialised value(s)\n> ==2380== at 0x441631: resolve_delta (index-pack.c:837)\n> ==2380== by 0x4419D6: find_unresolved_deltas_1 (index-pack.c:898)\n> ==2380== by 0x441A45: find_unresolved_deltas (index-pack.c:914)\n> ==2380== by 0x4427CA: fix_unresolved_deltas (index-pack.c:1232)\n> ==2380== by 0x4421F5: conclude_pack (index-pack.c:1111)\n> ==2380== by 0x443A5C: cmd_index_pack (index-pack.c:1604)\n> ==2380== by 0x4058A2: run_builtin (git.c:281)\n> ==2380== by 0x405A35: handle_internal_command (git.c:443)\n> ==2380== by 0x405C01: main (git.c:532)\n>\n> but the line in question is:\n>\n> if (deepest_delta < delta_obj->delta_depth)\n>\n> And in the debugger, both of those variables appear to have sane values\n> (nor should either impacted by the patch you bisected to). On top of\n> that, running with pack.threads=1 produces the same error. So I think it\n> may be a false positive from valgrind, and unrelated to your issue.\n\nI find that somewhat unlikely, for two reasons: memcheck is actually\nquite good at finding uninitialized memory use, it just isn't that good\nat distinguishing if it makes a difference. Most false positives are of\nthe \"loading an entire word and discarding most of it\" kind.\n\nSecond, the thread-debugging valgrind tools (drd and helgrind) also\ncomplain about exactly this line:\n\nDRD says:\n\n ==20987== Thread 4:\n ==20987== Conflicting load by thread 4 at 0x007a70d0 size 4\n ==20987== at 0x43A783: resolve_delta (index-pack.c:837)\n ==20987== by 0x43A94F: find_unresolved_deltas (index-pack.c:898)\n ==20987== by 0x43B0F8: threaded_second_pass (index-pack.c:945)\n ==20987== by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)\n ==20987== by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)\n ==20987== Allocation context: BSS section of /home/thomas/.local/bin/git\n ==20987== Other segment start (thread 2)\n ==20987== at 0x4C30A1F: pthread_mutex_unlock (drd_pthread_intercepts.c:665)\n ==20987== by 0x43B06E: threaded_second_pass (index-pack.c:122)\n ==20987== by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)\n ==20987== by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)\n ==20987== Other segment end (thread 2)\n ==20987== at 0x5436AE3: ??? (in /lib64/libpthread-2.15.so)\n ==20987== by 0x439C76: unpack_data.constprop.8 (index-pack.c:528)\n ==20987== by 0x439EA7: get_base_data (index-pack.c:571)\n ==20987== by 0x43A7B4: resolve_delta (index-pack.c:841)\n ==20987== by 0x43A94F: find_unresolved_deltas (index-pack.c:898)\n ==20987== by 0x43B0F8: threaded_second_pass (index-pack.c:945)\n ==20987== by 0x4C2CF60: vgDrd_thread_wrapper (drd_pthread_intercepts.c:341)\n ==20987== by 0x542FE0D: start_thread (in /lib64/libpthread-2.15.so)\n\n\nhelgrind says:\n\n ==21160== Possible data race during read of size 4 at 0x7A70D0 by thread #3\n ==21160== Locks held: none\n ==21160== at 0x43A783: resolve_delta (index-pack.c:837)\n ==21160== by 0x43A94F: find_unresolved_deltas (index-pack.c:898)\n ==21160== by 0x43B0F8: threaded_second_pass (index-pack.c:945)\n ==21160== by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)\n ==21160== by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)\n ==21160== \n ==21160== This conflicts with a previous write of size 4 by thread #2\n ==21160== Locks held: none\n ==21160== at 0x43A78E: resolve_delta (index-pack.c:838)\n ==21160== by 0x43A94F: find_unresolved_deltas (index-pack.c:898)\n ==21160== by 0x43B0F8: threaded_second_pass (index-pack.c:945)\n ==21160== by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)\n ==21160== by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)\n\n\nYou were apparently just lucky in catching it before it was even\ninitialized.\n\nI can reproduce the above warnings with\n\n valgrind --tool=helgrind --trace-children=yes git index-pack \n\ni.e., it does not seem to depend on the pack (sample size 3, packs\nlooked at were from my git.git).\n\nDuy, what was the reasoning why resolve_delta() does not need to hold\nlocks when it looks when it looks at deepest_delta? My coffee levels\naren't up to this task yet. It certainly seems extremely dubious to me,\nas the code uses the global deepest_delta in threaded sections. You can\nprobably argue that the load/store is atomic on most(?) platforms, but\nyou get no guarantees that deepest_delta at any time in fact holds the\nmaximum value of delta_obj->delta_depth.\n\n\nFurthermore there's another warning shown by helgrind:\n\n ==21160== Possible data race during write of size 4 at 0x7A7060 by thread #2\n ==21160== Locks held: 1, at address 0x7A70E0\n ==21160== at 0x43A840: resolve_delta (index-pack.c:853)\n ==21160== by 0x43A94F: find_unresolved_deltas (index-pack.c:898)\n ==21160== by 0x43B0F8: threaded_second_pass (index-pack.c:945)\n ==21160== by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)\n ==21160== by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)\n ==21160== \n ==21160== This conflicts with a previous read of size 4 by thread #3\n ==21160== Locks held: 1, at address 0x7A7080\n ==21160== at 0x43AFC8: threaded_second_pass (index-pack.c:955)\n ==21160== by 0x4C2D35D: mythread_wrapper (hg_intercepts.c:219)\n ==21160== by 0x5424E0D: start_thread (in /lib64/libpthread-2.15.so)\n\nThat one really seems to be a false positive in the sense that\nthreaded_second_pass() doesn't really care if it gets a bad value for\nnr_resolved_deltas. The only thing that matters is that the counter\nincrement is done with counter_mutex held.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211643","messageId":"20130319093034.GA29997@sigill.intra.peff.net","threadId":"33193","inReplyTo":"87fvzrajmr.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T09:30:34Z","receivedAt":"2013-03-19T09:30:34Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 09:17:32AM +0100, Thomas Rast wrote:\n\n> > but the line in question is:\n> >\n> > if (deepest_delta < delta_obj->delta_depth)\n> >\n> > And in the debugger, both of those variables appear to have sane values\n> > (nor should either impacted by the patch you bisected to). On top of\n> > that, running with pack.threads=1 produces the same error. So I think it\n> > may be a false positive from valgrind, and unrelated to your issue.\n> \n> I find that somewhat unlikely, for two reasons: memcheck is actually\n> quite good at finding uninitialized memory use, it just isn't that good\n> at distinguishing if it makes a difference. Most false positives are of\n> the \"loading an entire word and discarding most of it\" kind.\n\nYes, that has been my experience with valgrind false positives, too. But\nif this is a real problem, it may be different from the OP's issue. It\nseems to trigger for me in v1.7.10, before Duy's threading patches. It\ndoes not seem to be in v1.7.5. I'm bisecting now.\n\n-Peff\n"},{"id":"211646","messageId":"20130319095943.GA6031@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319093034.GA29997@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T09:59:43Z","receivedAt":"2013-03-19T09:59:43Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 05:30:34AM -0400, Jeff King wrote:\n\n> On Tue, Mar 19, 2013 at 09:17:32AM +0100, Thomas Rast wrote:\n> \n> > > but the line in question is:\n> > >\n> > > if (deepest_delta < delta_obj->delta_depth)\n> > >\n> > > And in the debugger, both of those variables appear to have sane values\n> > > (nor should either impacted by the patch you bisected to). On top of\n> > > that, running with pack.threads=1 produces the same error. So I think it\n> > > may be a false positive from valgrind, and unrelated to your issue.\n> > \n> > I find that somewhat unlikely, for two reasons: memcheck is actually\n> > quite good at finding uninitialized memory use, it just isn't that good\n> > at distinguishing if it makes a difference. Most false positives are of\n> > the \"loading an entire word and discarding most of it\" kind.\n> \n> Yes, that has been my experience with valgrind false positives, too. But\n> if this is a real problem, it may be different from the OP's issue. It\n> seems to trigger for me in v1.7.10, before Duy's threading patches. It\n> does not seem to be in v1.7.5. I'm bisecting now.\n\nHmph. It bisects to Junio's d1a0ed1 (index-pack: show histogram when\nemulating \"verify-pack -v\", 2011-06-03), which introduces those lines.\nThe deepest_delta variable is static, so by definition it is always\ninitialized to something. So I guess some objects may not have\ndelta_depth set. Still looking.\n\n-Peff\n"},{"id":"211648","messageId":"20130319100800.GA6341@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319095943.GA6031@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T10:08:00Z","receivedAt":"2013-03-19T10:08:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 05:59:43AM -0400, Jeff King wrote:\n\n> > Yes, that has been my experience with valgrind false positives, too. But\n> > if this is a real problem, it may be different from the OP's issue. It\n> > seems to trigger for me in v1.7.10, before Duy's threading patches. It\n> > does not seem to be in v1.7.5. I'm bisecting now.\n> \n> Hmph. It bisects to Junio's d1a0ed1 (index-pack: show histogram when\n> emulating \"verify-pack -v\", 2011-06-03), which introduces those lines.\n> The deepest_delta variable is static, so by definition it is always\n> initialized to something. So I guess some objects may not have\n> delta_depth set. Still looking.\n\nI'm doubly confused now. The commit in question introduces this:\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex aa3c9c6..ed4c3bb 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -70,6 +70,7 @@ static off_t consumed_bytes;\n static unsigned char input_buffer[4096];\n static unsigned int input_offset, input_len;\n static off_t consumed_bytes;\n+static unsigned deepest_delta;\n static git_SHA_CTX input_ctx;\n static uint32_t input_crc32;\n static int input_fd, output_fd, pack_fd;\n@@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n \n \tdelta_obj->real_type = base->obj->real_type;\n \tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n+\tif (deepest_delta < delta_obj->delta_depth)\n+\t\tdeepest_delta = delta_obj->delta_depth;\n \tdelta_obj->base_object_no = base->obj - objects;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n\nand valgrind reports an uninitialized value in the conditional. But we\ncan see that deepest_delta is static, and therefore always has some\nvalue. And delta_obj->delta_depth is set in the line above. So both\nshould have some known value, unless they are computed from unknown\nvalues. In that case, shouldn't valgrind have previously noticed when we\naccessed those unknown values?\n\n-Peff\n"},{"id":"211649","messageId":"20130319102422.GB6341@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319100800.GA6341@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T10:24:22Z","receivedAt":"2013-03-19T10:24:22Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 06:08:00AM -0400, Jeff King wrote:\n\n> @@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n> \n> \tdelta_obj->real_type = base->obj->real_type;\n> \tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n> +\tif (deepest_delta < delta_obj->delta_depth)\n> +\t\tdeepest_delta = delta_obj->delta_depth;\n> \tdelta_obj->base_object_no = base->obj - objects;\n> \tdelta_data = get_data_from_pack(delta_obj);\n> \tbase_data = get_base_data(base);\n> \n> and valgrind reports an uninitialized value in the conditional. But we\n> can see that deepest_delta is static, and therefore always has some\n> value. And delta_obj->delta_depth is set in the line above. So both\n> should have some known value, unless they are computed from unknown\n> values. In that case, shouldn't valgrind have previously noticed when we\n> accessed those unknown values?\n\nAh, indeed. Putting:\n\n fprintf(stderr, \"%lu\\n\", base->obj->delta_depth);\n\nbefore the conditional reveals that base->obj->delta_depth is\nuninitialized, which is the real problem. I'm sure there is some\nperfectly logical explanation for why valgrind can't detect its use\nduring the assignment, but I'm not sure what it is.\n\nAt any rate, doing this:\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex ed4c3bb..73686af 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -538,6 +538,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tvoid *base_data, *delta_data;\n \n \tdelta_obj->real_type = base->obj->real_type;\n+\tif (!is_delta_type(base->obj->type))\n+\t\tbase->obj->delta_depth = 0;\n \tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n \tif (deepest_delta < delta_obj->delta_depth)\n \t\tdeepest_delta = delta_obj->delta_depth;\n\nmakes the warning go away. It looks like the delta_depth value was\nintroduced in 38a4556 (index-pack: start learning to emulate\n\"verify-pack -v\", 2011-06-03), and it used only for showing the chain\ndepths with --verify-stat. So it is almost certainly not related to\nStefan's original problem, but it does mean we've probably been\ncomputing bogus chain lengths.\n\nThere may be a more reasonable place to set base->obj->delta_depth than\nright here; I'll see if I can cook up a real patch.\n\n-Peff\n"},{"id":"211650","messageId":"87obef8yy7.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130319102422.GB6341@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T10:29:36Z","receivedAt":"2013-03-19T10:29:36Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Tue, Mar 19, 2013 at 06:08:00AM -0400, Jeff King wrote:\n>\n>> @@ -538,6 +539,8 @@ static void resolve_delta(struct object_entry *delta_obj,\n>> \n>> \tdelta_obj->real_type = base->obj->real_type;\n>> \tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n>> +\tif (deepest_delta < delta_obj->delta_depth)\n>> +\t\tdeepest_delta = delta_obj->delta_depth;\n>> \tdelta_obj->base_object_no = base->obj - objects;\n>> \tdelta_data = get_data_from_pack(delta_obj);\n>> \tbase_data = get_base_data(base);\n>> \n>> and valgrind reports an uninitialized value in the conditional. But we\n>> can see that deepest_delta is static, and therefore always has some\n>> value. And delta_obj->delta_depth is set in the line above. So both\n>> should have some known value, unless they are computed from unknown\n>> values. In that case, shouldn't valgrind have previously noticed when we\n>> accessed those unknown values?\n>\n> Ah, indeed. Putting:\n>\n> fprintf(stderr, \"%lu\\n\", base->obj->delta_depth);\n>\n> before the conditional reveals that base->obj->delta_depth is\n> uninitialized, which is the real problem. I'm sure there is some\n> perfectly logical explanation for why valgrind can't detect its use\n> during the assignment, but I'm not sure what it is.\n\nThat's simply because you would get far too much noise. It only reports\nan uninitialized value when it actually gets used in a conditional or\nfor output (syscalls), which is when they matter.\n\nYou can use --track-origins=yes to see where the undefined value came\nfrom, but it's veeeery slow.\n\n> It looks like the delta_depth value was\n> introduced in 38a4556 (index-pack: start learning to emulate\n> \"verify-pack -v\", 2011-06-03), and it used only for showing the chain\n> depths with --verify-stat. So it is almost certainly not related to\n> Stefan's original problem, but it does mean we've probably been\n> computing bogus chain lengths.\n\nNice catch!\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211651","messageId":"20130319103306.GA9490@sigill.intra.peff.net","threadId":"33193","inReplyTo":"87obef8yy7.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T10:33:06Z","receivedAt":"2013-03-19T10:33:06Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 11:29:36AM +0100, Thomas Rast wrote:\n\n> > Ah, indeed. Putting:\n> >\n> > fprintf(stderr, \"%lu\\n\", base->obj->delta_depth);\n> >\n> > before the conditional reveals that base->obj->delta_depth is\n> > uninitialized, which is the real problem. I'm sure there is some\n> > perfectly logical explanation for why valgrind can't detect its use\n> > during the assignment, but I'm not sure what it is.\n> \n> That's simply because you would get far too much noise. It only reports\n> an uninitialized value when it actually gets used in a conditional or\n> for output (syscalls), which is when they matter.\n\nWould it? I would think any computation you start with an undefined\nvalue would be suspect (and you would want to know about it as soon as\npossible, before the tainted value gets output). I was assuming it was a\nperformance issue or something.\n\n> You can use --track-origins=yes to see where the undefined value came\n> from, but it's veeeery slow.\n\nIt's pretty slow either way. :) I do have --track-origins on, but the\norigin is this:\n\n objects = xrealloc(objects,\n (nr_objects + nr_unresolved + 1)\n * sizeof(*objects));\n\nwhich is not very helpful. It's _somewhere_ in the list of objects...:)\n\n-Peff\n"},{"id":"211654","messageId":"871ubb8y6z.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130319103306.GA9490@sigill.intra.peff.net","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-03-19T10:45:56Z","receivedAt":"2013-03-19T10:45:56Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Tue, Mar 19, 2013 at 11:29:36AM +0100, Thomas Rast wrote:\n>\n>> > Ah, indeed. Putting:\n>> >\n>> > fprintf(stderr, \"%lu\\n\", base->obj->delta_depth);\n>> >\n>> > before the conditional reveals that base->obj->delta_depth is\n>> > uninitialized, which is the real problem. I'm sure there is some\n>> > perfectly logical explanation for why valgrind can't detect its use\n>> > during the assignment, but I'm not sure what it is.\n>> \n>> That's simply because you would get far too much noise. It only reports\n>> an uninitialized value when it actually gets used in a conditional or\n>> for output (syscalls), which is when they matter.\n>\n> Would it? I would think any computation you start with an undefined\n> value would be suspect (and you would want to know about it as soon as\n> possible, before the tainted value gets output). I was assuming it was a\n> performance issue or something.\n\nNow consider\n\n // somewhere on the stack\n struct foo {\n char c;\n int i;\n } a, b;\n a.c = a.i = 0;\n\n memcpy(&b, &a, sizeof(struct foo));\n\nThe compiler could legitimately leave the padding between c and i\nuninitialized, and with your proposed \"early\" reporting the memcpy would\ncomplain.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211655","messageId":"20130319104759.GB9490@sigill.intra.peff.net","threadId":"33193","inReplyTo":"871ubb8y6z.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T10:47:59Z","receivedAt":"2013-03-19T10:47:59Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 11:45:56AM +0100, Thomas Rast wrote:\n\n> Now consider\n> \n> // somewhere on the stack\n> struct foo {\n> char c;\n> int i;\n> } a, b;\n> a.c = a.i = 0;\n> \n> memcpy(&b, &a, sizeof(struct foo));\n> \n> The compiler could legitimately leave the padding between c and i\n> uninitialized, and with your proposed \"early\" reporting the memcpy would\n> complain.\n\nAh, good point. And valgrind does not have any way of knowing what is\npadding and what is not, since it sees only the compiled contents.\nProbably llvm's memory checker support could do a better job there.\n\n-Peff\n"},{"id":"211658","messageId":"20130319105852.GA15182@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319102422.GB6341@sigill.intra.peff.net","subject":"[PATCH] index-pack: always zero-initialize object_entry list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T10:58:52Z","receivedAt":"2013-03-19T10:58:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"Commit 38a4556 (index-pack: start learning to emulate\n\"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\nto each \"struct object_entry\". Initially, all object entries\nhave their depth set to 0; in resolve_delta, we then set the\ndepth of each delta to \"base + 1\". Base entries never have\ntheir depth touched, and remain at 0.\n\nTo ensure that all depths start at 0, that commit changed\ncalls to xmalloc the object_entry list into calls to\nxcalloc. However, it forgot that we grow the list with\nxrealloc later. These extra entries are used when we add an\nobject from elsewhere pack to complete a thin pack. If we\nadd a non-delta object, its depth value will just be\nuninitialized heap data.\n\nThis patch fixes it by zero-initializing entries we add to\nthe objects list via the xrealloc.\n\nSigned-off-by: Jeff King \n---\nAnother solution would be to say \"only look at delta_depth\nif the object is a delta\"; we follow that rule already in\nthe output histogram code path, but just do not when\nchecking a delta's base. So it would similarly be a\none-liner. But I think given the switch to xcalloc in the\noriginal patch, the intent was to just always zero each\nobject, as I described above.\n\nThis would be more readable if we had an \"xrecalloc\" or\nsimilar, which realloc'd a pointer and set just the _new_\nspace to zeros. I do not recall ever hearing of such a\nfunction, though. I figured since it is a one-off, it is\nsimpler to just say what we mean with memset here than\ninvent a new allocation function that will leave people\nscratching their heads about its semantics.\n\n builtin/index-pack.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 43d364b..ca62443 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1107,6 +1107,8 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tobjects = xrealloc(objects,\n \t\t\t\t (nr_objects + nr_unresolved + 1)\n \t\t\t\t * sizeof(*objects));\n+\t\tmemset(objects + nr_objects, 0,\n+\t\t (nr_unresolved + 1) * sizeof(*objects));\n \t\tf = sha1fd(output_fd, curr_pack);\n \t\tfix_unresolved_deltas(f, nr_unresolved);\n \t\tsprintf(msg, _(\"completed with %d local objects\"),\n-- \n1.8.2.4.g2ed830d\n"},{"id":"211663","messageId":"CACsJy8DgQZFewPjLSXSkdHHWqhQDqExoVq-pBGpKr1G8w06uvQ@mail.gmail.com","threadId":"33193","inReplyTo":"87fvzrajmr.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-19T12:35:28Z","receivedAt":"2013-03-19T12:35:28Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 19, 2013 at 3:17 PM, Thomas Rast wrote:\n>> but the line in question is:\n>>\n>> if (deepest_delta < delta_obj->delta_depth)\n>>\n>...\n>\n> Duy, what was the reasoning why resolve_delta() does not need to hold\n> locks when it looks when it looks at deepest_delta? My coffee levels\n> aren't up to this task yet. It certainly seems extremely dubious to me,\n> as the code uses the global deepest_delta in threaded sections. You can\n> probably argue that the load/store is atomic on most(?) platforms, but\n> you get no guarantees that deepest_delta at any time in fact holds the\n> maximum value of delta_obj->delta_depth.\n\nNow that I have had dinner (and energy restored), the explanation\nmight be because I missed it. resolve_delta() deals with data in\ndelta_obj and does not share global state, except this one and\nnr_resolved_deltas. The latter is protected. I guess we could protect\nthis one with a mutex. But only do so when \"--verify\" is specified\n\nif (stat) {\n lock();\n if (deepest_delta < delta_obj->delta_depth)\n deepest_delta = delta_obj->delta_depth;\n unlock();\n}\n\nso that we don't need to hold/release lock when index-pack is run.\n-- \nDuy\n"},{"id":"211664","messageId":"1363698075-12452-1-git-send-email-pclouds@gmail.com","threadId":"33193","inReplyTo":"CACsJy8DgQZFewPjLSXSkdHHWqhQDqExoVq-pBGpKr1G8w06uvQ@mail.gmail.com","subject":"[PATCH] index-pack: protect deepest_delta in multithread code","fromName":"Nguyễn Thái Ngọc Duy","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-19T13:01:15Z","receivedAt":"2013-03-19T13:01:15Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"deepest_delta is a global variable but is updated without protection\nin resolve_delta(), a multithreaded function. Add a new mutex for it,\nbut only protect and update when it's actually used (i.e. show_stat is\nnon-zero).\n\nAnother variable that will not be updated is delta_depth in \"struct\nobject_entry\" as it's only useful when show_stat is 1. Putting it in\n\"if (show_stat)\" makes it clearer.\n\nThe local variable \"stat\" is renamed to \"show_stat\" after moving to\nglobal scope because the name \"stat\" conflicts with stat(2) syscall.\n\nSigned-off-by: Nguyễn Thái Ngọc Duy \n---\n builtin/index-pack.c | 30 +++++++++++++++++++++++-------\n 1 file changed, 23 insertions(+), 7 deletions(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 43d364b..9cfd6e7 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -78,6 +78,7 @@ static int nr_threads;\n static int from_stdin;\n static int strict;\n static int verbose;\n+static int show_stat;\n \n static struct progress *progress;\n \n@@ -108,6 +109,10 @@ static pthread_mutex_t work_mutex;\n #define work_lock()\t\tlock_mutex(&work_mutex)\n #define work_unlock()\t\tunlock_mutex(&work_mutex)\n \n+static pthread_mutex_t deepest_delta_mutex;\n+#define deepest_delta_lock()\tlock_mutex(&deepest_delta_mutex)\n+#define deepest_delta_unlock()\tunlock_mutex(&deepest_delta_mutex)\n+\n static pthread_key_t key;\n \n static inline void lock_mutex(pthread_mutex_t *mutex)\n@@ -130,6 +135,8 @@ static void init_thread(void)\n \tinit_recursive_mutex(&read_mutex);\n \tpthread_mutex_init(&counter_mutex, NULL);\n \tpthread_mutex_init(&work_mutex, NULL);\n+\tif (show_stat)\n+\t\tpthread_mutex_init(&deepest_delta_mutex, NULL);\n \tpthread_key_create(&key, NULL);\n \tthread_data = xcalloc(nr_threads, sizeof(*thread_data));\n \tthreads_active = 1;\n@@ -143,6 +150,8 @@ static void cleanup_thread(void)\n \tpthread_mutex_destroy(&read_mutex);\n \tpthread_mutex_destroy(&counter_mutex);\n \tpthread_mutex_destroy(&work_mutex);\n+\tif (show_stat)\n+\t\tpthread_mutex_destroy(&deepest_delta_mutex);\n \tpthread_key_delete(key);\n \tfree(thread_data);\n }\n@@ -158,6 +167,9 @@ static void cleanup_thread(void)\n #define work_lock()\n #define work_unlock()\n \n+#define deepest_delta_lock()\n+#define deepest_delta_unlock()\n+\n #endif\n \n \n@@ -833,9 +845,13 @@ static void resolve_delta(struct object_entry *delta_obj,\n \tvoid *base_data, *delta_data;\n \n \tdelta_obj->real_type = base->obj->real_type;\n-\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n-\tif (deepest_delta < delta_obj->delta_depth)\n-\t\tdeepest_delta = delta_obj->delta_depth;\n+\tif (show_stat) {\n+\t\tdelta_obj->delta_depth = base->obj->delta_depth + 1;\n+\t\tdeepest_delta_lock();\n+\t\tif (deepest_delta < delta_obj->delta_depth)\n+\t\t\tdeepest_delta = delta_obj->delta_depth;\n+\t\tdeepest_delta_unlock();\n+\t}\n \tdelta_obj->base_object_no = base->obj - objects;\n \tdelta_data = get_data_from_pack(delta_obj);\n \tbase_data = get_base_data(base);\n@@ -1462,7 +1478,7 @@ static void show_pack_info(int stat_only)\n \n int cmd_index_pack(int argc, const char **argv, const char *prefix)\n {\n-\tint i, fix_thin_pack = 0, verify = 0, stat_only = 0, stat = 0;\n+\tint i, fix_thin_pack = 0, verify = 0, stat_only = 0;\n \tconst char *curr_pack, *curr_index;\n \tconst char *index_name = NULL, *pack_name = NULL;\n \tconst char *keep_name = NULL, *keep_msg = NULL;\n@@ -1495,10 +1511,10 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \t\t\t\tverify = 1;\n \t\t\t} else if (!strcmp(arg, \"--verify-stat\")) {\n \t\t\t\tverify = 1;\n-\t\t\t\tstat = 1;\n+\t\t\t\tshow_stat = 1;\n \t\t\t} else if (!strcmp(arg, \"--verify-stat-only\")) {\n \t\t\t\tverify = 1;\n-\t\t\t\tstat = 1;\n+\t\t\t\tshow_stat = 1;\n \t\t\t\tstat_only = 1;\n \t\t\t} else if (!strcmp(arg, \"--keep\")) {\n \t\t\t\tkeep_msg = \"\";\n@@ -1606,7 +1622,7 @@ int cmd_index_pack(int argc, const char **argv, const char *prefix)\n \tif (strict)\n \t\tcheck_objects();\n \n-\tif (stat)\n+\tif (show_stat)\n \t\tshow_pack_info(stat_only);\n \n \tidx_objects = xmalloc((nr_objects) * sizeof(struct pack_idx_entry *));\n-- \n1.8.2.83.gc99314b\n"},{"id":"211666","messageId":"20130319132529.GA6646@sigill.intra.peff.net","threadId":"33193","inReplyTo":"1363698075-12452-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] index-pack: protect deepest_delta in multithread code","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T13:25:29Z","receivedAt":"2013-03-19T13:25:29Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 08:01:15PM +0700, Nguyen Thai Ngoc Duy wrote:\n\n> deepest_delta is a global variable but is updated without protection\n> in resolve_delta(), a multithreaded function. Add a new mutex for it,\n> but only protect and update when it's actually used (i.e. show_stat is\n> non-zero).\n\nThis makes sense to me.\n\n> Another variable that will not be updated is delta_depth in \"struct\n> object_entry\" as it's only useful when show_stat is 1. Putting it in\n> \"if (show_stat)\" makes it clearer.\n\nHaving just read through this code for the first time, I agree that\nhaving the \"if (show_stat)\" would have made it a lot more clear under\nwhat conditions and for what purpose the delta_depth flag was being\nused.\n\n> builtin/index-pack.c | 30 +++++++++++++++++++++++-------\n> 1 file changed, 23 insertions(+), 7 deletions(-)\n\nPatch looks good to me. Thanks.\n\n-Peff\n"},{"id":"211668","messageId":"87d2uv7b31.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"1363698075-12452-1-git-send-email-pclouds@gmail.com","subject":"Re: [PATCH] index-pack: protect deepest_delta in multithread code","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T13:50:26Z","receivedAt":"2013-03-19T13:50:26Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Nguyễn Thái Ngọc Duy writes:\n\n> deepest_delta is a global variable but is updated without protection\n> in resolve_delta(), a multithreaded function. Add a new mutex for it,\n> but only protect and update when it's actually used (i.e. show_stat is\n> non-zero).\n>\n> Another variable that will not be updated is delta_depth in \"struct\n> object_entry\" as it's only useful when show_stat is 1. Putting it in\n> \"if (show_stat)\" makes it clearer.\n>\n> The local variable \"stat\" is renamed to \"show_stat\" after moving to\n> global scope because the name \"stat\" conflicts with stat(2) syscall.\n\nLooks good to me, too. However, I think it would still be less magical\nif we had the below too. It also silences helgrind.\n\n-- >8 --\nSubject: [PATCH] index-pack: guard nr_resolved_deltas reads by lock\n\nThe threaded parts of index-pack increment the number of resolved\ndeltas in nr_resolved_deltas guarded by counter_mutex. However, the\nper-thread outer loop accessed nr_resolved_deltas without any locks.\n\nThis is not wrong as such, since it doesn't matter all that much\nwhether we get an outdated value. However, unless someone proves that\nthis one lock makes all the performance difference, it would be much\ncleaner to guard _all_ accesses to the variable with the lock.\n\nSigned-off-by: Thomas Rast \n---\n builtin/index-pack.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex b3fee45..6be99e2 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -968,7 +968,9 @@ static void *threaded_second_pass(void *data)\n \tfor (;;) {\n \t\tint i;\n \t\twork_lock();\n+\t\tcounter_lock();\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\tcounter_unlock();\n \t\twhile (nr_dispatched < nr_objects &&\n \t\t is_delta_type(objects[nr_dispatched].type))\n \t\t\tnr_dispatched++;\n-- \n1.8.2.487.g725f6bb\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211669","messageId":"CACsJy8C0AYvAEm6fJFv+JLWpg3HuFG0erKXnq3NxpkYAy=qb_w@mail.gmail.com","threadId":"33193","inReplyTo":"87d2uv7b31.fsf@pctrast.inf.ethz.ch","subject":"Re: [PATCH] index-pack: protect deepest_delta in multithread code","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-19T14:07:56Z","receivedAt":"2013-03-19T14:07:56Z","isPatch":true,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 19, 2013 at 8:50 PM, Thomas Rast wrote:\n> -- >8 --\n> Subject: [PATCH] index-pack: guard nr_resolved_deltas reads by lock\n>\n> The threaded parts of index-pack increment the number of resolved\n> deltas in nr_resolved_deltas guarded by counter_mutex. However, the\n> per-thread outer loop accessed nr_resolved_deltas without any locks.\n>\n> This is not wrong as such, since it doesn't matter all that much\n> whether we get an outdated value. However, unless someone proves that\n> this one lock makes all the performance difference, it would be much\n> cleaner to guard _all_ accesses to the variable with the lock.\n>\n> Signed-off-by: Thomas Rast \n> ---\n> builtin/index-pack.c | 2 ++\n> 1 file changed, 2 insertions(+)\n>\n> diff --git a/builtin/index-pack.c b/builtin/index-pack.c\n> index b3fee45..6be99e2 100644\n> --- a/builtin/index-pack.c\n> +++ b/builtin/index-pack.c\n> @@ -968,7 +968,9 @@ static void *threaded_second_pass(void *data)\n> for (;;) {\n> int i;\n> work_lock();\n> + counter_lock();\n> display_progress(progress, nr_resolved_deltas);\n> + counter_unlock();\n> while (nr_dispatched < nr_objects &&\n> is_delta_type(objects[nr_dispatched].type))\n> nr_dispatched++;\n\nI'm pretty sure futex will make this cheap. The only thing I don't\nlike here is the double locking (work_lock then counter_lock) is an\ninvitation for potential deadlocks (not now, but who now what can\nchange later). I think you could move work_lock(); down after\ncounter_unlock() so we hold one lock at a time.\n-- \nDuy\n"},{"id":"211670","messageId":"8ddf4db38f33034b5ebf504a18948bccf841ab72.1363702423.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"CACsJy8C0AYvAEm6fJFv+JLWpg3HuFG0erKXnq3NxpkYAy=qb_w@mail.gmail.com","subject":"[PATCH v2] index-pack: guard nr_resolved_deltas reads by lock","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T14:16:41Z","receivedAt":"2013-03-19T14:16:41Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The threaded parts of index-pack increment the number of resolved\ndeltas in nr_resolved_deltas guarded by counter_mutex. However, the\nper-thread outer loop accessed nr_resolved_deltas without any locks.\n\nThis is not wrong as such, since it doesn't matter all that much\nwhether we get an outdated value. However, unless someone proves that\nthis one lock makes all the performance difference, it would be much\ncleaner to guard _all_ accesses to the variable with the lock.\n\nThe only such use is display_progress() in the threaded section (all\nothers are in the conclude_pack() callchain outside the threaded\npart). To make it obvious that it cannot deadlock, move it out of\nwork_mutex.\n\nSigned-off-by: Thomas Rast \n---\n\n> The only thing I don't\n> like here is the double locking (work_lock then counter_lock) is an\n> invitation for potential deadlocks (not now, but who now what can\n> change later). I think you could move work_lock(); down after\n> counter_unlock() so we hold one lock at a time.\n\nGood point.\n\n\n builtin/index-pack.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex b3fee45..a481f54 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -967,8 +967,10 @@ static void *threaded_second_pass(void *data)\n \tset_thread_data(data);\n \tfor (;;) {\n \t\tint i;\n-\t\twork_lock();\n+\t\tcounter_lock();\n \t\tdisplay_progress(progress, nr_resolved_deltas);\n+\t\tcounter_unlock();\n+\t\twork_lock();\n \t\twhile (nr_dispatched < nr_objects &&\n \t\t is_delta_type(objects[nr_dispatched].type))\n \t\t\tnr_dispatched++;\n-- \n1.8.2.490.gc3bbe62\n"},{"id":"211676","messageId":"8738vr5rqh.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130319105852.GA15182@sigill.intra.peff.net","subject":"Re: [PATCH] index-pack: always zero-initialize object_entry list","fromName":"Thomas Rast","fromEmail":"trast@inf.ethz.ch","sentAt":"2013-03-19T15:33:42Z","receivedAt":"2013-03-19T15:33:42Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> Commit 38a4556 (index-pack: start learning to emulate\n> \"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\n> to each \"struct object_entry\". Initially, all object entries\n> have their depth set to 0; in resolve_delta, we then set the\n> depth of each delta to \"base + 1\". Base entries never have\n> their depth touched, and remain at 0.\n\nThis patch causes index-pack to fail on the pack that triggered the\nwhole discussion. More in a minute in another side thread, but\nmeanwhile: NAK until we understand what is really going on here.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211677","messageId":"87hak74cse.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130315224240.50AA340839@wince.sfo.corp.google.com","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T15:41:53Z","receivedAt":"2013-03-19T15:41:53Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"szager@google.com (Stefan Zager) writes:\n\n> We have uncovered a regression in this commit:\n>\n> b8a2486f1524947f232f657e9f2ebf44e3e7a243\n>\n> The symptom is that 'git fetch' dies with:\n>\n> error: index-pack died of signal 10\n> fatal: index-pack failed\n\nSo after that fun detour into threading issues, I have actually managed\nto reproduce this problem on OS X even with the three in-flight patches\nalready applied.\n\nI reduced the issue to this file:\n\n http://thomasrast.ch/download/broken-pack\n\non which you can run this command in the repo that Stefan provided:\n\n git index-pack --keep --stdin -v --pack_header=2,50757 real_type == OBJ_OFS_DELTA' failed.\n Aborted\n\nI think the patch is probably still good as it stands, but there's some\nunderlying breakage going on that hides the problem if we don't clear\nthat memory...\n\nI'm still looking, but I wanted to get this -- and in particular the\npack -- out for you to play with ;-)\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211680","messageId":"20130319154353.GA10010@sigill.intra.peff.net","threadId":"33193","inReplyTo":"8738vr5rqh.fsf@pctrast.inf.ethz.ch","subject":"Re: [PATCH] index-pack: always zero-initialize object_entry list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T15:43:53Z","receivedAt":"2013-03-19T15:43:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 04:33:42PM +0100, Thomas Rast wrote:\n\n> Jeff King writes:\n> \n> > Commit 38a4556 (index-pack: start learning to emulate\n> > \"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\n> > to each \"struct object_entry\". Initially, all object entries\n> > have their depth set to 0; in resolve_delta, we then set the\n> > depth of each delta to \"base + 1\". Base entries never have\n> > their depth touched, and remain at 0.\n> \n> This patch causes index-pack to fail on the pack that triggered the\n> whole discussion. More in a minute in another side thread, but\n> meanwhile: NAK until we understand what is really going on here.\n\nOdd; that's what I was testing with, and it worked fine.\n\nLet me double-check that I didn't screw up my tests. I initially did\nsomething more like:\n\n if (is_delta_type(base->obj->type))\n delta_obj->delta_depth = base->obj->delta_depth + 1;\n else\n delta_obj->delta_depth = 1;\n\nand I'm wondering if I screwed up testing the revised version.\n\n-Peff\n"},{"id":"211682","messageId":"87620n4clo.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"87hak74cse.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T15:45:55Z","receivedAt":"2013-03-19T15:45:55Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast writes:\n\n> (gdb) r index-pack --keep --stdin -v --pack_header=2,50757 Starting program: /Users/trast/.local/bin/git index-pack --keep\n> --stdin -v --pack_header=2,50757 Reading symbols for shared libraries +++........................ done\n> Receiving objects: 100% (50757/50757), 24.52 MiB | 13.06 MiB/s, done.\n> Resolving deltas: 25% (10568/42272) \n> Program received signal EXC_BAD_ACCESS, Could not access memory.\n> Reason: KERN_PROTECTION_FAILURE at address: 0x000000014484dfe8\n> [Switching to process 96573 thread 0x10f]\n> 0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0,\n> offset=69638148, left=0x0) at sha1_file.c:866\n> 866 if (!win || !in_window(win, offset)) {\n>\n> This seems to be a SIGBUS triggered by stack overflow, largely based on\n> the observation that\n>\n> (gdb) p &p\n> $6 = (struct packed_git **) 0x144748058\n\nActually, scratch that; the stack depth is the same no matter what\nulimits I put (up to 64MB). Roughly speaking\n\n (gdb) bt 10\n #0 0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0, offset=69638148, left=0x0) at sha1_file.c:866\n #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\n #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\n #3 0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638146, sizep=0x0, rtype=0x0) at sha1_file.c:1727\n #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\n #5 0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638190, sizep=0x0, rtype=0x0) at sha1_file.c:1727\n #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\n #7 0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638237, sizep=0x0, rtype=0x0) at sha1_file.c:1727\n #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\n #9 0x0000000100181c97 in packed_object_info (p=0x100500f30, obj_offset=69638282, sizep=0x0, rtype=0x0) at sha1_file.c:1727\n (More stack frames follow...)\n (gdb) bt -10\n #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\n #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\n #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\n #4091 0x000000010005457f in resolve_delta (delta_obj=0x1011b0900, base=0x144e00000, result=0x144e00040) at index-pack.c:866\n #4092 0x00000001000548b6 in find_unresolved_deltas_1 (base=0x144e00000, prev_base=0x0) at index-pack.c:914\n #4093 0x0000000100054947 in find_unresolved_deltas (base=0x144e00000) at index-pack.c:930\n #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961\n #4095 0x0000000100054ba5 in threaded_second_pass (data=0x100537dd0) at index-pack.c:984\n #4096 0x00007fff8ec8b8bf in _pthread_start ()\n #4097 0x00007fff8ec8eb75 in thread_start ()\n\nThat leaves me stumped as to the cause of that SIGBUS, however.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211683","messageId":"20130319155244.GA16532@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319154353.GA10010@sigill.intra.peff.net","subject":"Re: [PATCH] index-pack: always zero-initialize object_entry list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T15:52:44Z","receivedAt":"2013-03-19T15:52:44Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 11:43:53AM -0400, Jeff King wrote:\n\n> On Tue, Mar 19, 2013 at 04:33:42PM +0100, Thomas Rast wrote:\n> \n> > Jeff King writes:\n> > \n> > > Commit 38a4556 (index-pack: start learning to emulate\n> > > \"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\n> > > to each \"struct object_entry\". Initially, all object entries\n> > > have their depth set to 0; in resolve_delta, we then set the\n> > > depth of each delta to \"base + 1\". Base entries never have\n> > > their depth touched, and remain at 0.\n> > \n> > This patch causes index-pack to fail on the pack that triggered the\n> > whole discussion. More in a minute in another side thread, but\n> > meanwhile: NAK until we understand what is really going on here.\n> \n> Odd; that's what I was testing with, and it worked fine.\n\nAh, interesting. I built the fix on top of d1a0ed1, the first commit\nthat shows the problem. And it works fine there. But when it is\nforward-ported to the current master, it breaks as you saw.\n\nMore bisection fun.\n\n-Peff\n"},{"id":"211684","messageId":"7vsj3rjshx.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"8ddf4db38f33034b5ebf504a18948bccf841ab72.1363702423.git.trast@student.ethz.ch","subject":"Re: [PATCH v2] index-pack: guard nr_resolved_deltas reads by lock","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-19T15:53:30Z","receivedAt":"2013-03-19T15:53:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> The threaded parts of index-pack increment the number of resolved\n> deltas in nr_resolved_deltas guarded by counter_mutex. However, the\n> per-thread outer loop accessed nr_resolved_deltas without any locks.\n>\n> This is not wrong as such, since it doesn't matter all that much\n> whether we get an outdated value. However, unless someone proves that\n> this one lock makes all the performance difference, it would be much\n> cleaner to guard _all_ accesses to the variable with the lock.\n>\n> The only such use is display_progress() in the threaded section (all\n> others are in the conclude_pack() callchain outside the threaded\n> part). To make it obvious that it cannot deadlock, move it out of\n> work_mutex.\n>\n> Signed-off-by: Thomas Rast \n> ---\n>\n>> The only thing I don't\n>> like here is the double locking (work_lock then counter_lock) is an\n>> invitation for potential deadlocks (not now, but who now what can\n>> change later). I think you could move work_lock(); down after\n>> counter_unlock() so we hold one lock at a time.\n>\n> Good point.\n\nThanks guys for fixing my mess with these two patches.\n"},{"id":"211689","messageId":"87obef2wut.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"87620n4clo.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T16:11:22Z","receivedAt":"2013-03-19T16:11:22Z","isPatch":false,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Thomas Rast writes:\n\n> Thomas Rast writes:\n>\n>> (gdb) r index-pack --keep --stdin -v --pack_header=2,50757 > Starting program: /Users/trast/.local/bin/git index-pack --keep\n>> --stdin -v --pack_header=2,50757 > Reading symbols for shared libraries +++........................ done\n>> Receiving objects: 100% (50757/50757), 24.52 MiB | 13.06 MiB/s, done.\n>> Resolving deltas: 25% (10568/42272) \n>> Program received signal EXC_BAD_ACCESS, Could not access memory.\n>> Reason: KERN_PROTECTION_FAILURE at address: 0x000000014484dfe8\n>> [Switching to process 96573 thread 0x10f]\n>> 0x000000010017ee20 in use_pack (p=0x100500f30, w_cursor=0x14484e1a0,\n>> offset=69638148, left=0x0) at sha1_file.c:866\n>> 866 if (!win || !in_window(win, offset)) {\n>>\n>> This seems to be a SIGBUS triggered by stack overflow, largely based on\n>> the observation that\n>>\n>> (gdb) p &p\n>> $6 = (struct packed_git **) 0x144748058\n>\n> Actually, scratch that; the stack depth is the same no matter what\n> ulimits I put (up to 64MB).\n\nActually scratch that again. It *is* a stack overflow, except that this\nis a thread stack, for which the OS X defaults are 512kB apparently, as\nopposed to 2MB on linux.\n\nTo wit:\n\n (gdb) p &p\n $11 = (struct packed_git **) 0x14484e058\n (gdb) bt -5\n #4093 0x0000000100054947 in find_unresolved_deltas (base=0x144e00000) at index-pack.c:930\n #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961\n #4095 0x0000000100054ba5 in threaded_second_pass (data=0x100537dd0) at index-pack.c:984\n #4096 0x00007fff8ec8b8bf in _pthread_start ()\n #4097 0x00007fff8ec8eb75 in thread_start ()\n (gdb) f 4094\n #4094 0x0000000100054a79 in resolve_base (obj=0x1011b08c0) at index-pack.c:961\n 961 find_unresolved_deltas(base_obj);\n (gdb) p &obj\n $12 = (struct object_entry **) 0x1448cdec8\n (gdb) p 0x14484e058-0x1448cdec8\n $13 = -523888\n (gdb) p 512*1024\n $14 = 524288\n\nAnd indeed the following patch fixes it. Sounds like the delta\nunpacking needs a rewrite to support stackless operation. Sigh.\n\ndiff --git i/builtin/index-pack.c w/builtin/index-pack.c\nindex 6be99e2..f73291f 100644\n--- i/builtin/index-pack.c\n+++ w/builtin/index-pack.c\n@@ -1075,13 +1075,17 @@ static void resolve_deltas(void)\n \tnr_dispatched = 0;\n \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\n \t\tinit_thread();\n+\t\tpthread_attr_t attr;\n+\t\tpthread_attr_init(&attr);\n+\t\tpthread_attr_setstacksize(&attr, 2*1024*1024);\n \t\tfor (i = 0; i < nr_threads; i++) {\n-\t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n+\t\t\tint ret = pthread_create(&thread_data[i].thread, &attr,\n \t\t\t\t\t\t threaded_second_pass, thread_data + i);\n \t\t\tif (ret)\n \t\t\t\tdie(_(\"unable to create thread: %s\"),\n \t\t\t\t strerror(ret));\n \t\t}\n+\t\tpthread_attr_destroy(&attr);\n \t\tfor (i = 0; i < nr_threads; i++)\n \t\t\tpthread_join(thread_data[i].thread, NULL);\n \t\tcleanup_thread();\n\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211690","messageId":"20130319161722.GA17445@sigill.intra.peff.net","threadId":"33193","inReplyTo":"20130319155244.GA16532@sigill.intra.peff.net","subject":"[PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-19T16:17:22Z","receivedAt":"2013-03-19T16:17:22Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Mar 19, 2013 at 11:52:44AM -0400, Jeff King wrote:\n\n> > > > Commit 38a4556 (index-pack: start learning to emulate\n> > > > \"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\n> > > > to each \"struct object_entry\". Initially, all object entries\n> > > > have their depth set to 0; in resolve_delta, we then set the\n> > > > depth of each delta to \"base + 1\". Base entries never have\n> > > > their depth touched, and remain at 0.\n> > > \n> > > This patch causes index-pack to fail on the pack that triggered the\n> > > whole discussion. More in a minute in another side thread, but\n> > > meanwhile: NAK until we understand what is really going on here.\n> > \n> > Odd; that's what I was testing with, and it worked fine.\n> \n> Ah, interesting. I built the fix on top of d1a0ed1, the first commit\n> that shows the problem. And it works fine there. But when it is\n> forward-ported to the current master, it breaks as you saw.\n> \n> More bisection fun.\n\nSo after bisecting, I realize that it is indeed broken on top of\nd1a0ed1. I have no idea why I didn't notice that before; I'm guessing it\nwas because I was running it under valgrind and paying attention only to\nvalgrind errors.\n\nAnyway, the problem is simple and stupid. The original object array is\nnot nr_objects item long; it is (nr_objects + 1) long, though I'm not\nclear why (1-indexing?). So my previous patch was zeroing the final\nentry, which was supposed to contain actual data. Oops.\n\nHere's the corrected patch.\n\n-- >8 --\nSubject: [PATCH] index-pack: always zero-initialize object_entry list\n\nCommit 38a4556 (index-pack: start learning to emulate\n\"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\nto each \"struct object_entry\". Initially, all object entries\nhave their depth set to 0; in resolve_delta, we then set the\ndepth of each delta to \"base + 1\". Base entries never have\ntheir depth touched, and remain at 0.\n\nTo ensure that all depths start at 0, that commit changed\ncalls to xmalloc the object_entry list into calls to\nxcalloc. However, it forgot that we grow the list with\nxrealloc later. These extra entries are used when we add an\nobject from elsewhere pack to complete a thin pack. If we\nadd a non-delta object, its depth value will just be\nuninitialized heap data.\n\nThis patch fixes it by zero-initializing entries we add to\nthe objects list via the xrealloc.\n\nSigned-off-by: Jeff King \n---\n builtin/index-pack.c | 2 ++\n 1 file changed, 2 insertions(+)\n\ndiff --git a/builtin/index-pack.c b/builtin/index-pack.c\nindex 43d364b..5860085 100644\n--- a/builtin/index-pack.c\n+++ b/builtin/index-pack.c\n@@ -1107,6 +1107,8 @@ static void conclude_pack(int fix_thin_pack, const char *curr_pack, unsigned cha\n \t\tobjects = xrealloc(objects,\n \t\t\t\t (nr_objects + nr_unresolved + 1)\n \t\t\t\t * sizeof(*objects));\n+\t\tmemset(objects + nr_objects + 1, 0,\n+\t\t nr_unresolved * sizeof(*objects));\n \t\tf = sha1fd(output_fd, curr_pack);\n \t\tfix_unresolved_deltas(f, nr_unresolved);\n \t\tsprintf(msg, _(\"completed with %d local objects\"),\n-- \n1.8.2.22.g4863f63\n"},{"id":"211692","messageId":"87ehfb2w4q.fsf@pctrast.inf.ethz.ch","threadId":"33193","inReplyTo":"20130319161722.GA17445@sigill.intra.peff.net","subject":"Re: [PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T16:27:01Z","receivedAt":"2013-03-19T16:27:01Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Jeff King writes:\n\n> On Tue, Mar 19, 2013 at 11:52:44AM -0400, Jeff King wrote:\n>\n>> > > > Commit 38a4556 (index-pack: start learning to emulate\n>> > > > \"verify-pack -v\", 2011-06-03) added a \"delta_depth\" counter\n>> > > > to each \"struct object_entry\". Initially, all object entries\n>> > > > have their depth set to 0; in resolve_delta, we then set the\n>> > > > depth of each delta to \"base + 1\". Base entries never have\n>> > > > their depth touched, and remain at 0.\n>> > > \n>> > > This patch causes index-pack to fail on the pack that triggered the\n>> > > whole discussion. More in a minute in another side thread, but\n>> > > meanwhile: NAK until we understand what is really going on here.\n>> > \n>> > Odd; that's what I was testing with, and it worked fine.\n>> \n>> Ah, interesting. I built the fix on top of d1a0ed1, the first commit\n>> that shows the problem. And it works fine there. But when it is\n>> forward-ported to the current master, it breaks as you saw.\n>> \n>> More bisection fun.\n>\n> So after bisecting, I realize that it is indeed broken on top of\n> d1a0ed1. I have no idea why I didn't notice that before; I'm guessing it\n> was because I was running it under valgrind and paying attention only to\n> valgrind errors.\n>\n> Anyway, the problem is simple and stupid. The original object array is\n> not nr_objects item long; it is (nr_objects + 1) long, though I'm not\n> clear why (1-indexing?).\n\nIt apparently relates to the use of .idx.offset to compute the \"next\"\noffset, cf. append_obj_to_pack():\n\n\tstruct object_entry *obj = &objects[nr_objects++];\n ...\n\tobj[1].idx.offset = obj[0].idx.offset + n;\n\tobj[1].idx.offset += write_compressed(f, buf, size);\n\nSo you trashed the offset of the first object after all the objects that\nare actually *in* the patch.\n\nAnd with that: ACK.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"211693","messageId":"7vboafjot5.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"87ehfb2w4q.fsf@pctrast.inf.ethz.ch","subject":"Re: [PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-19T17:13:10Z","receivedAt":"2013-03-19T17:13:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> It apparently relates to the use of .idx.offset to compute the \"next\"\n> offset, cf. append_obj_to_pack():\n>\n> \tstruct object_entry *obj = &objects[nr_objects++];\n> ...\n> \tobj[1].idx.offset = obj[0].idx.offset + n;\n> \tobj[1].idx.offset += write_compressed(f, buf, size);\n>\n> So you trashed the offset of the first object after all the objects that\n> are actually *in* the patch.\n>\n> And with that: ACK.\n\nAhh, I also was scratching my head about that +1 thing. After all,\nthe +1 in the argument to xrealloc() was already a clue.\n\nThanks both for digging to the bottom of this one.\n"},{"id":"211696","messageId":"7v1ubbjmq7.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"87obef2wut.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-19T17:58:08Z","receivedAt":"2013-03-19T17:58:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Actually scratch that again. It *is* a stack overflow, except that this\n> is a thread stack, for which the OS X defaults are 512kB apparently, as\n> opposed to 2MB on linux.\n> ...\n> And indeed the following patch fixes it. Sounds like the delta\n> unpacking needs a rewrite to support stackless operation. Sigh.\n\nYikes. Thanks for digging it to the bottom.\n\nI am not sure if I want to carry this patch in its current form,\nthough. As this episode demonstrates, no default is good enough for\neverybody, and I am not sure if a configuration variable is a good\nway to go, either.\n\n>\n> diff --git i/builtin/index-pack.c w/builtin/index-pack.c\n> index 6be99e2..f73291f 100644\n> --- i/builtin/index-pack.c\n> +++ w/builtin/index-pack.c\n> @@ -1075,13 +1075,17 @@ static void resolve_deltas(void)\n> \tnr_dispatched = 0;\n> \tif (nr_threads > 1 || getenv(\"GIT_FORCE_THREADS\")) {\n> \t\tinit_thread();\n> +\t\tpthread_attr_t attr;\n> +\t\tpthread_attr_init(&attr);\n> +\t\tpthread_attr_setstacksize(&attr, 2*1024*1024);\n> \t\tfor (i = 0; i < nr_threads; i++) {\n> -\t\t\tint ret = pthread_create(&thread_data[i].thread, NULL,\n> +\t\t\tint ret = pthread_create(&thread_data[i].thread, &attr,\n> \t\t\t\t\t\t threaded_second_pass, thread_data + i);\n> \t\t\tif (ret)\n> \t\t\t\tdie(_(\"unable to create thread: %s\"),\n> \t\t\t\t strerror(ret));\n> \t\t}\n> +\t\tpthread_attr_destroy(&attr);\n> \t\tfor (i = 0; i < nr_threads; i++)\n> \t\t\tpthread_join(thread_data[i].thread, NULL);\n> \t\tcleanup_thread();\n"},{"id":"211712","messageId":"c5fc1d2040544965ad3cc09e7b82b6013f06b7fa.1363729774.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"7v1ubbjmq7.fsf@alter.siamese.dyndns.org","subject":"[PATCH] sha1_file: remove recursion in packed_object_info","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-19T22:08:13Z","receivedAt":"2013-03-19T22:08:13Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"packed_object_info() and packed_delta_info() were mutually recursive.\nThe former would handle ordinary types and defer deltas to the latter;\nthe latter would use the former to resolve the delta base.\n\nThis arrangement, however, leads to trouble with threaded index-pack\nand long delta chains on platforms where thread stacks are small, as\nhappened on OS X (512kB thread stacks by default) with the chromium\nrepo.\n\nThe task of the two functions is not all that hard to describe without\nany recursion, however. It proceeds in three steps:\n\n- determine the representation type and size, based on the outermost\n object (delta or not)\n\n- follow through the delta chain, if any\n\n- determine the object type from what is found at the end of the delta\n chain\n\nThe only complication stems from the error recovery. If parsing fails\nat any step, we want to mark that object (within the pack) as bad and\ntry getting the corresponding SHA1 from elsewhere. If that also\nfails, we want to repeat this process back up the delta chain until we\nfind a reasonable solution or conclude that there is no way to\nreconstruct the object. (This is conveniently checked by t5303.)\n\nTo achieve that within the pack, we keep track of the entire delta\nchain in a stack. When things go sour, we process that stack from the\ntop, marking entries as bad and attempting to re-resolve by sha1. To\navoid excessive malloc(), the stack starts out with a small\nstack-allocated array. The choice of 64 is based on the default of\npack.depth, which is 50, in the hope that it covers \"most\" delta\nchains without any need for malloc().\n\nIt's much harder to make the actual re-resolving by sha1 nonrecursive,\nso we skip that. If you can't afford *that* recursion, your\ncorruption problems are more serious than your stack size problems.\n\nReported-by: Stefan Zager \nSigned-off-by: Thomas Rast \n---\n\nJunio C Hamano writes:\n\n> Thomas Rast writes:\n> \n> > Actually scratch that again. It *is* a stack overflow, except that this\n> > is a thread stack, for which the OS X defaults are 512kB apparently, as\n> > opposed to 2MB on linux.\n> > ...\n> > And indeed the following patch fixes it. Sounds like the delta\n> > unpacking needs a rewrite to support stackless operation. Sigh.\n> \n> Yikes. Thanks for digging it to the bottom.\n\nSo here's a nonrecursive version. Dijkstra is probably turning over\nin his grave as we speak.\n\nI *think* I actually got it right. It passes tests in any case. ;-)\n\nThe sad part is, after all the effort it still bombs out in the same\nplace because of the very similar recursion in unpack_entry(). I'll\nsave that for another day.\n\n\n sha1_file.c | 132 +++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 81 insertions(+), 51 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 16967d3..54e92a2 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1639,50 +1639,6 @@ static off_t get_delta_base(struct packed_git *p,\n \treturn base_offset;\n }\n \n-/* forward declaration for a mutually recursive function */\n-static int packed_object_info(struct packed_git *p, off_t offset,\n-\t\t\t unsigned long *sizep, int *rtype);\n-\n-static int packed_delta_info(struct packed_git *p,\n-\t\t\t struct pack_window **w_curs,\n-\t\t\t off_t curpos,\n-\t\t\t enum object_type type,\n-\t\t\t off_t obj_offset,\n-\t\t\t unsigned long *sizep)\n-{\n-\toff_t base_offset;\n-\n-\tbase_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);\n-\tif (!base_offset)\n-\t\treturn OBJ_BAD;\n-\ttype = packed_object_info(p, base_offset, NULL, NULL);\n-\tif (type <= OBJ_NONE) {\n-\t\tstruct revindex_entry *revidx;\n-\t\tconst unsigned char *base_sha1;\n-\t\trevidx = find_pack_revindex(p, base_offset);\n-\t\tif (!revidx)\n-\t\t\treturn OBJ_BAD;\n-\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n-\t\tmark_bad_packed_object(p, base_sha1);\n-\t\ttype = sha1_object_info(base_sha1, NULL);\n-\t\tif (type <= OBJ_NONE)\n-\t\t\treturn OBJ_BAD;\n-\t}\n-\n-\t/* We choose to only get the type of the base object and\n-\t * ignore potentially corrupt pack file that expects the delta\n-\t * based on a base with a wrong size. This saves tons of\n-\t * inflate() calls.\n-\t */\n-\tif (sizep) {\n-\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n-\t\tif (*sizep == 0)\n-\t\t\ttype = OBJ_BAD;\n-\t}\n-\n-\treturn type;\n-}\n-\n int unpack_object_header(struct packed_git *p,\n \t\t\t struct pack_window **w_curs,\n \t\t\t off_t *curpos,\n@@ -1709,6 +1665,25 @@ int unpack_object_header(struct packed_git *p,\n \treturn type;\n }\n \n+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)\n+{\n+\tint type;\n+\tstruct revindex_entry *revidx;\n+\tconst unsigned char *sha1;\n+\trevidx = find_pack_revindex(p, obj_offset);\n+\tif (!revidx)\n+\t\treturn OBJ_BAD;\n+\tsha1 = nth_packed_object_sha1(p, revidx->nr);\n+\tmark_bad_packed_object(p, sha1);\n+\ttype = sha1_object_info(sha1, NULL);\n+\tif (type <= OBJ_NONE)\n+\t\treturn OBJ_BAD;\n+\treturn type;\n+}\n+\n+\n+#define POI_STACK_PREALLOC 64\n+\n static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \t\t\t unsigned long *sizep, int *rtype)\n {\n@@ -1716,31 +1691,86 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \tunsigned long size;\n \toff_t curpos = obj_offset;\n \tenum object_type type;\n+\toff_t small_poi_stack[POI_STACK_PREALLOC];\n+\toff_t *poi_stack = small_poi_stack;\n+\tint poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;\n \n \ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\n \tif (rtype)\n \t\t*rtype = type; /* representation type */\n \n+\tif (sizep) {\n+\t\tif (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\t\toff_t tmp_pos = curpos;\n+\t\t\tget_delta_base(p, &w_curs, &tmp_pos, type, obj_offset);\n+\t\t\t*sizep = get_size_from_delta(p, &w_curs, tmp_pos);\n+\t\t\tif (*sizep == 0) {\n+\t\t\t\ttype = OBJ_BAD;\n+\t\t\t\tgoto out;\n+\t\t\t}\n+\t\t} else {\n+\t\t\t*sizep = size;\n+\t\t}\n+\t}\n+\n+\twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\toff_t base_offset;\n+\t\t/* Push the object we're going to leave behind */\n+\t\tif (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {\n+\t\t\tpoi_stack_alloc = alloc_nr(poi_stack_nr);\n+\t\t\tpoi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);\n+\t\t\tmemcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);\n+\t\t} else {\n+\t\t\tALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);\n+\t\t}\n+\t\tpoi_stack[poi_stack_nr++] = obj_offset;\n+\t\t/* If parsing the base offset fails, just unwind */\n+\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n+\t\tif (!base_offset)\n+\t\t\tgoto unwind;\n+\t\tcurpos = obj_offset = base_offset;\n+\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\t\tif (type <= OBJ_NONE) {\n+\t\t\t/* If getting the base itself fails, we first\n+\t\t\t * retry the base, otherwise unwind */\n+\t\t\ttype = retry_bad_packed_offset(p, base_offset);\n+\t\t\tif (type > OBJ_NONE)\n+\t\t\t\tgoto out;\n+\t\t\tgoto unwind;\n+\t\t}\n+\t}\n+\n \tswitch (type) {\n-\tcase OBJ_OFS_DELTA:\n-\tcase OBJ_REF_DELTA:\n-\t\ttype = packed_delta_info(p, &w_curs, curpos,\n-\t\t\t\t\t type, obj_offset, sizep);\n-\t\tbreak;\n+\tcase OBJ_BAD:\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tif (sizep)\n-\t\t\t*sizep = size;\n \t\tbreak;\n \tdefault:\n \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n \t\t type, (uintmax_t)obj_offset, p->pack_name);\n \t\ttype = OBJ_BAD;\n \t}\n+\n+out:\n+\tif (poi_stack != small_poi_stack)\n+\t\tfree(poi_stack);\n \tunuse_pack(&w_curs);\n \treturn type;\n+\n+unwind:\n+\twhile (poi_stack_nr) {\n+\t\tobj_offset = poi_stack[poi_stack_nr--];\n+\t\ttype = retry_bad_packed_offset(p, obj_offset);\n+\t\tif (type > OBJ_NONE)\n+\t\t\tgoto out;\n+\t}\n+\tif (poi_stack != small_poi_stack)\n+\t\tfree(poi_stack);\n+\tunuse_pack(&w_curs);\n+\treturn OBJ_BAD;\n }\n \n static void *unpack_compressed_entry(struct packed_git *p,\n-- \n1.8.2.490.g25051b0\n"},{"id":"211721","messageId":"CACsJy8ARYEtU4_6zJQXGDyE4FunbV3Gk0BocNW3cZtV-uSVFOg@mail.gmail.com","threadId":"33193","inReplyTo":"87obef2wut.fsf@pctrast.inf.ethz.ch","subject":"Re: regression in multi-threaded git-pack-index","fromName":"Duy Nguyen","fromEmail":"pclouds@gmail.com","sentAt":"2013-03-20T01:17:18Z","receivedAt":"2013-03-20T01:17:18Z","isPatch":false,"sender":{"key":"pclouds@gmail.com","avatar":"https://avatars.githubusercontent.com/u/720?v=4"},"body":"On Tue, Mar 19, 2013 at 11:11 PM, Thomas Rast wrote:\n> Actually scratch that again. It *is* a stack overflow, except that this\n> is a thread stack, for which the OS X defaults are 512kB apparently, as\n> opposed to 2MB on linux.\n\nThanks. I was scratching my head last night wondering if there was\nunprotected access to the object database and probably would have\ncontinued this morning.\n-- \nDuy\n"},{"id":"211762","messageId":"7vtxo6f27l.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"c5fc1d2040544965ad3cc09e7b82b6013f06b7fa.1363729774.git.trast@student.ethz.ch","subject":"Re: [PATCH] sha1_file: remove recursion in packed_object_info","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-20T16:47:10Z","receivedAt":"2013-03-20T16:47:10Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> So here's a nonrecursive version. Dijkstra is probably turning over\n> in his grave as we speak.\n>\n> I *think* I actually got it right.\n\nYou seem to have lost the \"if we cannot get delta base, this object\nis BAD\" check where you measure the size of a deltified object,\nwhich would correspond to this check:\n\n> -static int packed_delta_info(struct packed_git *p,\n> -\t\t\t struct pack_window **w_curs,\n> -\t\t\t off_t curpos,\n> -\t\t\t enum object_type type,\n> -\t\t\t off_t obj_offset,\n> -\t\t\t unsigned long *sizep)\n> -{\n> -\toff_t base_offset;\n> -\n> -\tbase_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);\n> -\tif (!base_offset)\n> -\t\treturn OBJ_BAD;\n\nThe following comment is also lost but...\n\n> -\t/* We choose to only get the type of the base object and\n> -\t * ignore potentially corrupt pack file that expects the delta\n> -\t * based on a base with a wrong size. This saves tons of\n> -\t * inflate() calls.\n> -\t */\n> -\tif (sizep) {\n> -\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n> -\t\tif (*sizep == 0)\n> -\t\t\ttype = OBJ_BAD;\n\n... is this check correct? There is an equivalent check at the\nbeginning of the new packed_object_info() to error out a deltified\nresult. Why is an object whose size is 0 bad?\n\nThis comes from 3d77d8774fc1 (make packed_object_info() resilient to\npack corruptions, 2008-10-29), and I tend to trust Nico more than I\ndo myself. I must be missing something obvious, but it appears to me\nthat the only thing that keeps us from triggering a false positive\nis that we do not even attempt to deltify anything smaller than 50\nbytes, and create_delta() refuses to create a delta to produce an\nempty data. But a hand-crafted packfile could certainly record such\na delta, no?\n\n> The task of the two functions is not all that hard to describe without\n> any recursion, however. It proceeds in three steps:\n>\n> - determine the representation type and size, based on the outermost\n> object (delta or not)\n>\n> - follow through the delta chain, if any\n>\n> - determine the object type from what is found at the end of the delta\n> chain\n\nThe stack/recursion is used _only_ for error recovery, no? If we do\nnot care about retrying with a different copy of an object we find\nin the delta chain, we can just update obj_offset with base_offset\nand keep digging. It almost makes me wonder if a logical follow-up\nto this patch may be to do so, and rewrite the error recovery\ncodepath to just mark the bad copy and jump back to the very top,\nretrying everything from scratch. Eventually we would run out\nbad copies of the problematic object and would report an error, or\nfind a good copy and return the type.\n"},{"id":"211806","messageId":"CAPig+cQobu8GoqSNjVw8498e8D3vEJKU+UVUqkYbwypLyPTNhQ@mail.gmail.com","threadId":"33193","inReplyTo":"20130319161722.GA17445@sigill.intra.peff.net","subject":"Re: [PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-20T19:12:07Z","receivedAt":"2013-03-20T19:12:07Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Tue, Mar 19, 2013 at 12:17 PM, Jeff King wrote:\n> To ensure that all depths start at 0, that commit changed\n> calls to xmalloc the object_entry list into calls to\n> xcalloc. However, it forgot that we grow the list with\n> xrealloc later. These extra entries are used when we add an\n> object from elsewhere pack to complete a thin pack. If we\n\ns/elsewhere pack/pack/\n\n> add a non-delta object, its depth value will just be\n> uninitialized heap data.\n"},{"id":"211807","messageId":"20130320191327.GA31383@sigill.intra.peff.net","threadId":"33193","inReplyTo":"CAPig+cQobu8GoqSNjVw8498e8D3vEJKU+UVUqkYbwypLyPTNhQ@mail.gmail.com","subject":"Re: [PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-03-20T19:13:27Z","receivedAt":"2013-03-20T19:13:27Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 20, 2013 at 03:12:07PM -0400, Eric Sunshine wrote:\n\n> On Tue, Mar 19, 2013 at 12:17 PM, Jeff King wrote:\n> > To ensure that all depths start at 0, that commit changed\n> > calls to xmalloc the object_entry list into calls to\n> > xcalloc. However, it forgot that we grow the list with\n> > xrealloc later. These extra entries are used when we add an\n> > object from elsewhere pack to complete a thin pack. If we\n> \n> s/elsewhere pack/pack/\n\nI think it is supposed to be s/elsewhere pack/elsewhere/.\n\nThanks for noticing.\n\n-Peff\n"},{"id":"211808","messageId":"CAPig+cSqnXeqfYnAm1Nct6UF4DcpP2hxzCUeTytrNENvpuBk2A@mail.gmail.com","threadId":"33193","inReplyTo":"20130320191327.GA31383@sigill.intra.peff.net","subject":"Re: [PATCH v2] index-pack: always zero-initialize object_entry list","fromName":"Eric Sunshine","fromEmail":"sunshine@sunshineco.com","sentAt":"2013-03-20T19:14:22Z","receivedAt":"2013-03-20T19:14:22Z","isPatch":true,"sender":{"key":"sunshine@sunshineco.com","avatar":"https://avatars.githubusercontent.com/u/163641?v=4"},"body":"On Wed, Mar 20, 2013 at 3:13 PM, Jeff King wrote:\n> On Wed, Mar 20, 2013 at 03:12:07PM -0400, Eric Sunshine wrote:\n>\n>> On Tue, Mar 19, 2013 at 12:17 PM, Jeff King wrote:\n>> > To ensure that all depths start at 0, that commit changed\n>> > calls to xmalloc the object_entry list into calls to\n>> > xcalloc. However, it forgot that we grow the list with\n>> > xrealloc later. These extra entries are used when we add an\n>> > object from elsewhere pack to complete a thin pack. If we\n>>\n>> s/elsewhere pack/pack/\n>\n> I think it is supposed to be s/elsewhere pack/elsewhere/.\n\nSorry, yes.\n\n-- ES\n"},{"id":"212155","messageId":"87620faky3.fsf@linux-k42r.v.cablecom.net","threadId":"33193","inReplyTo":"7vtxo6f27l.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] sha1_file: remove recursion in packed_object_info","fromName":"thomas","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-25T09:27:16Z","receivedAt":"2013-03-25T09:27:16Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> So here's a nonrecursive version. Dijkstra is probably turning over\n>> in his grave as we speak.\n>>\n>> I *think* I actually got it right.\n>\n> You seem to have lost the \"if we cannot get delta base, this object\n> is BAD\" check where you measure the size of a deltified object,\n> which would correspond to this check:\n>\n>> -static int packed_delta_info(struct packed_git *p,\n>> -\t\t\t struct pack_window **w_curs,\n>> -\t\t\t off_t curpos,\n>> -\t\t\t enum object_type type,\n>> -\t\t\t off_t obj_offset,\n>> -\t\t\t unsigned long *sizep)\n>> -{\n>> -\toff_t base_offset;\n>> -\n>> -\tbase_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);\n>> -\tif (!base_offset)\n>> -\t\treturn OBJ_BAD;\n\nTrue, I'll think about this.\n\n> The following comment is also lost but...\n>\n>> -\t/* We choose to only get the type of the base object and\n>> -\t * ignore potentially corrupt pack file that expects the delta\n>> -\t * based on a base with a wrong size. This saves tons of\n>> -\t * inflate() calls.\n>> -\t */\n>> -\tif (sizep) {\n>> -\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n>> -\t\tif (*sizep == 0)\n>> -\t\t\ttype = OBJ_BAD;\n>\n> ... is this check correct? There is an equivalent check at the\n> beginning of the new packed_object_info() to error out a deltified\n> result. Why is an object whose size is 0 bad?\n\nCc'ing Nicolas, but I think there are several reasons:\n\nIf it's a delta, then according to docs[1] it starts with the SHA1 of\nthe base object, plus the deflated data. So it is at least 20 bytes.\n\nIf it's not a delta, then it must start with ' \\0', which\neven after compression cannot possibly be 0 bytes.\n\nEither way, get_size_from_delta() also uses 0 as the error return.\n\n> The stack/recursion is used _only_ for error recovery, no? If we do\n> not care about retrying with a different copy of an object we find\n> in the delta chain, we can just update obj_offset with base_offset\n> and keep digging. It almost makes me wonder if a logical follow-up\n> to this patch may be to do so, and rewrite the error recovery\n> codepath to just mark the bad copy and jump back to the very top,\n> retrying everything from scratch.\n\nI totally agree. I'll try this again -- my last attempt just didn't\nwork out...\n\n\n\n[1] Documentation/technical/pack-format.txt\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"},{"id":"212187","messageId":"cover.1364234154.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"87620faky3.fsf@linux-k42r.v.cablecom.net","subject":"[PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-25T18:07:38Z","receivedAt":"2013-03-25T18:07:38Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"This is a fixed version of the initial patch, plus a two-patch\nimplementation of a recursion-free unpack_entry. (I narrowly resisted\nusing \"unrecursify\" to describe it.)\n\nI wrote:\n\n> Junio C Hamano writes:\n>\n>> The stack/recursion is used _only_ for error recovery, no? If we do\n>> not care about retrying with a different copy of an object we find\n>> in the delta chain, we can just update obj_offset with base_offset\n>> and keep digging. It almost makes me wonder if a logical follow-up\n>> to this patch may be to do so, and rewrite the error recovery\n>> codepath to just mark the bad copy and jump back to the very top,\n>> retrying everything from scratch.\n>\n> I totally agree. I'll try this again -- my last attempt just didn't\n> work out...\n\nNow I remember why it wasn't possible: we would have to go through the\nblacklists at every iteration, whereas now we only check them in the\ninitial lookups.\n\nI'm not sure it makes that much sense. If we need to shave off some\nspeed in these functions, I would rather:\n\n- write packed_object_info so that it runs with constant space, and\n restarts another implementation _with_ the recovery stack if it hits\n a problem;\n\n- write unpack_entry so that it reuses the stack. It can't do so by\n using a static buffer because it needs to be reentrant in the error\n case.\n\n\nThomas Rast (3):\n sha1_file: remove recursion in packed_object_info\n Refactor parts of in_delta_base_cache/cache_or_unpack_entry\n sha1_file: remove recursion in unpack_entry\n\n sha1_file.c | 411 +++++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 266 insertions(+), 145 deletions(-)\n\n-- \n1.8.2.266.g8176668\n"},{"id":"212188","messageId":"0cb230552c02a453180a5ecc6479173619865b73.1364234154.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"cover.1364234154.git.trast@student.ethz.ch","subject":"[PATCH v2 1/3] sha1_file: remove recursion in packed_object_info","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-25T18:07:39Z","receivedAt":"2013-03-25T18:07:39Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"packed_object_info() and packed_delta_info() were mutually recursive.\nThe former would handle ordinary types and defer deltas to the latter;\nthe latter would use the former to resolve the delta base.\n\nThis arrangement, however, leads to trouble with threaded index-pack\nand long delta chains on platforms where thread stacks are small, as\nhappened on OS X (512kB thread stacks by default) with the chromium\nrepo.\n\nThe task of the two functions is not all that hard to describe without\nany recursion, however. It proceeds in three steps:\n\n- determine the representation type and size, based on the outermost\n object (delta or not)\n\n- follow through the delta chain, if any\n\n- determine the object type from what is found at the end of the delta\n chain\n\nThe only complication stems from the error recovery. If parsing fails\nat any step, we want to mark that object (within the pack) as bad and\ntry getting the corresponding SHA1 from elsewhere. If that also\nfails, we want to repeat this process back up the delta chain until we\nfind a reasonable solution or conclude that there is no way to\nreconstruct the object. (This is conveniently checked by t5303.)\n\nTo achieve that within the pack, we keep track of the entire delta\nchain in a stack. When things go sour, we process that stack from the\ntop, marking entries as bad and attempting to re-resolve by sha1. To\navoid excessive malloc(), the stack starts out with a small\nstack-allocated array. The choice of 64 is based on the default of\npack.depth, which is 50, in the hope that it covers \"most\" delta\nchains without any need for malloc().\n\nIt's much harder to make the actual re-resolving by sha1 nonrecursive,\nso we skip that. If you can't afford *that* recursion, your\ncorruption problems are more serious than your stack size problems.\n\nReported-by: Stefan Zager \nSigned-off-by: Thomas Rast \n---\n sha1_file.c | 135 +++++++++++++++++++++++++++++++++++++-----------------------\n 1 file changed, 84 insertions(+), 51 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 40b2329..71877a7 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1560,50 +1560,6 @@ static off_t get_delta_base(struct packed_git *p,\n \treturn base_offset;\n }\n \n-/* forward declaration for a mutually recursive function */\n-static int packed_object_info(struct packed_git *p, off_t offset,\n-\t\t\t unsigned long *sizep, int *rtype);\n-\n-static int packed_delta_info(struct packed_git *p,\n-\t\t\t struct pack_window **w_curs,\n-\t\t\t off_t curpos,\n-\t\t\t enum object_type type,\n-\t\t\t off_t obj_offset,\n-\t\t\t unsigned long *sizep)\n-{\n-\toff_t base_offset;\n-\n-\tbase_offset = get_delta_base(p, w_curs, &curpos, type, obj_offset);\n-\tif (!base_offset)\n-\t\treturn OBJ_BAD;\n-\ttype = packed_object_info(p, base_offset, NULL, NULL);\n-\tif (type <= OBJ_NONE) {\n-\t\tstruct revindex_entry *revidx;\n-\t\tconst unsigned char *base_sha1;\n-\t\trevidx = find_pack_revindex(p, base_offset);\n-\t\tif (!revidx)\n-\t\t\treturn OBJ_BAD;\n-\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n-\t\tmark_bad_packed_object(p, base_sha1);\n-\t\ttype = sha1_object_info(base_sha1, NULL);\n-\t\tif (type <= OBJ_NONE)\n-\t\t\treturn OBJ_BAD;\n-\t}\n-\n-\t/* We choose to only get the type of the base object and\n-\t * ignore potentially corrupt pack file that expects the delta\n-\t * based on a base with a wrong size. This saves tons of\n-\t * inflate() calls.\n-\t */\n-\tif (sizep) {\n-\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n-\t\tif (*sizep == 0)\n-\t\t\ttype = OBJ_BAD;\n-\t}\n-\n-\treturn type;\n-}\n-\n int unpack_object_header(struct packed_git *p,\n \t\t\t struct pack_window **w_curs,\n \t\t\t off_t *curpos,\n@@ -1630,6 +1586,25 @@ int unpack_object_header(struct packed_git *p,\n \treturn type;\n }\n \n+static int retry_bad_packed_offset(struct packed_git *p, off_t obj_offset)\n+{\n+\tint type;\n+\tstruct revindex_entry *revidx;\n+\tconst unsigned char *sha1;\n+\trevidx = find_pack_revindex(p, obj_offset);\n+\tif (!revidx)\n+\t\treturn OBJ_BAD;\n+\tsha1 = nth_packed_object_sha1(p, revidx->nr);\n+\tmark_bad_packed_object(p, sha1);\n+\ttype = sha1_object_info(sha1, NULL);\n+\tif (type <= OBJ_NONE)\n+\t\treturn OBJ_BAD;\n+\treturn type;\n+}\n+\n+\n+#define POI_STACK_PREALLOC 64\n+\n static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \t\t\t unsigned long *sizep, int *rtype)\n {\n@@ -1637,31 +1612,89 @@ static int packed_object_info(struct packed_git *p, off_t obj_offset,\n \tunsigned long size;\n \toff_t curpos = obj_offset;\n \tenum object_type type;\n+\toff_t small_poi_stack[POI_STACK_PREALLOC];\n+\toff_t *poi_stack = small_poi_stack;\n+\tint poi_stack_nr = 0, poi_stack_alloc = POI_STACK_PREALLOC;\n \n \ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\n \tif (rtype)\n \t\t*rtype = type; /* representation type */\n \n+\tif (sizep) {\n+\t\tif (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\t\toff_t tmp_pos = curpos;\n+\t\t\toff_t base_offset = get_delta_base(p, &w_curs, &tmp_pos,\n+\t\t\t\t\t\t\t type, obj_offset);\n+\t\t\tif (!base_offset) {\n+\t\t\t\ttype = OBJ_BAD;\n+\t\t\t\tgoto out;\n+\t\t\t}\n+\t\t\t*sizep = get_size_from_delta(p, &w_curs, tmp_pos);\n+\t\t\tif (*sizep == 0) {\n+\t\t\t\ttype = OBJ_BAD;\n+\t\t\t\tgoto out;\n+\t\t\t}\n+\t\t} else {\n+\t\t\t*sizep = size;\n+\t\t}\n+\t}\n+\n+\twhile (type == OBJ_OFS_DELTA || type == OBJ_REF_DELTA) {\n+\t\toff_t base_offset;\n+\t\t/* Push the object we're going to leave behind */\n+\t\tif (poi_stack_nr >= poi_stack_alloc && poi_stack == small_poi_stack) {\n+\t\t\tpoi_stack_alloc = alloc_nr(poi_stack_nr);\n+\t\t\tpoi_stack = xmalloc(sizeof(off_t)*poi_stack_alloc);\n+\t\t\tmemcpy(poi_stack, small_poi_stack, sizeof(off_t)*poi_stack_nr);\n+\t\t} else {\n+\t\t\tALLOC_GROW(poi_stack, poi_stack_nr+1, poi_stack_alloc);\n+\t\t}\n+\t\tpoi_stack[poi_stack_nr++] = obj_offset;\n+\t\t/* If parsing the base offset fails, just unwind */\n+\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n+\t\tif (!base_offset)\n+\t\t\tgoto unwind;\n+\t\tcurpos = obj_offset = base_offset;\n+\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\t\tif (type <= OBJ_NONE) {\n+\t\t\t/* If getting the base itself fails, we first\n+\t\t\t * retry the base, otherwise unwind */\n+\t\t\ttype = retry_bad_packed_offset(p, base_offset);\n+\t\t\tif (type > OBJ_NONE)\n+\t\t\t\tgoto out;\n+\t\t\tgoto unwind;\n+\t\t}\n+\t}\n+\n \tswitch (type) {\n-\tcase OBJ_OFS_DELTA:\n-\tcase OBJ_REF_DELTA:\n-\t\ttype = packed_delta_info(p, &w_curs, curpos,\n-\t\t\t\t\t type, obj_offset, sizep);\n-\t\tbreak;\n+\tcase OBJ_BAD:\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tif (sizep)\n-\t\t\t*sizep = size;\n \t\tbreak;\n \tdefault:\n \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n \t\t type, (uintmax_t)obj_offset, p->pack_name);\n \t\ttype = OBJ_BAD;\n \t}\n+\n+out:\n+\tif (poi_stack != small_poi_stack)\n+\t\tfree(poi_stack);\n \tunuse_pack(&w_curs);\n \treturn type;\n+\n+unwind:\n+\twhile (poi_stack_nr) {\n+\t\tobj_offset = poi_stack[--poi_stack_nr];\n+\t\ttype = retry_bad_packed_offset(p, obj_offset);\n+\t\tif (type > OBJ_NONE)\n+\t\t\tgoto out;\n+\t}\n+\ttype = OBJ_BAD;\n+\tgoto out;\n }\n \n static void *unpack_compressed_entry(struct packed_git *p,\n-- \n1.8.2.266.g8176668\n"},{"id":"212189","messageId":"987ab8138000d0aaa7d1bb6242cced1344e4d339.1364234154.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"cover.1364234154.git.trast@student.ethz.ch","subject":"[PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-25T18:07:40Z","receivedAt":"2013-03-25T18:07:40Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"The delta base cache lookup and test were shared. Refactor them;\nwe'll need both parts again. Also, we'll use the clearing routine\nlater.\n\nSigned-off-by: Thomas Rast \n---\n sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------\n 1 file changed, 32 insertions(+), 13 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 71877a7..bd054d1 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1756,32 +1756,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n \treturn hash % MAX_DELTA_CACHE;\n }\n \n-static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n+static struct delta_base_cache_entry *\n+get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)\n {\n \tunsigned long hash = pack_entry_hash(p, base_offset);\n-\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n+\treturn delta_base_cache + hash;\n+}\n+\n+static int cmp_delta_base_cache_entry(struct delta_base_cache_entry *ent,\n+\t\t\t\t struct packed_git *p, off_t base_offset)\n+{\n \treturn (ent->data && ent->p == p && ent->base_offset == base_offset);\n }\n \n+static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n+{\n+\tstruct delta_base_cache_entry *ent;\n+\tent = get_delta_base_cache_entry(p, base_offset);\n+\treturn cmp_delta_base_cache_entry(ent, p, base_offset);\n+}\n+\n+static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n+{\n+\tent->data = NULL;\n+\tent->lru.next->prev = ent->lru.prev;\n+\tent->lru.prev->next = ent->lru.next;\n+\tdelta_base_cached -= ent->size;\n+}\n+\n static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n \tunsigned long *base_size, enum object_type *type, int keep_cache)\n {\n+\tstruct delta_base_cache_entry *ent;\n \tvoid *ret;\n-\tunsigned long hash = pack_entry_hash(p, base_offset);\n-\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n \n-\tret = ent->data;\n-\tif (!ret || ent->p != p || ent->base_offset != base_offset)\n+\tent = get_delta_base_cache_entry(p, base_offset);\n+\n+\tif (!cmp_delta_base_cache_entry(ent, p, base_offset))\n \t\treturn unpack_entry(p, base_offset, type, base_size);\n \n-\tif (!keep_cache) {\n-\t\tent->data = NULL;\n-\t\tent->lru.next->prev = ent->lru.prev;\n-\t\tent->lru.prev->next = ent->lru.next;\n-\t\tdelta_base_cached -= ent->size;\n-\t} else {\n+\tret = ent->data;\n+\n+\tif (!keep_cache)\n+\t\tclear_delta_base_cache_entry(ent);\n+\telse\n \t\tret = xmemdupz(ent->data, ent->size);\n-\t}\n \t*type = ent->type;\n \t*base_size = ent->size;\n \treturn ret;\n-- \n1.8.2.266.g8176668\n"},{"id":"212190","messageId":"f65b321e148bd51fe369872c5679742e638f8fe5.1364234154.git.trast@student.ethz.ch","threadId":"33193","inReplyTo":"cover.1364234154.git.trast@student.ethz.ch","subject":"[PATCH v2 3/3] sha1_file: remove recursion in unpack_entry","fromName":"Thomas Rast","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-25T18:07:41Z","receivedAt":"2013-03-25T18:07:41Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Similar to the recursion in packed_object_info(), this leads to\nproblems on stack-space-constrained systems in the presence of long\ndelta chains.\n\nWe proceed in three phases:\n\n1. Dig through the delta chain, saving each delta object's offsets and\n size on an ad-hoc stack.\n\n2. Unpack the base object at the bottom.\n\n3. Apply the deltas from the stack.\n\nSigned-off-by: Thomas Rast \n---\n sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------\n 1 file changed, 150 insertions(+), 81 deletions(-)\n\ndiff --git a/sha1_file.c b/sha1_file.c\nindex bd054d1..1b685b9 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -1864,68 +1864,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n static void *read_object(const unsigned char *sha1, enum object_type *type,\n \t\t\t unsigned long *size);\n \n-static void *unpack_delta_entry(struct packed_git *p,\n-\t\t\t\tstruct pack_window **w_curs,\n-\t\t\t\toff_t curpos,\n-\t\t\t\tunsigned long delta_size,\n-\t\t\t\toff_t obj_offset,\n-\t\t\t\tenum object_type *type,\n-\t\t\t\tunsigned long *sizep)\n-{\n-\tvoid *delta_data, *result, *base;\n-\tunsigned long base_size;\n-\toff_t base_offset;\n-\n-\tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n-\tif (!base_offset) {\n-\t\terror(\"failed to validate delta base reference \"\n-\t\t \"at offset %\"PRIuMAX\" from %s\",\n-\t\t (uintmax_t)curpos, p->pack_name);\n-\t\treturn NULL;\n-\t}\n-\tunuse_pack(w_curs);\n-\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n-\tif (!base) {\n-\t\t/*\n-\t\t * We're probably in deep shit, but let's try to fetch\n-\t\t * the required base anyway from another pack or loose.\n-\t\t * This is costly but should happen only in the presence\n-\t\t * of a corrupted pack, and is better than failing outright.\n-\t\t */\n-\t\tstruct revindex_entry *revidx;\n-\t\tconst unsigned char *base_sha1;\n-\t\trevidx = find_pack_revindex(p, base_offset);\n-\t\tif (!revidx)\n-\t\t\treturn NULL;\n-\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n-\t\terror(\"failed to read delta base object %s\"\n-\t\t \" at offset %\"PRIuMAX\" from %s\",\n-\t\t sha1_to_hex(base_sha1), (uintmax_t)base_offset,\n-\t\t p->pack_name);\n-\t\tmark_bad_packed_object(p, base_sha1);\n-\t\tbase = read_object(base_sha1, type, &base_size);\n-\t\tif (!base)\n-\t\t\treturn NULL;\n-\t}\n-\n-\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n-\tif (!delta_data) {\n-\t\terror(\"failed to unpack compressed delta \"\n-\t\t \"at offset %\"PRIuMAX\" from %s\",\n-\t\t (uintmax_t)curpos, p->pack_name);\n-\t\tfree(base);\n-\t\treturn NULL;\n-\t}\n-\tresult = patch_delta(base, base_size,\n-\t\t\t delta_data, delta_size,\n-\t\t\t sizep);\n-\tif (!result)\n-\t\tdie(\"failed to apply delta\");\n-\tfree(delta_data);\n-\tadd_delta_base_cache(p, base_offset, base, base_size, *type);\n-\treturn result;\n-}\n-\n static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n {\n \tstatic FILE *log_file;\n@@ -1946,48 +1884,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n \n int do_check_packed_object_crc;\n \n+#define UNPACK_ENTRY_STACK_PREALLOC 64\n+struct unpack_entry_stack_ent {\n+\toff_t obj_offset;\n+\toff_t curpos;\n+\tunsigned long size;\n+};\n+\n void *unpack_entry(struct packed_git *p, off_t obj_offset,\n-\t\t enum object_type *type, unsigned long *sizep)\n+\t\t enum object_type *final_type, unsigned long *final_size)\n {\n \tstruct pack_window *w_curs = NULL;\n \toff_t curpos = obj_offset;\n-\tvoid *data;\n+\tvoid *data = NULL;\n+\tunsigned long size;\n+\tenum object_type type;\n+\tstruct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];\n+\tstruct unpack_entry_stack_ent *delta_stack = small_delta_stack;\n+\tint delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;\n+\tint base_from_cache = 0;\n \n \tif (log_pack_access)\n \t\twrite_pack_access_log(p, obj_offset);\n \n-\tif (do_check_packed_object_crc && p->index_version > 1) {\n-\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n-\t\tunsigned long len = revidx[1].offset - obj_offset;\n-\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n-\t\t\tconst unsigned char *sha1 =\n-\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n-\t\t\terror(\"bad packed object CRC for %s\",\n-\t\t\t sha1_to_hex(sha1));\n-\t\t\tmark_bad_packed_object(p, sha1);\n-\t\t\tunuse_pack(&w_curs);\n-\t\t\treturn NULL;\n+\t/* PHASE 1: drill down to the innermost base object */\n+\tfor (;;) {\n+\t\toff_t base_offset;\n+\t\tint i;\n+\t\tstruct delta_base_cache_entry *ent;\n+\n+\t\tif (do_check_packed_object_crc && p->index_version > 1) {\n+\t\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n+\t\t\tunsigned long len = revidx[1].offset - obj_offset;\n+\t\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n+\t\t\t\tconst unsigned char *sha1 =\n+\t\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\terror(\"bad packed object CRC for %s\",\n+\t\t\t\t sha1_to_hex(sha1));\n+\t\t\t\tmark_bad_packed_object(p, sha1);\n+\t\t\t\tunuse_pack(&w_curs);\n+\t\t\t\treturn NULL;\n+\t\t\t}\n+\t\t}\n+\n+\t\tent = get_delta_base_cache_entry(p, curpos);\n+\t\tif (cmp_delta_base_cache_entry(ent, p, curpos)) {\n+\t\t\ttype = ent->type;\n+\t\t\tdata = ent->data;\n+\t\t\tsize = ent->size;\n+\t\t\tclear_delta_base_cache_entry(ent);\n+\t\t\tbase_from_cache = 1;\n+\t\t\tbreak;\n+\t\t}\n+\n+\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n+\t\tif (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)\n+\t\t\tbreak;\n+\n+\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n+\t\tif (!base_offset) {\n+\t\t\terror(\"failed to validate delta base reference \"\n+\t\t\t \"at offset %\"PRIuMAX\" from %s\",\n+\t\t\t (uintmax_t)curpos, p->pack_name);\n+\t\t\t/* bail to phase 2, in hopes of recovery */\n+\t\t\tdata = NULL;\n+\t\t\tbreak;\n \t\t}\n+\n+\t\t/* push object, proceed to base */\n+\t\tif (delta_stack_nr >= delta_stack_alloc\n+\t\t && delta_stack == small_delta_stack) {\n+\t\t\tdelta_stack_alloc = alloc_nr(delta_stack_nr);\n+\t\t\tdelta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);\n+\t\t\tmemcpy(delta_stack, small_delta_stack,\n+\t\t\t sizeof(*delta_stack)*delta_stack_nr);\n+\t\t} else {\n+\t\t\tALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);\n+\t\t}\n+\t\ti = delta_stack_nr++;\n+\t\tdelta_stack[i].obj_offset = obj_offset;\n+\t\tdelta_stack[i].curpos = curpos;\n+\t\tdelta_stack[i].size = size;\n+\n+\t\tcurpos = obj_offset = base_offset;\n \t}\n \n-\t*type = unpack_object_header(p, &w_curs, &curpos, sizep);\n-\tswitch (*type) {\n+\t/* PHASE 2: handle the base */\n+\tswitch (type) {\n \tcase OBJ_OFS_DELTA:\n \tcase OBJ_REF_DELTA:\n-\t\tdata = unpack_delta_entry(p, &w_curs, curpos, *sizep,\n-\t\t\t\t\t obj_offset, type, sizep);\n+\t\tif (data)\n+\t\t\tdie(\"BUG in unpack_entry: left loop at a valid delta\");\n \t\tbreak;\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, *sizep);\n+\t\tif (!base_from_cache)\n+\t\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, size);\n \t\tbreak;\n \tdefault:\n \t\tdata = NULL;\n \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n-\t\t *type, (uintmax_t)obj_offset, p->pack_name);\n+\t\t type, (uintmax_t)obj_offset, p->pack_name);\n \t}\n+\n+\t/* PHASE 3: apply deltas in order */\n+\n+\t/* invariants:\n+\t * 'data' holds the base data, or NULL if there was corruption\n+\t */\n+\twhile (delta_stack_nr) {\n+\t\tvoid *delta_data;\n+\t\tvoid *base = data;\n+\t\tunsigned long delta_size, base_size = size;\n+\t\tint i;\n+\n+\t\tdata = NULL;\n+\n+\t\tif (base)\n+\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n+\n+\t\tif (!base) {\n+\t\t\t/*\n+\t\t\t * We're probably in deep shit, but let's try to fetch\n+\t\t\t * the required base anyway from another pack or loose.\n+\t\t\t * This is costly but should happen only in the presence\n+\t\t\t * of a corrupted pack, and is better than failing outright.\n+\t\t\t */\n+\t\t\tstruct revindex_entry *revidx;\n+\t\t\tconst unsigned char *base_sha1;\n+\t\t\trevidx = find_pack_revindex(p, obj_offset);\n+\t\t\tif (revidx) {\n+\t\t\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n+\t\t\t\terror(\"failed to read delta base object %s\"\n+\t\t\t\t \" at offset %\"PRIuMAX\" from %s\",\n+\t\t\t\t sha1_to_hex(base_sha1), (uintmax_t)obj_offset,\n+\t\t\t\t p->pack_name);\n+\t\t\t\tmark_bad_packed_object(p, base_sha1);\n+\t\t\t\tbase = read_object(base_sha1, &type, &base_size);\n+\t\t\t}\n+\t\t}\n+\n+\t\ti = --delta_stack_nr;\n+\t\tobj_offset = delta_stack[i].obj_offset;\n+\t\tcurpos = delta_stack[i].curpos;\n+\t\tdelta_size = delta_stack[i].size;\n+\n+\t\tif (!base)\n+\t\t\tcontinue;\n+\n+\t\tdelta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);\n+\n+\t\tif (!delta_data) {\n+\t\t\terror(\"failed to unpack compressed delta \"\n+\t\t\t \"at offset %\"PRIuMAX\" from %s\",\n+\t\t\t (uintmax_t)curpos, p->pack_name);\n+\t\t\tfree(base);\n+\t\t\tdata = NULL;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tdata = patch_delta(base, base_size,\n+\t\t\t\t delta_data, delta_size,\n+\t\t\t\t &size);\n+\t\tif (!data)\n+\t\t\tdie(\"failed to apply delta\");\n+\n+\t\tfree (delta_data);\n+\t}\n+\n+\t*final_type = type;\n+\t*final_size = size;\n+\n \tunuse_pack(&w_curs);\n \treturn data;\n }\n-- \n1.8.2.266.g8176668\n"},{"id":"212192","messageId":"7vtxnzxs1p.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"87620faky3.fsf@linux-k42r.v.cablecom.net","subject":"Re: [PATCH] sha1_file: remove recursion in packed_object_info","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-25T18:17:38Z","receivedAt":"2013-03-25T18:17:38Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"thomas writes:\n\n> Junio C Hamano writes:\n>\n>> The following comment is also lost but...\n>>\n>>> -\t/* We choose to only get the type of the base object and\n>>> -\t * ignore potentially corrupt pack file that expects the delta\n>>> -\t * based on a base with a wrong size. This saves tons of\n>>> -\t * inflate() calls.\n>>> -\t */\n>>> -\tif (sizep) {\n>>> -\t\t*sizep = get_size_from_delta(p, w_curs, curpos);\n>>> -\t\tif (*sizep == 0)\n>>> -\t\t\ttype = OBJ_BAD;\n>>\n>> ... is this check correct? There is an equivalent check at the\n>> beginning of the new packed_object_info() to error out a deltified\n>> result. Why is an object whose size is 0 bad?\n>\n> Cc'ing Nicolas, but I think there are several reasons:\n>\n> If it's a delta, then according to docs[1] it starts with the SHA1 of\n> the base object, plus the deflated data. So it is at least 20 bytes.\n\nget_size_from_delta() grabs the size, the number you would get in\nthe third parameter of read_sha1_file(), of the result of applying\nthe delta we are looking at. The part that stores this information\nis called the \"compressed delta data\" in the document you are\nlooking at.\n\nThe function you want to look at is patch_delta(), where it grabs\ntwo such sizes from the delta stream with get_delta_hdr_size().\n\nA delta stream begins with:\n\n * preimage length, expressed as a 7-bit-per-byte varint;\n * postimage length, expressed as a 7-bit-per-byte varint;\n\nfollowed by number of records, each prefixed by a command byte.\n\n * Command byte with its 8th bit set records source offset and\n size (max 32 and 24 bits, respectively---other 7 bits in the\n command byte tells us how large the offset and size are) and\n tells us to insert a copy of that region at the current point.\n\n * Command byte between 1-127 (inclusive) tells us to add that\n many bytes that follow the command byte from the delta stream\n at the current point.\n\n * Command byte 0 is an error.\n\nAnd get_size_from_delta() skips the preimage length, grabs postimage\nlength and returns the latter. It is how we decide how many bytes\nwe need to allocate to hold the result of applying the delta.\n\n> If it's not a delta, then it must start with ' \\0', which\n> even after compression cannot possibly be 0 bytes.\n>\n> Either way, get_size_from_delta() also uses 0 as the error return.\n\nYes, that is why I said \"is this check correct?\". As I already\nsaid, I think the only two things that protects us from creating a\ndelta whose postimage size is 0 are the fact that we do not even\nattempt to deltify anything smaller than 50 bytes in pack-objects,\nand create_delta() refuses to create a delta to produce an empty\npostimage.\n"},{"id":"212249","messageId":"7vtxnzul42.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"987ab8138000d0aaa7d1bb6242cced1344e4d339.1364234154.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-25T23:15:41Z","receivedAt":"2013-03-25T23:15:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> The delta base cache lookup and test were shared. Refactor them;\n> we'll need both parts again. Also, we'll use the clearing routine\n> later.\n>\n> Signed-off-by: Thomas Rast \n> ---\n\nLooks like a very straight-forward rewrite.\n\nThe only little concern I may have is this cmp_* function tells us\n\"I found it!\" by returning true, which is counter-intuitive to the\nreaders of the caller (not the callee).\n\nI think it makes sense to compare delta-base-cache entries only for\nequality, so eq-delta-base-cache-entry might be a better name for\nit, perhaps?\n\n> sha1_file.c | 45 ++++++++++++++++++++++++++++++++-------------\n> 1 file changed, 32 insertions(+), 13 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index 71877a7..bd054d1 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1756,32 +1756,51 @@ static unsigned long pack_entry_hash(struct packed_git *p, off_t base_offset)\n> \treturn hash % MAX_DELTA_CACHE;\n> }\n> \n> -static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n> +static struct delta_base_cache_entry *\n> +get_delta_base_cache_entry(struct packed_git *p, off_t base_offset)\n> {\n> \tunsigned long hash = pack_entry_hash(p, base_offset);\n> -\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n> +\treturn delta_base_cache + hash;\n> +}\n> +\n> +static int cmp_delta_base_cache_entry(struct delta_base_cache_entry *ent,\n> +\t\t\t\t struct packed_git *p, off_t base_offset)\n> +{\n> \treturn (ent->data && ent->p == p && ent->base_offset == base_offset);\n> }\n> \n> +static int in_delta_base_cache(struct packed_git *p, off_t base_offset)\n> +{\n> +\tstruct delta_base_cache_entry *ent;\n> +\tent = get_delta_base_cache_entry(p, base_offset);\n> +\treturn cmp_delta_base_cache_entry(ent, p, base_offset);\n> +}\n> +\n> +static void clear_delta_base_cache_entry(struct delta_base_cache_entry *ent)\n> +{\n> +\tent->data = NULL;\n> +\tent->lru.next->prev = ent->lru.prev;\n> +\tent->lru.prev->next = ent->lru.next;\n> +\tdelta_base_cached -= ent->size;\n> +}\n> +\n> static void *cache_or_unpack_entry(struct packed_git *p, off_t base_offset,\n> \tunsigned long *base_size, enum object_type *type, int keep_cache)\n> {\n> +\tstruct delta_base_cache_entry *ent;\n> \tvoid *ret;\n> -\tunsigned long hash = pack_entry_hash(p, base_offset);\n> -\tstruct delta_base_cache_entry *ent = delta_base_cache + hash;\n> \n> -\tret = ent->data;\n> -\tif (!ret || ent->p != p || ent->base_offset != base_offset)\n> +\tent = get_delta_base_cache_entry(p, base_offset);\n> +\n> +\tif (!cmp_delta_base_cache_entry(ent, p, base_offset))\n> \t\treturn unpack_entry(p, base_offset, type, base_size);\n> \n> -\tif (!keep_cache) {\n> -\t\tent->data = NULL;\n> -\t\tent->lru.next->prev = ent->lru.prev;\n> -\t\tent->lru.prev->next = ent->lru.next;\n> -\t\tdelta_base_cached -= ent->size;\n> -\t} else {\n> +\tret = ent->data;\n> +\n> +\tif (!keep_cache)\n> +\t\tclear_delta_base_cache_entry(ent);\n> +\telse\n> \t\tret = xmemdupz(ent->data, ent->size);\n> -\t}\n> \t*type = ent->type;\n> \t*base_size = ent->size;\n> \treturn ret;\n"},{"id":"212250","messageId":"7vppynuky7.fsf@alter.siamese.dyndns.org","threadId":"33193","inReplyTo":"f65b321e148bd51fe369872c5679742e638f8fe5.1364234154.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 3/3] sha1_file: remove recursion in unpack_entry","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-03-25T23:19:12Z","receivedAt":"2013-03-25T23:19:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Thomas Rast writes:\n\n> Similar to the recursion in packed_object_info(), this leads to\n> problems on stack-space-constrained systems in the presence of long\n> delta chains.\n>\n> We proceed in three phases:\n>\n> 1. Dig through the delta chain, saving each delta object's offsets and\n> size on an ad-hoc stack.\n>\n> 2. Unpack the base object at the bottom.\n>\n> 3. Apply the deltas from the stack.\n>\n> Signed-off-by: Thomas Rast \n\nThe above made me nervous but you are not pushing the actual delta\ndata on the stack, so the patch looks good from a quick scan.\n\nThanks. Will queue.\n\n> ---\n> sha1_file.c | 231 +++++++++++++++++++++++++++++++++++++++---------------------\n> 1 file changed, 150 insertions(+), 81 deletions(-)\n>\n> diff --git a/sha1_file.c b/sha1_file.c\n> index bd054d1..1b685b9 100644\n> --- a/sha1_file.c\n> +++ b/sha1_file.c\n> @@ -1864,68 +1864,6 @@ static void add_delta_base_cache(struct packed_git *p, off_t base_offset,\n> static void *read_object(const unsigned char *sha1, enum object_type *type,\n> \t\t\t unsigned long *size);\n> \n> -static void *unpack_delta_entry(struct packed_git *p,\n> -\t\t\t\tstruct pack_window **w_curs,\n> -\t\t\t\toff_t curpos,\n> -\t\t\t\tunsigned long delta_size,\n> -\t\t\t\toff_t obj_offset,\n> -\t\t\t\tenum object_type *type,\n> -\t\t\t\tunsigned long *sizep)\n> -{\n> -\tvoid *delta_data, *result, *base;\n> -\tunsigned long base_size;\n> -\toff_t base_offset;\n> -\n> -\tbase_offset = get_delta_base(p, w_curs, &curpos, *type, obj_offset);\n> -\tif (!base_offset) {\n> -\t\terror(\"failed to validate delta base reference \"\n> -\t\t \"at offset %\"PRIuMAX\" from %s\",\n> -\t\t (uintmax_t)curpos, p->pack_name);\n> -\t\treturn NULL;\n> -\t}\n> -\tunuse_pack(w_curs);\n> -\tbase = cache_or_unpack_entry(p, base_offset, &base_size, type, 0);\n> -\tif (!base) {\n> -\t\t/*\n> -\t\t * We're probably in deep shit, but let's try to fetch\n> -\t\t * the required base anyway from another pack or loose.\n> -\t\t * This is costly but should happen only in the presence\n> -\t\t * of a corrupted pack, and is better than failing outright.\n> -\t\t */\n> -\t\tstruct revindex_entry *revidx;\n> -\t\tconst unsigned char *base_sha1;\n> -\t\trevidx = find_pack_revindex(p, base_offset);\n> -\t\tif (!revidx)\n> -\t\t\treturn NULL;\n> -\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n> -\t\terror(\"failed to read delta base object %s\"\n> -\t\t \" at offset %\"PRIuMAX\" from %s\",\n> -\t\t sha1_to_hex(base_sha1), (uintmax_t)base_offset,\n> -\t\t p->pack_name);\n> -\t\tmark_bad_packed_object(p, base_sha1);\n> -\t\tbase = read_object(base_sha1, type, &base_size);\n> -\t\tif (!base)\n> -\t\t\treturn NULL;\n> -\t}\n> -\n> -\tdelta_data = unpack_compressed_entry(p, w_curs, curpos, delta_size);\n> -\tif (!delta_data) {\n> -\t\terror(\"failed to unpack compressed delta \"\n> -\t\t \"at offset %\"PRIuMAX\" from %s\",\n> -\t\t (uintmax_t)curpos, p->pack_name);\n> -\t\tfree(base);\n> -\t\treturn NULL;\n> -\t}\n> -\tresult = patch_delta(base, base_size,\n> -\t\t\t delta_data, delta_size,\n> -\t\t\t sizep);\n> -\tif (!result)\n> -\t\tdie(\"failed to apply delta\");\n> -\tfree(delta_data);\n> -\tadd_delta_base_cache(p, base_offset, base, base_size, *type);\n> -\treturn result;\n> -}\n> -\n> static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n> {\n> \tstatic FILE *log_file;\n> @@ -1946,48 +1884,179 @@ static void write_pack_access_log(struct packed_git *p, off_t obj_offset)\n> \n> int do_check_packed_object_crc;\n> \n> +#define UNPACK_ENTRY_STACK_PREALLOC 64\n> +struct unpack_entry_stack_ent {\n> +\toff_t obj_offset;\n> +\toff_t curpos;\n> +\tunsigned long size;\n> +};\n> +\n> void *unpack_entry(struct packed_git *p, off_t obj_offset,\n> -\t\t enum object_type *type, unsigned long *sizep)\n> +\t\t enum object_type *final_type, unsigned long *final_size)\n> {\n> \tstruct pack_window *w_curs = NULL;\n> \toff_t curpos = obj_offset;\n> -\tvoid *data;\n> +\tvoid *data = NULL;\n> +\tunsigned long size;\n> +\tenum object_type type;\n> +\tstruct unpack_entry_stack_ent small_delta_stack[UNPACK_ENTRY_STACK_PREALLOC];\n> +\tstruct unpack_entry_stack_ent *delta_stack = small_delta_stack;\n> +\tint delta_stack_nr = 0, delta_stack_alloc = UNPACK_ENTRY_STACK_PREALLOC;\n> +\tint base_from_cache = 0;\n> \n> \tif (log_pack_access)\n> \t\twrite_pack_access_log(p, obj_offset);\n> \n> -\tif (do_check_packed_object_crc && p->index_version > 1) {\n> -\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n> -\t\tunsigned long len = revidx[1].offset - obj_offset;\n> -\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n> -\t\t\tconst unsigned char *sha1 =\n> -\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n> -\t\t\terror(\"bad packed object CRC for %s\",\n> -\t\t\t sha1_to_hex(sha1));\n> -\t\t\tmark_bad_packed_object(p, sha1);\n> -\t\t\tunuse_pack(&w_curs);\n> -\t\t\treturn NULL;\n> +\t/* PHASE 1: drill down to the innermost base object */\n> +\tfor (;;) {\n> +\t\toff_t base_offset;\n> +\t\tint i;\n> +\t\tstruct delta_base_cache_entry *ent;\n> +\n> +\t\tif (do_check_packed_object_crc && p->index_version > 1) {\n> +\t\t\tstruct revindex_entry *revidx = find_pack_revindex(p, obj_offset);\n> +\t\t\tunsigned long len = revidx[1].offset - obj_offset;\n> +\t\t\tif (check_pack_crc(p, &w_curs, obj_offset, len, revidx->nr)) {\n> +\t\t\t\tconst unsigned char *sha1 =\n> +\t\t\t\t\tnth_packed_object_sha1(p, revidx->nr);\n> +\t\t\t\terror(\"bad packed object CRC for %s\",\n> +\t\t\t\t sha1_to_hex(sha1));\n> +\t\t\t\tmark_bad_packed_object(p, sha1);\n> +\t\t\t\tunuse_pack(&w_curs);\n> +\t\t\t\treturn NULL;\n> +\t\t\t}\n> +\t\t}\n> +\n> +\t\tent = get_delta_base_cache_entry(p, curpos);\n> +\t\tif (cmp_delta_base_cache_entry(ent, p, curpos)) {\n> +\t\t\ttype = ent->type;\n> +\t\t\tdata = ent->data;\n> +\t\t\tsize = ent->size;\n> +\t\t\tclear_delta_base_cache_entry(ent);\n> +\t\t\tbase_from_cache = 1;\n> +\t\t\tbreak;\n> +\t\t}\n> +\n> +\t\ttype = unpack_object_header(p, &w_curs, &curpos, &size);\n> +\t\tif (type != OBJ_OFS_DELTA && type != OBJ_REF_DELTA)\n> +\t\t\tbreak;\n> +\n> +\t\tbase_offset = get_delta_base(p, &w_curs, &curpos, type, obj_offset);\n> +\t\tif (!base_offset) {\n> +\t\t\terror(\"failed to validate delta base reference \"\n> +\t\t\t \"at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t (uintmax_t)curpos, p->pack_name);\n> +\t\t\t/* bail to phase 2, in hopes of recovery */\n> +\t\t\tdata = NULL;\n> +\t\t\tbreak;\n> \t\t}\n> +\n> +\t\t/* push object, proceed to base */\n> +\t\tif (delta_stack_nr >= delta_stack_alloc\n> +\t\t && delta_stack == small_delta_stack) {\n> +\t\t\tdelta_stack_alloc = alloc_nr(delta_stack_nr);\n> +\t\t\tdelta_stack = xmalloc(sizeof(*delta_stack)*delta_stack_alloc);\n> +\t\t\tmemcpy(delta_stack, small_delta_stack,\n> +\t\t\t sizeof(*delta_stack)*delta_stack_nr);\n> +\t\t} else {\n> +\t\t\tALLOC_GROW(delta_stack, delta_stack_nr+1, delta_stack_alloc);\n> +\t\t}\n> +\t\ti = delta_stack_nr++;\n> +\t\tdelta_stack[i].obj_offset = obj_offset;\n> +\t\tdelta_stack[i].curpos = curpos;\n> +\t\tdelta_stack[i].size = size;\n> +\n> +\t\tcurpos = obj_offset = base_offset;\n> \t}\n> \n> -\t*type = unpack_object_header(p, &w_curs, &curpos, sizep);\n> -\tswitch (*type) {\n> +\t/* PHASE 2: handle the base */\n> +\tswitch (type) {\n> \tcase OBJ_OFS_DELTA:\n> \tcase OBJ_REF_DELTA:\n> -\t\tdata = unpack_delta_entry(p, &w_curs, curpos, *sizep,\n> -\t\t\t\t\t obj_offset, type, sizep);\n> +\t\tif (data)\n> +\t\t\tdie(\"BUG in unpack_entry: left loop at a valid delta\");\n> \t\tbreak;\n> \tcase OBJ_COMMIT:\n> \tcase OBJ_TREE:\n> \tcase OBJ_BLOB:\n> \tcase OBJ_TAG:\n> -\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, *sizep);\n> +\t\tif (!base_from_cache)\n> +\t\t\tdata = unpack_compressed_entry(p, &w_curs, curpos, size);\n> \t\tbreak;\n> \tdefault:\n> \t\tdata = NULL;\n> \t\terror(\"unknown object type %i at offset %\"PRIuMAX\" in %s\",\n> -\t\t *type, (uintmax_t)obj_offset, p->pack_name);\n> +\t\t type, (uintmax_t)obj_offset, p->pack_name);\n> \t}\n> +\n> +\t/* PHASE 3: apply deltas in order */\n> +\n> +\t/* invariants:\n> +\t * 'data' holds the base data, or NULL if there was corruption\n> +\t */\n> +\twhile (delta_stack_nr) {\n> +\t\tvoid *delta_data;\n> +\t\tvoid *base = data;\n> +\t\tunsigned long delta_size, base_size = size;\n> +\t\tint i;\n> +\n> +\t\tdata = NULL;\n> +\n> +\t\tif (base)\n> +\t\t\tadd_delta_base_cache(p, obj_offset, base, base_size, type);\n> +\n> +\t\tif (!base) {\n> +\t\t\t/*\n> +\t\t\t * We're probably in deep shit, but let's try to fetch\n> +\t\t\t * the required base anyway from another pack or loose.\n> +\t\t\t * This is costly but should happen only in the presence\n> +\t\t\t * of a corrupted pack, and is better than failing outright.\n> +\t\t\t */\n> +\t\t\tstruct revindex_entry *revidx;\n> +\t\t\tconst unsigned char *base_sha1;\n> +\t\t\trevidx = find_pack_revindex(p, obj_offset);\n> +\t\t\tif (revidx) {\n> +\t\t\t\tbase_sha1 = nth_packed_object_sha1(p, revidx->nr);\n> +\t\t\t\terror(\"failed to read delta base object %s\"\n> +\t\t\t\t \" at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t\t sha1_to_hex(base_sha1), (uintmax_t)obj_offset,\n> +\t\t\t\t p->pack_name);\n> +\t\t\t\tmark_bad_packed_object(p, base_sha1);\n> +\t\t\t\tbase = read_object(base_sha1, &type, &base_size);\n> +\t\t\t}\n> +\t\t}\n> +\n> +\t\ti = --delta_stack_nr;\n> +\t\tobj_offset = delta_stack[i].obj_offset;\n> +\t\tcurpos = delta_stack[i].curpos;\n> +\t\tdelta_size = delta_stack[i].size;\n> +\n> +\t\tif (!base)\n> +\t\t\tcontinue;\n> +\n> +\t\tdelta_data = unpack_compressed_entry(p, &w_curs, curpos, delta_size);\n> +\n> +\t\tif (!delta_data) {\n> +\t\t\terror(\"failed to unpack compressed delta \"\n> +\t\t\t \"at offset %\"PRIuMAX\" from %s\",\n> +\t\t\t (uintmax_t)curpos, p->pack_name);\n> +\t\t\tfree(base);\n> +\t\t\tdata = NULL;\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tdata = patch_delta(base, base_size,\n> +\t\t\t\t delta_data, delta_size,\n> +\t\t\t\t &size);\n> +\t\tif (!data)\n> +\t\t\tdie(\"failed to apply delta\");\n> +\n> +\t\tfree (delta_data);\n> +\t}\n> +\n> +\t*final_type = type;\n> +\t*final_size = size;\n> +\n> \tunuse_pack(&w_curs);\n> \treturn data;\n> }\n"},{"id":"212262","messageId":"alpine.LFD.2.03.1303252333200.1372@syhkavp.arg","threadId":"33193","inReplyTo":"cover.1364234154.git.trast@student.ethz.ch","subject":"Re: [PATCH v2 0/3] Recursion-free unpack_entry and packed_object_info","fromName":"Nicolas Pitre","fromEmail":"nico@fluxnic.net","sentAt":"2013-03-26T03:37:57Z","receivedAt":"2013-03-26T03:37:57Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 25 Mar 2013, Thomas Rast wrote:\n\n> This is a fixed version of the initial patch, plus a two-patch\n> implementation of a recursion-free unpack_entry. (I narrowly resisted\n> using \"unrecursify\" to describe it.)\n\nHmmm... the intention is sensible and the patches look sane, however I \ndon't have my brain wrapped around this code as I used to, so I might \nbe missing something.\n\n\nNicolas\n"},{"id":"212284","messageId":"87y5da8liw.fsf@linux-k42r.v.cablecom.net","threadId":"33193","inReplyTo":"7vtxnzul42.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH v2 2/3] Refactor parts of in_delta_base_cache/cache_or_unpack_entry","fromName":"thomas","fromEmail":"trast@student.ethz.ch","sentAt":"2013-03-26T11:09:59Z","receivedAt":"2013-03-26T11:09:59Z","isPatch":true,"sender":{"key":"tr@thomasrast.ch","avatar":"https://avatars.githubusercontent.com/u/153510?v=4"},"body":"Junio C Hamano writes:\n\n> Thomas Rast writes:\n>\n>> The delta base cache lookup and test were shared. Refactor them;\n>> we'll need both parts again. Also, we'll use the clearing routine\n>> later.\n>>\n>> Signed-off-by: Thomas Rast \n>> ---\n>\n> Looks like a very straight-forward rewrite.\n>\n> The only little concern I may have is this cmp_* function tells us\n> \"I found it!\" by returning true, which is counter-intuitive to the\n> readers of the caller (not the callee).\n>\n> I think it makes sense to compare delta-base-cache entries only for\n> equality, so eq-delta-base-cache-entry might be a better name for\n> it, perhaps?\n\nTrue. I'll resend.\n\n-- \nThomas Rast\ntrast@{inf,student}.ethz.ch\n"}]}