{"thread":{"id":"36422","subject":"[PATCH] git tag --contains : avoid stack overflow","startedAt":"2014-04-16T14:15:19Z","lastAt":"2014-09-23T22:41:09Z","messageCount":24,"participants":["Stepan Kasal","Jeff King","Johannes Schindelin","Junio C Hamano","Andreas Schwab"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"238934","messageId":"20140416141519.GA9684@camelia.ucw.cz","threadId":"36422","inReplyTo":null,"subject":"[PATCH] git tag --contains : avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-16T14:15:19Z","receivedAt":"2014-04-16T14:15:19Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\nDate: Sat, 10 Nov 2012 18:36:10 +0100\n\nIn large repos, the recursion implementation of contains(commit,\ncommit_list) may result in a stack overflow. Replace the recursion with\na loop to fix it.\n\nThis problem is more apparent on Windows than on Linux, where the stack\nis more limited by default.\n\nSee also this thread on the msysGit list:\n\n\thttps://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion\n\n[jes: re-written to imitate the original recursion more closely]\n\nThomas Braun pointed out several documentation shortcomings.\n\nSigned-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\nTested-by: Stepan Kasal <kasal@ucw.cz>\nThanks-to: Thomas Braun <thomas.braun@byte-physics.de>\n---\n builtin/tag.c  | 81 ++++++++++++++++++++++++++++++++++++++++++++++++----------\n t/t7004-tag.sh | 21 +++++++++++++++\n 2 files changed, 88 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 74d3780..79c8c28 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -73,11 +73,13 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \treturn 0;\n }\n \n-static int contains_recurse(struct commit *candidate,\n+/*\n+ * Test whether the candidate or one of its parents is contained in the list.\n+ * Do not recurse to find out, though, but return -1 if inconclusive.\n+ */\n+static int contains_test(struct commit *candidate,\n \t\t\t    const struct commit_list *want)\n {\n-\tstruct commit_list *p;\n-\n \t/* was it previously marked as containing a want commit? */\n \tif (candidate->object.flags & TMP_MARK)\n \t\treturn 1;\n@@ -85,26 +87,77 @@ static int contains_recurse(struct commit *candidate,\n \tif (candidate->object.flags & UNINTERESTING)\n \t\treturn 0;\n \t/* or are we it? */\n-\tif (in_commit_list(want, candidate))\n+\tif (in_commit_list(want, candidate)) {\n+\t\tcandidate->object.flags |= TMP_MARK;\n \t\treturn 1;\n+\t}\n \n \tif (parse_commit(candidate) < 0)\n \t\treturn 0;\n \n-\t/* Otherwise recurse and mark ourselves for future traversals. */\n-\tfor (p = candidate->parents; p; p = p->next) {\n-\t\tif (contains_recurse(p->item, want)) {\n-\t\t\tcandidate->object.flags |= TMP_MARK;\n-\t\t\treturn 1;\n-\t\t}\n-\t}\n-\tcandidate->object.flags |= UNINTERESTING;\n-\treturn 0;\n+\treturn -1;\n+}\n+\n+/*\n+ * Mimicking the real stack, this stack lives on the heap, avoiding stack\n+ * overflows.\n+ *\n+ * At each recursion step, the stack items points to the commits whose\n+ * ancestors are to be inspected.\n+ */\n+struct stack {\n+\tint nr, alloc;\n+\tstruct stack_entry {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *parents;\n+\t} *stack;\n+};\n+\n+static void push_to_stack(struct commit *candidate, struct stack *stack)\n+{\n+\tint index = stack->nr++;\n+\tALLOC_GROW(stack->stack, stack->nr, stack->alloc);\n+\tstack->stack[index].commit = candidate;\n+\tstack->stack[index].parents = candidate->parents;\n }\n \n static int contains(struct commit *candidate, const struct commit_list *want)\n {\n-\treturn contains_recurse(candidate, want);\n+\tstruct stack stack = { 0, 0, NULL };\n+\tint result = contains_test(candidate, want);\n+\n+\tif (result >= 0)\n+\t\treturn result;\n+\n+\tpush_to_stack(candidate, &stack);\n+\twhile (stack.nr) {\n+\t\tstruct stack_entry *entry = &stack.stack[stack.nr - 1];\n+\t\tstruct commit *commit = entry->commit;\n+\t\tstruct commit_list *parents = entry->parents;\n+\n+\t\tif (!parents) {\n+\t\t\tcommit->object.flags = UNINTERESTING;\n+\t\t\tstack.nr--;\n+\t\t}\n+\t\t/*\n+\t\t * If we just popped the stack, parents->item has been marked,\n+\t\t * therefore contains_test will return a meaningful 0 or 1.\n+\t\t */\n+\t\telse switch (contains_test(parents->item, want)) {\n+\t\tcase 1:\n+\t\t\tcommit->object.flags |= TMP_MARK;\n+\t\t\tstack.nr--;\n+\t\t\tbreak;\n+\t\tcase 0:\n+\t\t\tentry->parents = parents->next;\n+\t\t\tbreak;\n+\t\tdefault:\n+\t\t\tpush_to_stack(parents->item, &stack);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tfree(stack.stack);\n+\treturn contains_test(candidate, want);\n }\n \n static void show_tag_lines(const unsigned char *sha1, int lines)\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex c8d6e9f..edaff13 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1380,4 +1380,25 @@ test_expect_success 'multiple --points-at are OR-ed together' '\n \ttest_cmp expect actual\n '\n \n+>expect\n+# ulimit is a bash builtin; we can rely on that in MinGW, but nowhere else\n+test_expect_success MINGW '--contains works in a deep repo' '\n+\tulimit -s 64\n+\ti=1 &&\n+\twhile test $i -lt 1000\n+\tdo\n+\t\techo \"commit refs/heads/master\n+committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n+data <<EOF\n+commit #$i\n+EOF\"\n+\t\ttest $i = 1 && echo \"from refs/heads/master^0\"\n+\t\ti=$(($i + 1))\n+\tdone | git fast-import &&\n+\tgit checkout master &&\n+\tgit tag far-far-away HEAD^ &&\n+\tgit tag --contains HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.9.2.msysgit.0.154.g978f18d\n"},{"id":"238939","messageId":"20140416154653.GB4691@sigill.intra.peff.net","threadId":"36422","inReplyTo":"20140416141519.GA9684@camelia.ucw.cz","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-16T15:46:54Z","receivedAt":"2014-04-16T15:46:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 16, 2014 at 04:15:19PM +0200, Stepan Kasal wrote:\n\n> From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n> Date: Sat, 10 Nov 2012 18:36:10 +0100\n> \n> In large repos, the recursion implementation of contains(commit,\n> commit_list) may result in a stack overflow. Replace the recursion with\n> a loop to fix it.\n> \n> This problem is more apparent on Windows than on Linux, where the stack\n> is more limited by default.\n\nI think this is a good thing to be doing, and it looks mostly good to\nme. A few comments:\n\n> -static int contains_recurse(struct commit *candidate,\n> +/*\n> + * Test whether the candidate or one of its parents is contained in the list.\n> + * Do not recurse to find out, though, but return -1 if inconclusive.\n> + */\n> +static int contains_test(struct commit *candidate,\n>  \t\t\t    const struct commit_list *want)\n\nCan we turn this return value into\n\n  enum {\n\tCONTAINS_UNKNOWN = -1,\n\tCONTAINS_NO = 0,\n\tCONTAINS_YES = 1,\n  } contains_result;\n\nto make the code a little more self-documenting?\n\n>  static int contains(struct commit *candidate, const struct commit_list *want)\n>  {\n> -\treturn contains_recurse(candidate, want);\n> +\tstruct stack stack = { 0, 0, NULL };\n> +\tint result = contains_test(candidate, want);\n> +\n> +\tif (result >= 0)\n> +\t\treturn result;\n\nThen this can become:\n\n  if (result != CONTAINS_UNKNOWN)\n\treturn result;\n\n> +\t\tif (!parents) {\n> +\t\t\tcommit->object.flags = UNINTERESTING;\n> +\t\t\tstack.nr--;\n> +\t\t}\n\nShouldn't this be \"|=\" when setting the flag?\n\n> +\t\t/*\n> +\t\t * If we just popped the stack, parents->item has been marked,\n> +\t\t * therefore contains_test will return a meaningful 0 or 1.\n> +\t\t */\n> +\t\telse switch (contains_test(parents->item, want)) {\n> +\t\tcase 1:\n> +\t\t\tcommit->object.flags |= TMP_MARK;\n> +\t\t\tstack.nr--;\n> +\t\t\tbreak;\n> +\t\tcase 0:\n> +\t\t\tentry->parents = parents->next;\n> +\t\t\tbreak;\n> +\t\tdefault:\n> +\t\t\tpush_to_stack(parents->item, &stack);\n> +\t\t\tbreak;\n> +\t\t}\n\nAnd if we have an enum, this switch() becomes more readable (the\n\"default\" here threw me off initially, because it is actually just\nlooking for \"-1\").\n\n> +>expect\n> +# ulimit is a bash builtin; we can rely on that in MinGW, but nowhere else\n> +test_expect_success MINGW '--contains works in a deep repo' '\n> +\tulimit -s 64\n\nIt would be nice to test this on Linux.\n\nCan we do something like:\n\n  test_lazy_prereq BASH 'bash --version'\n\n  test_expect_success BASH '--contains works in a deep repo' '\n\t... setup repo ...\n\tbash -c \"ulimit -s 64 && git tag --contains HEAD\" >actual &&\n\ttest_cmp expect actual\n  '\n\nAs a bonus, then our \"ulimit\" call does not pollute the environment of\nsubsequent tests.\n\n-Peff\n"},{"id":"239025","messageId":"alpine.DEB.1.00.1404171902010.14982@s15462909.onlinehome-server.info","threadId":"36422","inReplyTo":"20140416154653.GB4691@sigill.intra.peff.net","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2014-04-17T17:31:54Z","receivedAt":"2014-04-17T17:31:54Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Wed, 16 Apr 2014, Jeff King wrote:\n\n> On Wed, Apr 16, 2014 at 04:15:19PM +0200, Stepan Kasal wrote:\n> \n> > From: Jean-Jacques Lafay at Sat, 10 Nov 2012 18:36:10 +0100\n> > \n> > In large repos, the recursion implementation of contains(commit,\n> > commit_list) may result in a stack overflow. Replace the recursion\n> > with a loop to fix it.\n> > \n> > This problem is more apparent on Windows than on Linux, where the\n> > stack is more limited by default.\n> \n> I think this is a good thing to be doing, and it looks mostly good to\n> me. A few comments:\n> \n> > -static int contains_recurse(struct commit *candidate,\n> > +/*\n> > + * Test whether the candidate or one of its parents is contained in the list.\n> > + * Do not recurse to find out, though, but return -1 if inconclusive.\n> > + */\n> > +static int contains_test(struct commit *candidate,\n> >  \t\t\t    const struct commit_list *want)\n> \n> Can we turn this return value into\n> \n>   enum {\n> \tCONTAINS_UNKNOWN = -1,\n> \tCONTAINS_NO = 0,\n> \tCONTAINS_YES = 1,\n>   } contains_result;\n> \n> to make the code a little more self-documenting?\n\nGood idea!\n\n> [... detailed instructions what changes are implied by the enum ...]\n> \n> > +>expect\n> > +# ulimit is a bash builtin; we can rely on that in MinGW, but nowhere else\n> > +test_expect_success MINGW '--contains works in a deep repo' '\n> > +\tulimit -s 64\n> \n> It would be nice to test this on Linux.\n> \n> Can we do something like:\n> \n>   test_lazy_prereq BASH 'bash --version'\n> \n>   test_expect_success BASH '--contains works in a deep repo' '\n> \t... setup repo ...\n> \tbash -c \"ulimit -s 64 && git tag --contains HEAD\" >actual &&\n> \ttest_cmp expect actual\n>   '\n> \n> As a bonus, then our \"ulimit\" call does not pollute the environment of\n> subsequent tests.\n\nThat's a very good idea! We mulled it over a bit and did not come up with\nthis excellent solution.\n\nPlease see https://github.com/msysgit/git/c63d196 for the fixup, and\nhttps://github.com/msysgit/git/compare/tag-contains%5E...tag-contains for\nthe updated patch.\n\nThanks,\nDscho\n"},{"id":"239052","messageId":"20140417213238.GA14792@sigill.intra.peff.net","threadId":"36422","inReplyTo":"alpine.DEB.1.00.1404171902010.14982@s15462909.onlinehome-server.info","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-17T21:32:38Z","receivedAt":"2014-04-17T21:32:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 17, 2014 at 07:31:54PM +0200, Johannes Schindelin wrote:\n\n> > \tbash -c \"ulimit -s 64 && git tag --contains HEAD\" >actual &&\n> [...]\n> Please see https://github.com/msysgit/git/c63d196 for the fixup, and\n> https://github.com/msysgit/git/compare/tag-contains%5E...tag-contains for\n> the updated patch.\n\nI tried running the test on my Linux box, but it doesn't fail with the\nexisting recursive code. So I tried a few different stack sizes, like:\n\n  for i in `seq 1 64`; do\n    bash -c \"\n      ulimit -s $i &&\n      ../../git tag --contains HEAD ||\n      echo fail $i\"\n  done\n\nThe results are strangely non-deterministic, but with -O0, we generally\ndie reliably below about 60. With -O2, though, it's more like 43. We\ncan't go _too_ low here, though, as lots of things start breaking around\n32.\n\nIf we instead bump the size of the history to 2000 commits, then I\nreliably fail with a 64k stack (even with -O2, it needs around 80k).\n\nOf course those numbers are all black magic, and are going to vary based\non the system, the compiler, settings, etc. My system is 64-bit, and the\ncurrent code needs at least 3 pointers per recursive invocation. So\nwe're spending ~46K on those variables, not counting any calling\nconvention overhead (and presumably we at least need a function return\npointer there). So a 32-bit system might actually get by, as it would\nneed half as much.\n\nSo we can bump the depth further; probably 4000 is enough for any system\nto fail with a 64k stack. The deeper we make it, the longer it takes to\nrun the test, though. At 4000, my machine seems to take about 300ms to\nrun it. That's may be OK.\n\n-Peff\n"},{"id":"239053","messageId":"alpine.DEB.1.00.1404172347440.14982@s15462909.onlinehome-server.info","threadId":"36422","inReplyTo":"20140417213238.GA14792@sigill.intra.peff.net","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2014-04-17T21:52:56Z","receivedAt":"2014-04-17T21:52:56Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Thu, 17 Apr 2014, Jeff King wrote:\n\n> On Thu, Apr 17, 2014 at 07:31:54PM +0200, Johannes Schindelin wrote:\n> \n> > > \tbash -c \"ulimit -s 64 && git tag --contains HEAD\" >actual &&\n> > [...]\n> > Please see https://github.com/msysgit/git/c63d196 for the fixup, and\n> > https://github.com/msysgit/git/compare/tag-contains%5E...tag-contains for\n> > the updated patch.\n> \n> I tried running the test on my Linux box, but it doesn't fail with the\n> existing recursive code.\n\nI cannot recall how I came to choose 64, but I *think* I only tested on\nWindows, and I *think* I reduced the number of tags in order to make\nthings faster (Windows is *unbearably* slow with spawn-happy programs such\nas Git's tests -- literally every single line in a shell script tests the\npatience of this developer, running the complete test suite with 15\nparallel threads takes several hours, no kidding).\n\n> The results are strangely non-deterministic, but with -O0, we generally\n> die reliably below about 60. With -O2, though, it's more like 43. We\n> can't go _too_ low here, though, as lots of things start breaking around\n> 32.\n\nHow about using 40, then? I am more interested in reducing the runtime\nthan reducing the number of false negatives. The problem will be exercised\nenough on Windows, but not if the test suite becomes even slower than it\nalready is.\n\nCiao,\nJohannes\n"},{"id":"239055","messageId":"20140417215817.GA822@sigill.intra.peff.net","threadId":"36422","inReplyTo":"alpine.DEB.1.00.1404172347440.14982@s15462909.onlinehome-server.info","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-17T21:58:17Z","receivedAt":"2014-04-17T21:58:17Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 17, 2014 at 11:52:56PM +0200, Johannes Schindelin wrote:\n\n> > I tried running the test on my Linux box, but it doesn't fail with the\n> > existing recursive code.\n> \n> I cannot recall how I came to choose 64, but I *think* I only tested on\n> Windows, and I *think* I reduced the number of tags in order to make\n> things faster (Windows is *unbearably* slow with spawn-happy programs such\n> as Git's tests -- literally every single line in a shell script tests the\n> patience of this developer, running the complete test suite with 15\n> parallel threads takes several hours, no kidding).\n\nYeah, I figured speed had something to do with it. However, since you\nare using a bash loop to generate the input (and it should all be done\nas builtins in bash, I think), and fast-import to create the objects, I\ndon't think bumping it will actually increase your process count.\n\n> > The results are strangely non-deterministic, but with -O0, we generally\n> > die reliably below about 60. With -O2, though, it's more like 43. We\n> > can't go _too_ low here, though, as lots of things start breaking around\n> > 32.\n> \n> How about using 40, then? I am more interested in reducing the runtime\n> than reducing the number of false negatives. The problem will be exercised\n> enough on Windows, but not if the test suite becomes even slower than it\n> already is.\n\nI'm OK with doing that. My biggest concern is that it will cause false\npositives on systems that are hungrier for stack space, but we can\naddress that if it happens.\n\n-Peff\n"},{"id":"239411","messageId":"20140423075325.GA7268@camelia.ucw.cz","threadId":"36422","inReplyTo":"20140417215817.GA822@sigill.intra.peff.net","subject":"[PATCH v2] git tag --contains : avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-23T07:53:25Z","receivedAt":"2014-04-23T07:53:25Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n\nIn large repos, the recursion implementation of contains(commit,\ncommit_list) may result in a stack overflow. Replace the recursion with\na loop to fix it.\n\nThis problem is more apparent on Windows than on Linux, where the stack\nis more limited by default.\n\nSee also this thread on the msysGit list:\n\n\thttps://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion\n\n[jes: re-written to imitate the original recursion more closely]\n\nThomas Braun pointed out several documentation shortcomings.\n\nTests are run only if ulimit -s is available.  This means they cannot\nbe run on Windows.\n\nSigned-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\nTested-by: Stepan Kasal <kasal@ucw.cz>\n---\nHello,\nI have found out that \"ulimit -s\" does not work on Windows.\nAdding this as a prerequisite, we will skip the test there.\n\nOn Thu, Apr 17, 2014 at 05:32:38PM -0400, Jeff King wrote:\n> So we can bump the depth further; probably 4000 is enough for any system\n> to fail with a 64k stack. The deeper we make it, the longer it takes to\n> run the test, though. At 4000, my machine seems to take about 300ms to\n> run it. That's may be OK.\n\nConsequently, we can accept this proposal.\n\nStepan Kasal\n\n builtin/tag.c  | 90 ++++++++++++++++++++++++++++++++++++++++++++++++----------\n t/t7004-tag.sh | 23 +++++++++++++++\n 2 files changed, 98 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 6c7c6bd..f344002 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -80,11 +80,19 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \treturn 0;\n }\n \n-static int contains_recurse(struct commit *candidate,\n+enum contains_result {\n+\tCONTAINS_UNKNOWN = -1,\n+\tCONTAINS_NO = 0,\n+\tCONTAINS_YES = 1,\n+};\n+\n+/*\n+ * Test whether the candidate or one of its parents is contained in the list.\n+ * Do not recurse to find out, though, but return -1 if inconclusive.\n+ */\n+static enum contains_result contains_test(struct commit *candidate,\n \t\t\t    const struct commit_list *want)\n {\n-\tstruct commit_list *p;\n-\n \t/* was it previously marked as containing a want commit? */\n \tif (candidate->object.flags & TMP_MARK)\n \t\treturn 1;\n@@ -92,26 +100,78 @@ static int contains_recurse(struct commit *candidate,\n \tif (candidate->object.flags & UNINTERESTING)\n \t\treturn 0;\n \t/* or are we it? */\n-\tif (in_commit_list(want, candidate))\n+\tif (in_commit_list(want, candidate)) {\n+\t\tcandidate->object.flags |= TMP_MARK;\n \t\treturn 1;\n+\t}\n \n \tif (parse_commit(candidate) < 0)\n \t\treturn 0;\n \n-\t/* Otherwise recurse and mark ourselves for future traversals. */\n-\tfor (p = candidate->parents; p; p = p->next) {\n-\t\tif (contains_recurse(p->item, want)) {\n-\t\t\tcandidate->object.flags |= TMP_MARK;\n-\t\t\treturn 1;\n-\t\t}\n-\t}\n-\tcandidate->object.flags |= UNINTERESTING;\n-\treturn 0;\n+\treturn -1;\n }\n \n-static int contains(struct commit *candidate, const struct commit_list *want)\n+/*\n+ * Mimicking the real stack, this stack lives on the heap, avoiding stack\n+ * overflows.\n+ *\n+ * At each recursion step, the stack items points to the commits whose\n+ * ancestors are to be inspected.\n+ */\n+struct stack {\n+\tint nr, alloc;\n+\tstruct stack_entry {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *parents;\n+\t} *stack;\n+};\n+\n+static void push_to_stack(struct commit *candidate, struct stack *stack)\n+{\n+\tint index = stack->nr++;\n+\tALLOC_GROW(stack->stack, stack->nr, stack->alloc);\n+\tstack->stack[index].commit = candidate;\n+\tstack->stack[index].parents = candidate->parents;\n+}\n+\n+static enum contains_result contains(struct commit *candidate,\n+\t\tconst struct commit_list *want)\n {\n-\treturn contains_recurse(candidate, want);\n+\tstruct stack stack = { 0, 0, NULL };\n+\tint result = contains_test(candidate, want);\n+\n+\tif (result != CONTAINS_UNKNOWN)\n+\t\treturn result;\n+\n+\tpush_to_stack(candidate, &stack);\n+\twhile (stack.nr) {\n+\t\tstruct stack_entry *entry = &stack.stack[stack.nr - 1];\n+\t\tstruct commit *commit = entry->commit;\n+\t\tstruct commit_list *parents = entry->parents;\n+\n+\t\tif (!parents) {\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tstack.nr--;\n+\t\t}\n+\t\t/*\n+\t\t * If we just popped the stack, parents->item has been marked,\n+\t\t * therefore contains_test will return a meaningful 0 or 1.\n+\t\t */\n+\t\telse switch (contains_test(parents->item, want)) {\n+\t\tcase CONTAINS_YES:\n+\t\t\tcommit->object.flags |= TMP_MARK;\n+\t\t\tstack.nr--;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_NO:\n+\t\t\tentry->parents = parents->next;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_UNKNOWN:\n+\t\t\tpush_to_stack(parents->item, &stack);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tfree(stack.stack);\n+\treturn contains_test(candidate, want);\n }\n \n static void show_tag_lines(const unsigned char *sha1, int lines)\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex 143a8ea..db82f6d 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1423,4 +1423,27 @@ EOF\n \ttest_cmp expect actual\n '\n \n+ulimit_stack=\"ulimit -s 64\"\n+test_lazy_prereq ULIMIT 'bash -c \"'\"$ulimit_stack\"'\"'\n+\n+>expect\n+# we require bash and ulimit, this excludes Windows\n+test_expect_success ULIMIT '--contains works in a deep repo' '\n+\ti=1 &&\n+\twhile test $i -lt 4000\n+\tdo\n+\t\techo \"commit refs/heads/master\n+committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n+data <<EOF\n+commit #$i\n+EOF\"\n+\t\ttest $i = 1 && echo \"from refs/heads/master^0\"\n+\t\ti=$(($i + 1))\n+\tdone | git fast-import &&\n+\tgit checkout master &&\n+\tgit tag far-far-away HEAD^ &&\n+\tbash -c \"'\"$ulimit_stack\"' && git tag --contains HEAD >actual\" &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.9.2.msysgit.0.158.g49754fb\n"},{"id":"239439","messageId":"alpine.DEB.1.00.1404231627590.14982@s15462909.onlinehome-server.info","threadId":"36422","inReplyTo":"20140423075325.GA7268@camelia.ucw.cz","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2014-04-23T14:28:39Z","receivedAt":"2014-04-23T14:28:39Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 23 Apr 2014, Stepan Kasal wrote:\n\n> I have found out that \"ulimit -s\" does not work on Windows.\n> Adding this as a prerequisite, we will skip the test there.\n\nThe interdiff can be seen here:\n\n\thttps://github.com/msysgit/git/commit/c68e27d5\n\nCiao,\nJohannes\n"},{"id":"239444","messageId":"20140423154528.GB2291@camelia.ucw.cz","threadId":"36422","inReplyTo":"alpine.DEB.1.00.1404231627590.14982@s15462909.onlinehome-server.info","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-23T15:45:28Z","receivedAt":"2014-04-23T15:45:28Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"Hello,\n\nOn Wed, Apr 23, 2014 at 04:28:39PM +0200, Johannes Schindelin wrote:\n> The interdiff can be seen here:\n> \thttps://github.com/msysgit/git/commit/c68e27d5\n\nnot exatly, is also changes the number of commits in the \"deep repo\"\nfrom 1000 to 4000, as peff proposed.\n\nStepan\n"},{"id":"239464","messageId":"xmqqeh0nzwq9.fsf@gitster.dls.corp.google.com","threadId":"36422","inReplyTo":"20140423075325.GA7268@camelia.ucw.cz","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-23T19:12:14Z","receivedAt":"2014-04-23T19:12:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Stepan Kasal <kasal@ucw.cz> writes:\n\n[Administrivia: please refrain from using Mail-Followup-To to\ndeflect an attempt to directly respond to you; it will waste time of\nother people while it may be saving your time].\n\n> From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n>\n> In large repos, the recursion implementation of contains(commit,\n> commit_list) may result in a stack overflow. Replace the recursion with\n> a loop to fix it.\n>\n> This problem is more apparent on Windows than on Linux, where the stack\n> is more limited by default.\n>\n> See also this thread on the msysGit list:\n>\n> \thttps://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion\n>\n> [jes: re-written to imitate the original recursion more closely]\n>\n> Thomas Braun pointed out several documentation shortcomings.\n>\n> Tests are run only if ulimit -s is available.  This means they cannot\n> be run on Windows.\n>\n> Signed-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> Tested-by: Stepan Kasal <kasal@ucw.cz>\n\nThanks.\n\n> diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\n> index 143a8ea..db82f6d 100755\n> --- a/t/t7004-tag.sh\n> +++ b/t/t7004-tag.sh\n> @@ -1423,4 +1423,27 @@ EOF\n>  \ttest_cmp expect actual\n>  '\n>  \n> +ulimit_stack=\"ulimit -s 64\"\n> +test_lazy_prereq ULIMIT 'bash -c \"'\"$ulimit_stack\"'\"'\n\nWith this implementaion, ULIMIT implies bash, and we use bash that\nappears on user's PATH that may not be the one the user chose to run\ngit with.  Can't we fix both of them by using $SHELL_PATH?\n\n> +>expect\n\nMove this inside test_expect_success?\n\n> +# we require bash and ulimit, this excludes Windows\n> +test_expect_success ULIMIT '--contains works in a deep repo' '\n> +\ti=1 &&\n> +\twhile test $i -lt 4000\n> +\tdo\n> +\t\techo \"commit refs/heads/master\n> +committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n> +data <<EOF\n> +commit #$i\n> +EOF\"\n> +\t\ttest $i = 1 && echo \"from refs/heads/master^0\"\n> +\t\ti=$(($i + 1))\n> +\tdone | git fast-import &&\n> +\tgit checkout master &&\n> +\tgit tag far-far-away HEAD^ &&\n> +\tbash -c \"'\"$ulimit_stack\"' && git tag --contains HEAD >actual\" &&\n\nSo this runs a separate \"bash\", the only thing which does is to run\na small script that gives a small stack to itself and exit, and then\nrun \"git tag\" in the original shell?\n\nAhh, no, I am mis-pairing the quotes.\n\nHow about doing it along this line instead?\n\n\trun_with_limited_stack () {\n\t\t\"$SHELL_PATH\" -c \"ulimit -s 64 && $*\"\n\t}\n\n\ttest_lazy_prereq ULIMIT \"run_with_limited_stack true\"\n\n\ttest_expect_success ULIMIT '...' '\n        \t>expect &&\n\t\ti=1 &&\n                ...\n                done | git-fast-import &&\n                git tag far-far-away HEAD^ &&\n                run_with_limited_stack \"git tag --contains HEAD\" >actual &&\n\t\ttest_cmp expect actual\n\t'\n"},{"id":"239465","messageId":"20140423191628.GA20596@sigill.intra.peff.net","threadId":"36422","inReplyTo":"xmqqeh0nzwq9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-23T19:16:28Z","receivedAt":"2014-04-23T19:16:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 23, 2014 at 12:12:14PM -0700, Junio C Hamano wrote:\n\n> > +ulimit_stack=\"ulimit -s 64\"\n> > +test_lazy_prereq ULIMIT 'bash -c \"'\"$ulimit_stack\"'\"'\n> \n> With this implementaion, ULIMIT implies bash, and we use bash that\n> appears on user's PATH that may not be the one the user chose to run\n> git with.  Can't we fix both of them by using $SHELL_PATH?\n\nI don't think so. The point is that we _must_ use bash here, not any\nPOSIX shell. So my $SHELL_PATH is /bin/sh, which is dash, and would not\nrun the test.\n\nWe want to run \"some bash\" if we can. We may pick a bash on the user's\nPATH that is not what they put into $SHELL_PATH, but that should be\nrelatively rare. And the consequence is that either that bash works fine\nand we run the test, or it does not, and we skip the test.\n\n> How about doing it along this line instead?\n> \n> \trun_with_limited_stack () {\n> \t\t\"$SHELL_PATH\" -c \"ulimit -s 64 && $*\"\n> \t}\n> \n> \ttest_lazy_prereq ULIMIT \"run_with_limited_stack true\"\n\nThat's a much more direct test. I like it (aside from the $SHELL_PATH\nthing as described above).\n\n-Peff\n"},{"id":"239466","messageId":"20140423191749.GB20596@sigill.intra.peff.net","threadId":"36422","inReplyTo":"20140423075325.GA7268@camelia.ucw.cz","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-23T19:17:50Z","receivedAt":"2014-04-23T19:17:50Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 23, 2014 at 09:53:25AM +0200, Stepan Kasal wrote:\n\n> I have found out that \"ulimit -s\" does not work on Windows.\n> Adding this as a prerequisite, we will skip the test there.\n\nI found this bit weird, as the test originated on Windows. Did it never\nactually cause a failure there (i.e., the \"ulimit -s\" doesn't do\nanything)? Or does \"ulimit\" fail?\n\n-Peff\n"},{"id":"239477","messageId":"20140423195957.GA3187@camelia.ucw.cz","threadId":"36422","inReplyTo":"xmqqeh0nzwq9.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-23T19:59:57Z","receivedAt":"2014-04-23T19:59:57Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"Hi,\n\nOn Wed, Apr 23, 2014 at 12:12:14PM -0700, Junio C Hamano wrote:\n> [Administrivia: please refrain from using Mail-Followup-To to\n> deflect an attempt to directly respond to you;\n\nthanks a lot for telling me.\nActually, this was a mistake: I added git to the list of discussion\nlists, without realizing the consequences.\nI'm glad to have separate copies of \"my threads\" that do not fall\nto the git-list folder.\n\n> > +>expect\n> Move this inside test_expect_success?\n\nOf course.  Had this in mind, then forgot.\n\n> So this runs a separate \"bash\", [...]\n> run \"git tag\" in the original shell?\n> \n> Ahh, no, I am mis-pairing the quotes.\n\nPoint taken.  I admire how nicely you explained that!\n\n> \trun_with_limited_stack () {\n> \t\t\"$SHELL_PATH\" -c \"ulimit -s 64 && $*\"\n> \t}\n\nElegant. But I agree with Peff that we shall run \"a bash\" instead.\n\nI'll mail an updated patch tomorrow.\n\nStepan\n"},{"id":"239489","messageId":"xmqqk3afydq2.fsf@gitster.dls.corp.google.com","threadId":"36422","inReplyTo":"20140423191628.GA20596@sigill.intra.peff.net","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-23T20:48:05Z","receivedAt":"2014-04-23T20:48:05Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Apr 23, 2014 at 12:12:14PM -0700, Junio C Hamano wrote:\n>\n>> > +ulimit_stack=\"ulimit -s 64\"\n>> > +test_lazy_prereq ULIMIT 'bash -c \"'\"$ulimit_stack\"'\"'\n>> \n>> With this implementaion, ULIMIT implies bash, and we use bash that\n>> appears on user's PATH that may not be the one the user chose to run\n>> git with.  Can't we fix both of them by using $SHELL_PATH?\n>\n> I don't think so. The point is that we _must_ use bash here, not any\n> POSIX shell.\n\nSorry, but I do not understand.  Isn't what you want \"any POSIX\nshell with 'ulimit -s 64' supported\"?\n\n    $ dash -c 'ulimit -s && ulimit -s 64 && ulimit -s'\n    8192\n    64\n\n> We want to run \"some bash\" if we can. We may pick a bash on the user's\n> PATH that is not what they put into $SHELL_PATH, but that should be\n> relatively rare. And the consequence is that either that bash works fine\n> and we run the test, or it does not, and we skip the test.\n>\n>> How about doing it along this line instead?\n>> \n>> \trun_with_limited_stack () {\n>> \t\t\"$SHELL_PATH\" -c \"ulimit -s 64 && $*\"\n>> \t}\n>> \n>> \ttest_lazy_prereq ULIMIT \"run_with_limited_stack true\"\n>\n> That's a much more direct test. I like it (aside from the $SHELL_PATH\n> thing as described above).\n\nStill puzzled.\n"},{"id":"239490","messageId":"20140423205533.GA20582@sigill.intra.peff.net","threadId":"36422","inReplyTo":"xmqqk3afydq2.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-23T20:55:33Z","receivedAt":"2014-04-23T20:55:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Apr 23, 2014 at 01:48:05PM -0700, Junio C Hamano wrote:\n\n> > I don't think so. The point is that we _must_ use bash here, not any\n> > POSIX shell.\n> \n> Sorry, but I do not understand.  Isn't what you want \"any POSIX\n> shell with 'ulimit -s 64' supported\"?\n\nSure, that would be fine, but the original patch which started this\nthread claimed that bash was required. I had assumed that to be true,\nbut it seems like it's not:\n\n>     $ dash -c 'ulimit -s && ulimit -s 64 && ulimit -s'\n>     8192\n>     64\n\nIf we are just using the same shell we are already running, then why\ninvoke it by name in the first place? IOW, why not:\n\n  run_with_limited_stack () {\n\t(ulimit -s 64 && \"$@\")\n  }\n\n-Peff\n"},{"id":"239492","messageId":"xmqqfvl3ycwk.fsf@gitster.dls.corp.google.com","threadId":"36422","inReplyTo":"20140423205533.GA20582@sigill.intra.peff.net","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-04-23T21:05:47Z","receivedAt":"2014-04-23T21:05:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Apr 23, 2014 at 01:48:05PM -0700, Junio C Hamano wrote:\n>\n>> > I don't think so. The point is that we _must_ use bash here, not any\n>> > POSIX shell.\n>> \n>> Sorry, but I do not understand.  Isn't what you want \"any POSIX\n>> shell with 'ulimit -s 64' supported\"?\n>\n> Sure, that would be fine, but the original patch which started this\n> thread claimed that bash was required. I had assumed that to be true,\n> but it seems like it's not:\n>\n>>     $ dash -c 'ulimit -s && ulimit -s 64 && ulimit -s'\n>>     8192\n>>     64\n>\n> If we are just using the same shell we are already running, then why\n> invoke it by name in the first place? IOW, why not:\n>\n>   run_with_limited_stack () {\n> \t(ulimit -s 64 && \"$@\")\n>   }\n\nThat is certainly more preferrable than an explicit \"run this piece\nwith $SHELL_PATH\".\n\nI think the choice between \"Any bash that is on user's PATH\" vs \"The\nshell the user told us to use when working with Git\" is a trade-off\nbetween\n\n - those who choose a shell that does not support \"ulimit -s\" to\n   work with Git (which is fine, because our scripted Porcelains\n   would not have any need for that); for these people, this test\n   would be skipped unnecessarily if we insist on SHELL_PATH; and\n\n - those who run on a box without any bash on their PATH, chose a\n   shell that is not bash but does support \"ulimit -s\" as their\n   SHELL_PATH to build Git with; for these people, this test would\n   be skipped unnecessarily if we insist on \"bash\".\n\nand I do not think of a good reason to favor one over the other.\n\nIf I have to pick, I'd take your \"don't name any shell, and let the\ncurrent one run it\" approach, solely for the simplicity of the\nsolution (it ends up favoring the latter class of people as a\nside-effect, though).\n"},{"id":"239494","messageId":"alpine.DEB.1.00.1404232313370.14982@s15462909.onlinehome-server.info","threadId":"36422","inReplyTo":"20140423191749.GB20596@sigill.intra.peff.net","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2014-04-23T21:14:42Z","receivedAt":"2014-04-23T21:14:42Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Wed, 23 Apr 2014, Jeff King wrote:\n\n> On Wed, Apr 23, 2014 at 09:53:25AM +0200, Stepan Kasal wrote:\n> \n> > I have found out that \"ulimit -s\" does not work on Windows.  Adding\n> > this as a prerequisite, we will skip the test there.\n> \n> I found this bit weird, as the test originated on Windows. Did it never\n> actually cause a failure there (i.e., the \"ulimit -s\" doesn't do\n> anything)? Or does \"ulimit\" fail?\n\nI must have forgotten to test on Windows. For performance reasons (you\nknow that I only have a Git time budget of about 15min/day), I developed\nthe test and the patch on Linux.\n\nCiao,\nJohannes\n"},{"id":"239561","messageId":"20140424122029.GA8168@camelia.ucw.cz","threadId":"36422","inReplyTo":"xmqqfvl3ycwk.fsf@gitster.dls.corp.google.com","subject":"Re: [PATCH v2] git tag --contains : avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-24T12:20:29Z","receivedAt":"2014-04-24T12:20:29Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"Thanks for all suggestions and explanations.\nThe diff against PATCH v2 is below, PATCH v3 follows.\n\nHave a nice day,\n\tStepan\n\nSubject: [PATCH] fixup! git tag --contains : avoid stack overflow\n\n---\n t/t7004-tag.sh | 11 +++++++----\n 1 file changed, 7 insertions(+), 4 deletions(-)\n\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex db82f6d..a911df0 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1423,12 +1423,15 @@ EOF\n \ttest_cmp expect actual\n '\n \n-ulimit_stack=\"ulimit -s 64\"\n-test_lazy_prereq ULIMIT 'bash -c \"'\"$ulimit_stack\"'\"'\n+run_with_limited_stack () {\n+\t(ulimit -s 64 && \"$@\")\n+}\n+\n+test_lazy_prereq ULIMIT 'run_with_limited_stack true'\n \n->expect\n # we require bash and ulimit, this excludes Windows\n test_expect_success ULIMIT '--contains works in a deep repo' '\n+\t>expect &&\n \ti=1 &&\n \twhile test $i -lt 4000\n \tdo\n@@ -1442,7 +1445,7 @@ EOF\"\n \tdone | git fast-import &&\n \tgit checkout master &&\n \tgit tag far-far-away HEAD^ &&\n-\tbash -c \"'\"$ulimit_stack\"' && git tag --contains HEAD >actual\" &&\n+\trun_with_limited_stack git tag --contains HEAD >actual &&\n \ttest_cmp expect actual\n '\n \n-- \n1.9.0.msysgit.0.119.g722efef\n"},{"id":"239562","messageId":"20140424122439.GB8168@camelia.ucw.cz","threadId":"36422","inReplyTo":"20140424122029.GA8168@camelia.ucw.cz","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Stepan Kasal","fromEmail":"kasal@ucw.cz","sentAt":"2014-04-24T12:24:39Z","receivedAt":"2014-04-24T12:24:39Z","isPatch":true,"sender":{"key":"kasal@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/1481596?v=4"},"body":"From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n\nIn large repos, the recursion implementation of contains(commit,\ncommit_list) may result in a stack overflow. Replace the recursion with\na loop to fix it.\n\nThis problem is more apparent on Windows than on Linux, where the stack\nis more limited by default.\n\nSee also this thread on the msysGit list:\n\n\thttps://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion\n\n[jes: re-written to imitate the original recursion more closely]\n\nThomas Braun pointed out several documentation shortcomings.\n\nTests are run only if ulimit -s is available.  This means they cannot\nbe run on Windows.\n\nSigned-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\nTested-by: Stepan Kasal <kasal@ucw.cz>\n---\n\nOops, actually there is one more omission, the comments needs to be\nfixed:\n   -# we require bash and ulimit, this excludes Windows\n   +# we require ulimit, this excludes Windows\n\nI forgot to add this to the preceding diff, but the final version\nhere has this fixed.\n\n builtin/tag.c  | 90 ++++++++++++++++++++++++++++++++++++++++++++++++----------\n t/t7004-tag.sh | 26 +++++++++++++++++\n 2 files changed, 101 insertions(+), 15 deletions(-)\n\ndiff --git a/builtin/tag.c b/builtin/tag.c\nindex 6c7c6bd..f344002 100644\n--- a/builtin/tag.c\n+++ b/builtin/tag.c\n@@ -80,11 +80,19 @@ static int in_commit_list(const struct commit_list *want, struct commit *c)\n \treturn 0;\n }\n \n-static int contains_recurse(struct commit *candidate,\n+enum contains_result {\n+\tCONTAINS_UNKNOWN = -1,\n+\tCONTAINS_NO = 0,\n+\tCONTAINS_YES = 1,\n+};\n+\n+/*\n+ * Test whether the candidate or one of its parents is contained in the list.\n+ * Do not recurse to find out, though, but return -1 if inconclusive.\n+ */\n+static enum contains_result contains_test(struct commit *candidate,\n \t\t\t    const struct commit_list *want)\n {\n-\tstruct commit_list *p;\n-\n \t/* was it previously marked as containing a want commit? */\n \tif (candidate->object.flags & TMP_MARK)\n \t\treturn 1;\n@@ -92,26 +100,78 @@ static int contains_recurse(struct commit *candidate,\n \tif (candidate->object.flags & UNINTERESTING)\n \t\treturn 0;\n \t/* or are we it? */\n-\tif (in_commit_list(want, candidate))\n+\tif (in_commit_list(want, candidate)) {\n+\t\tcandidate->object.flags |= TMP_MARK;\n \t\treturn 1;\n+\t}\n \n \tif (parse_commit(candidate) < 0)\n \t\treturn 0;\n \n-\t/* Otherwise recurse and mark ourselves for future traversals. */\n-\tfor (p = candidate->parents; p; p = p->next) {\n-\t\tif (contains_recurse(p->item, want)) {\n-\t\t\tcandidate->object.flags |= TMP_MARK;\n-\t\t\treturn 1;\n-\t\t}\n-\t}\n-\tcandidate->object.flags |= UNINTERESTING;\n-\treturn 0;\n+\treturn -1;\n }\n \n-static int contains(struct commit *candidate, const struct commit_list *want)\n+/*\n+ * Mimicking the real stack, this stack lives on the heap, avoiding stack\n+ * overflows.\n+ *\n+ * At each recursion step, the stack items points to the commits whose\n+ * ancestors are to be inspected.\n+ */\n+struct stack {\n+\tint nr, alloc;\n+\tstruct stack_entry {\n+\t\tstruct commit *commit;\n+\t\tstruct commit_list *parents;\n+\t} *stack;\n+};\n+\n+static void push_to_stack(struct commit *candidate, struct stack *stack)\n+{\n+\tint index = stack->nr++;\n+\tALLOC_GROW(stack->stack, stack->nr, stack->alloc);\n+\tstack->stack[index].commit = candidate;\n+\tstack->stack[index].parents = candidate->parents;\n+}\n+\n+static enum contains_result contains(struct commit *candidate,\n+\t\tconst struct commit_list *want)\n {\n-\treturn contains_recurse(candidate, want);\n+\tstruct stack stack = { 0, 0, NULL };\n+\tint result = contains_test(candidate, want);\n+\n+\tif (result != CONTAINS_UNKNOWN)\n+\t\treturn result;\n+\n+\tpush_to_stack(candidate, &stack);\n+\twhile (stack.nr) {\n+\t\tstruct stack_entry *entry = &stack.stack[stack.nr - 1];\n+\t\tstruct commit *commit = entry->commit;\n+\t\tstruct commit_list *parents = entry->parents;\n+\n+\t\tif (!parents) {\n+\t\t\tcommit->object.flags |= UNINTERESTING;\n+\t\t\tstack.nr--;\n+\t\t}\n+\t\t/*\n+\t\t * If we just popped the stack, parents->item has been marked,\n+\t\t * therefore contains_test will return a meaningful 0 or 1.\n+\t\t */\n+\t\telse switch (contains_test(parents->item, want)) {\n+\t\tcase CONTAINS_YES:\n+\t\t\tcommit->object.flags |= TMP_MARK;\n+\t\t\tstack.nr--;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_NO:\n+\t\t\tentry->parents = parents->next;\n+\t\t\tbreak;\n+\t\tcase CONTAINS_UNKNOWN:\n+\t\t\tpush_to_stack(parents->item, &stack);\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\tfree(stack.stack);\n+\treturn contains_test(candidate, want);\n }\n \n static void show_tag_lines(const unsigned char *sha1, int lines)\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex 143a8ea..a911df0 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1423,4 +1423,30 @@ EOF\n \ttest_cmp expect actual\n '\n \n+run_with_limited_stack () {\n+\t(ulimit -s 64 && \"$@\")\n+}\n+\n+test_lazy_prereq ULIMIT 'run_with_limited_stack true'\n+\n+# we require ulimit, this excludes Windows\n+test_expect_success ULIMIT '--contains works in a deep repo' '\n+\t>expect &&\n+\ti=1 &&\n+\twhile test $i -lt 4000\n+\tdo\n+\t\techo \"commit refs/heads/master\n+committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n+data <<EOF\n+commit #$i\n+EOF\"\n+\t\ttest $i = 1 && echo \"from refs/heads/master^0\"\n+\t\ti=$(($i + 1))\n+\tdone | git fast-import &&\n+\tgit checkout master &&\n+\tgit tag far-far-away HEAD^ &&\n+\trun_with_limited_stack git tag --contains HEAD >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n1.9.0.msysgit.0.119.g722efef\n"},{"id":"239629","messageId":"20140425055428.GA25337@sigill.intra.peff.net","threadId":"36422","inReplyTo":"20140424122439.GB8168@camelia.ucw.cz","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-04-25T05:54:28Z","receivedAt":"2014-04-25T05:54:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Apr 24, 2014 at 02:24:39PM +0200, Stepan Kasal wrote:\n\n> From: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n> \n> In large repos, the recursion implementation of contains(commit,\n> commit_list) may result in a stack overflow. Replace the recursion with\n> a loop to fix it.\n> \n> This problem is more apparent on Windows than on Linux, where the stack\n> is more limited by default.\n> \n> See also this thread on the msysGit list:\n> \n> \thttps://groups.google.com/d/topic/msysgit/FqT6boJrb2g/discussion\n> \n> [jes: re-written to imitate the original recursion more closely]\n> \n> Thomas Braun pointed out several documentation shortcomings.\n> \n> Tests are run only if ulimit -s is available.  This means they cannot\n> be run on Windows.\n> \n> Signed-off-by: Jean-Jacques Lafay <jeanjacques.lafay@gmail.com>\n> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n> Tested-by: Stepan Kasal <kasal@ucw.cz>\n\nThanks, this version looks good to me.\n\n-Peff\n"},{"id":"249700","messageId":"871tr688a4.fsf@igel.home","threadId":"36422","inReplyTo":"20140424122439.GB8168@camelia.ucw.cz","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Andreas Schwab","fromEmail":"schwab@linux-m68k.org","sentAt":"2014-09-20T18:18:59Z","receivedAt":"2014-09-20T18:18:59Z","isPatch":true,"sender":{"key":"schwab@linux-m68k.org","avatar":"https://avatars.githubusercontent.com/u/2175493?v=4"},"body":"Stepan Kasal <kasal@ucw.cz> writes:\n\n> diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\n> index 143a8ea..a911df0 100755\n> --- a/t/t7004-tag.sh\n> +++ b/t/t7004-tag.sh\n> @@ -1423,4 +1423,30 @@ EOF\n>  \ttest_cmp expect actual\n>  '\n>  \n> +run_with_limited_stack () {\n> +\t(ulimit -s 64 && \"$@\")\n> +}\n\nThat is way too small.\n\nhttps://build.opensuse.org/package/live_build_log/openSUSE:Factory:PowerPC/git/standard/ppc64le\n\n[  492s] not ok 136 - --contains works in a deep repo\n[  492s] ok 11 - log using absolute path names\n[  492s] #      \n[  492s] #              >expect &&\n[  492s] #              i=1 &&\n[  492s] #              while test $i -lt 4000\n[  492s] #              do\n[  492s] #                      echo \"commit refs/heads/master\n[  492s] #      committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n[  492s] #      data <<EOF\n[  492s] #      commit #$i\n[  492s] #      EOF\"\n[  492s] #                      test $i = 1 && echo \"from refs/heads/master^0\"\n[  492s] #                      i=$(($i + 1))\n[  492s] #              done | git fast-import &&\n[  492s] #              git checkout master &&\n[  492s] #              git tag far-far-away HEAD^ &&\n[  492s] #              run_with_limited_stack git tag --contains HEAD >actual &&\n[  492s] #              test_cmp expect actual\n[  492s] #      \n[  492s] # failed 1 among 136 test(s)\n[  492s] 1..136\n[  492s] Makefile:44: recipe for target 't7004-tag.sh' failed\n[  492s] make[2]: *** [t7004-tag.sh] Error 1\n\nAndreas.\n\n-- \nAndreas Schwab, schwab@linux-m68k.org\nGPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5\n\"And now for something completely different.\"\n"},{"id":"249794","messageId":"20140923160552.GA20624@peff.net","threadId":"36422","inReplyTo":"871tr688a4.fsf@igel.home","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-09-23T16:05:52Z","receivedAt":"2014-09-23T16:05:52Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Sep 20, 2014 at 08:18:59PM +0200, Andreas Schwab wrote:\n\n> Stepan Kasal <kasal@ucw.cz> writes:\n> \n> > diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\n> > index 143a8ea..a911df0 100755\n> > --- a/t/t7004-tag.sh\n> > +++ b/t/t7004-tag.sh\n> > @@ -1423,4 +1423,30 @@ EOF\n> >  \ttest_cmp expect actual\n> >  '\n> >  \n> > +run_with_limited_stack () {\n> > +\t(ulimit -s 64 && \"$@\")\n> > +}\n> \n> That is way too small.\n> \n> https://build.opensuse.org/package/live_build_log/openSUSE:Factory:PowerPC/git/standard/ppc64le\n\nThanks for the report. I'd be OK with just giving up and dropping this\ntest as too flaky and system-specific to be worth the trouble.\n\nBut if we do want to keep it, does bumping it to 128 (and bumping the\n4000 to 8000 in the test below it) work?\n\n-Peff\n"},{"id":"249817","messageId":"87wq8u3t4l.fsf@igel.home","threadId":"36422","inReplyTo":"20140923160552.GA20624@peff.net","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Andreas Schwab","fromEmail":"schwab@linux-m68k.org","sentAt":"2014-09-23T21:48:58Z","receivedAt":"2014-09-23T21:48:58Z","isPatch":true,"sender":{"key":"schwab@linux-m68k.org","avatar":"https://avatars.githubusercontent.com/u/2175493?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> But if we do want to keep it, does bumping it to 128 (and bumping the\n> 4000 to 8000 in the test below it) work?\n\nIt works for all architectures supported by the openSUSE build service.\n\nhttps://build.opensuse.org/package/show/home:AndreasSchwab:f/git\n\nAndreas.\n\n-- \nAndreas Schwab, schwab@linux-m68k.org\nGPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5\n\"And now for something completely different.\"\n"},{"id":"249819","messageId":"xmqqk34ugdtm.fsf@gitster.dls.corp.google.com","threadId":"36422","inReplyTo":"87wq8u3t4l.fsf@igel.home","subject":"Re: [PATCH v3] git tag --contains: avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-09-23T22:41:09Z","receivedAt":"2014-09-23T22:41:09Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Andreas Schwab <schwab@linux-m68k.org> writes:\n\n> Jeff King <peff@peff.net> writes:\n>\n>> But if we do want to keep it, does bumping it to 128 (and bumping the\n>> 4000 to 8000 in the test below it) work?\n>\n> It works for all architectures supported by the openSUSE build service.\n>\n> https://build.opensuse.org/package/show/home:AndreasSchwab:f/git\n>\n> Andreas.\n\nSo this on top of cbc60b67 (git tag --contains: avoid stack\noverflow, 2014-04-24) and merge it to maint and upwards?\n\n t/t7004-tag.sh | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex e4ab0f5..c564197 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1424,7 +1424,7 @@ EOF\n '\n \n run_with_limited_stack () {\n-\t(ulimit -s 64 && \"$@\")\n+\t(ulimit -s 128 && \"$@\")\n }\n \n test_lazy_prereq ULIMIT 'run_with_limited_stack true'\n@@ -1433,7 +1433,7 @@ test_lazy_prereq ULIMIT 'run_with_limited_stack true'\n test_expect_success ULIMIT '--contains works in a deep repo' '\n \t>expect &&\n \ti=1 &&\n-\twhile test $i -lt 4000\n+\twhile test $i -lt 8000\n \tdo\n \t\techo \"commit refs/heads/master\n committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200\n"}]}