{"thread":{"id":"46684","subject":"[PATCH] name-rev: change ULONG_MAX to TIME_MAX","startedAt":"2017-08-30T09:46:28Z","lastAt":"2017-09-11T18:08:31Z","messageCount":14,"participants":["Michael J Gruber","Johannes Schindelin","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"327393","messageId":"ef9aebb63227c36b8b72a65240a416a0271cc618.1504086318.git.git@grubix.eu","threadId":"46684","inReplyTo":null,"subject":"[PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-08-30T09:46:06Z","receivedAt":"2017-08-30T09:46:28Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Earlier, dddbad728c (\"timestamp_t: a new data type for timestamps\",\n2017-04-26) changed several types to timestamp_t.\n\n5589e87fd8 (\"name-rev: change a \"long\" variable to timestamp_t\",\n2017-05-20) cleaned up a missed variable, but both missed a _MAX\nconstant.\n\nChange the remaining constant to the one appropriate for the current\ntype\n\nSigned-off-by: Michael J Gruber <git@grubix.eu>\n---\n builtin/name-rev.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/name-rev.c b/builtin/name-rev.c\nindex c41ea7c2a6..598da6c8bc 100644\n--- a/builtin/name-rev.c\n+++ b/builtin/name-rev.c\n@@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo\n \t\tstruct commit *commit = (struct commit *)o;\n \t\tint from_tag = starts_with(path, \"refs/tags/\");\n \n-\t\tif (taggerdate == ULONG_MAX)\n+\t\tif (taggerdate == TIME_MAX)\n \t\t\ttaggerdate = ((struct commit *)o)->date;\n \t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n \t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327465","messageId":"alpine.DEB.2.21.1.1708302223020.7424@virtualbox","threadId":"46684","inReplyTo":"ef9aebb63227c36b8b72a65240a416a0271cc618.1504086318.git.git@grubix.eu","subject":"Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-08-30T20:23:21Z","receivedAt":"2017-08-30T20:23:35Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Michael,\n\nOn Wed, 30 Aug 2017, Michael J Gruber wrote:\n\n> Earlier, dddbad728c (\"timestamp_t: a new data type for timestamps\",\n> 2017-04-26) changed several types to timestamp_t.\n> \n> 5589e87fd8 (\"name-rev: change a \"long\" variable to timestamp_t\",\n> 2017-05-20) cleaned up a missed variable, but both missed a _MAX\n> constant.\n> \n> Change the remaining constant to the one appropriate for the current\n> type\n> \n> Signed-off-by: Michael J Gruber <git@grubix.eu>\n\nGood catch!\n\nACK,\nDscho\n"},{"id":"327629","messageId":"xmqqbmmo8pp6.fsf@gitster.mtv.corp.google.com","threadId":"46684","inReplyTo":"ef9aebb63227c36b8b72a65240a416a0271cc618.1504086318.git.git@grubix.eu","subject":"Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-09-06T03:35:01Z","receivedAt":"2017-09-06T03:35:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael J Gruber <git@grubix.eu> writes:\n\n> Earlier, dddbad728c (\"timestamp_t: a new data type for timestamps\",\n> 2017-04-26) changed several types to timestamp_t.\n>\n> 5589e87fd8 (\"name-rev: change a \"long\" variable to timestamp_t\",\n> 2017-05-20) cleaned up a missed variable, but both missed a _MAX\n> constant.\n>\n> Change the remaining constant to the one appropriate for the current\n> type\n>\n> Signed-off-by: Michael J Gruber <git@grubix.eu>\n> ---\n\nThanks.\n\nI think this (and the earlier 5589e8) was caused by an unnoticed\nsemantic conflict at 78089b71 (\"Merge branch 'jc/name-rev-lw-tag'\",\n2017-05-30).  Merging is sometimes hard ;-)\n\nWill queue.\n\n>  builtin/name-rev.c | 2 +-\n>  1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n> index c41ea7c2a6..598da6c8bc 100644\n> --- a/builtin/name-rev.c\n> +++ b/builtin/name-rev.c\n> @@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo\n>  \t\tstruct commit *commit = (struct commit *)o;\n>  \t\tint from_tag = starts_with(path, \"refs/tags/\");\n>  \n> -\t\tif (taggerdate == ULONG_MAX)\n> +\t\tif (taggerdate == TIME_MAX)\n>  \t\t\ttaggerdate = ((struct commit *)o)->date;\n>  \t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n>  \t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n"},{"id":"327644","messageId":"6a4cbbee-ffc6-739b-d649-079ba01439ca@grubix.eu","threadId":"46684","inReplyTo":"xmqqbmmo8pp6.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Michael J Gruber","fromEmail":"michael@grubix.eu","sentAt":"2017-09-06T11:59:31Z","receivedAt":"2017-09-06T11:59:45Z","isPatch":true,"sender":{"key":"michael@grubix.eu","avatar":null},"body":"Junio C Hamano venit, vidit, dixit 06.09.2017 05:35:\n> Michael J Gruber <git@grubix.eu> writes:\n> \n>> Earlier, dddbad728c (\"timestamp_t: a new data type for timestamps\",\n>> 2017-04-26) changed several types to timestamp_t.\n>>\n>> 5589e87fd8 (\"name-rev: change a \"long\" variable to timestamp_t\",\n>> 2017-05-20) cleaned up a missed variable, but both missed a _MAX\n>> constant.\n>>\n>> Change the remaining constant to the one appropriate for the current\n>> type\n>>\n>> Signed-off-by: Michael J Gruber <git@grubix.eu>\n>> ---\n> \n> Thanks.\n> \n> I think this (and the earlier 5589e8) was caused by an unnoticed\n> semantic conflict at 78089b71 (\"Merge branch 'jc/name-rev-lw-tag'\",\n> 2017-05-30).  Merging is sometimes hard ;-)\n\nSimple merges and semi-simple merges...\n\nBTW, there's more fallout from those name-rev changes: In connection\nwith that other thread about surprising describe results for emacs.git I\nnoticed that I can easily get \"git name-rev --stdin\" to segfault there.\nAs easy as\n\necho bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin\n\nfor example.\n\nThat's unfortunate for the use-case of name-rev to amend git log output.\n\nThe reason seems to be that with \"--stdin\" or \"--all\", \"name-rev\" walks\nand names all commits before beginning to use that those names for even\na single commit as above.\n\nThat segfault bisects to the logic changing commit in\njc/name-rev-lw-tag, but I think the changed logic simply leads to more\nxmallocs() the segfault sooner now. Or something that I dind't spot even\nafter a few hours.\n\nOn the other hand, nearly every time that I try to understand describe\nor name-rev I want get rid of insert_commit_by_date() and the like and\nreplace this by generations, and maybe a simple rev-walk (per ref)...\n\n> Will queue.\n> \n>>  builtin/name-rev.c | 2 +-\n>>  1 file changed, 1 insertion(+), 1 deletion(-)\n>>\n>> diff --git a/builtin/name-rev.c b/builtin/name-rev.c\n>> index c41ea7c2a6..598da6c8bc 100644\n>> --- a/builtin/name-rev.c\n>> +++ b/builtin/name-rev.c\n>> @@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo\n>>  \t\tstruct commit *commit = (struct commit *)o;\n>>  \t\tint from_tag = starts_with(path, \"refs/tags/\");\n>>  \n>> -\t\tif (taggerdate == ULONG_MAX)\n>> +\t\tif (taggerdate == TIME_MAX)\n>>  \t\t\ttaggerdate = ((struct commit *)o)->date;\n>>  \t\tpath = name_ref_abbrev(path, can_abbreviate_output);\n>>  \t\tname_rev(commit, xstrdup(path), taggerdate, 0, 0,\n"},{"id":"327652","messageId":"20170906133519.amlc5yunx4yfl5u3@sigill.intra.peff.net","threadId":"46684","inReplyTo":"6a4cbbee-ffc6-739b-d649-079ba01439ca@grubix.eu","subject":"Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-06T13:35:19Z","receivedAt":"2017-09-06T13:35:25Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Sep 06, 2017 at 01:59:31PM +0200, Michael J Gruber wrote:\n\n> BTW, there's more fallout from those name-rev changes: In connection\n> with that other thread about surprising describe results for emacs.git I\n> noticed that I can easily get \"git name-rev --stdin\" to segfault there.\n> As easy as\n> \n> echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin\n> \n> for example.\n> \n> That's unfortunate for the use-case of name-rev to amend git log output.\n> \n> The reason seems to be that with \"--stdin\" or \"--all\", \"name-rev\" walks\n> and names all commits before beginning to use that those names for even\n> a single commit as above.\n> \n> That segfault bisects to the logic changing commit in\n> jc/name-rev-lw-tag, but I think the changed logic simply leads to more\n> xmallocs() the segfault sooner now. Or something that I dind't spot even\n> after a few hours.\n\nThe segfault seems to be due to running out of stack space. The problem\nis that name_rev() is recursive over the history graph.  That topic\nadded a parameter to the function, which increased the memory used for\neach level of the recursion. But the fundamental problem has always been\nthere. The right solution is to switch to iteration (with our own stack\nstructure if necessary).\n\nWe had similar problems with the recursive --contains traversal in tag,\nand ended up with cbc60b6720 (git tag --contains: avoid stack overflow,\n2014-04-24).\n\n-Peff\n"},{"id":"327703","messageId":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","threadId":"46684","inReplyTo":"20170906133519.amlc5yunx4yfl5u3@sigill.intra.peff.net","subject":"Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T12:17:13Z","receivedAt":"2017-09-07T12:17:34Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Jeff King venit, vidit, dixit 06.09.2017 15:35:\n> On Wed, Sep 06, 2017 at 01:59:31PM +0200, Michael J Gruber wrote:\n> \n>> BTW, there's more fallout from those name-rev changes: In connection\n>> with that other thread about surprising describe results for emacs.git I\n>> noticed that I can easily get \"git name-rev --stdin\" to segfault there.\n>> As easy as\n>>\n>> echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin\n>>\n>> for example.\n>>\n>> That's unfortunate for the use-case of name-rev to amend git log output.\n>>\n>> The reason seems to be that with \"--stdin\" or \"--all\", \"name-rev\" walks\n>> and names all commits before beginning to use that those names for even\n>> a single commit as above.\n>>\n>> That segfault bisects to the logic changing commit in\n>> jc/name-rev-lw-tag, but I think the changed logic simply leads to more\n>> xmallocs() the segfault sooner now. Or something that I dind't spot even\n>> after a few hours.\n> \n> The segfault seems to be due to running out of stack space. The problem\n> is that name_rev() is recursive over the history graph.  That topic\n> added a parameter to the function, which increased the memory used for\n> each level of the recursion. But the fundamental problem has always been\n> there. The right solution is to switch to iteration (with our own stack\n> structure if necessary).\n> \n> We had similar problems with the recursive --contains traversal in tag,\n> and ended up with cbc60b6720 (git tag --contains: avoid stack overflow,\n> 2014-04-24).\n\nCool, thanks for the pointer. ulimit -s is a great way to test this.\n\nMichael\n"},{"id":"327705","messageId":"eb1b76068d898dd5fe1d4549c8985796a083ce18.1504792601.git.git@grubix.eu","threadId":"46684","inReplyTo":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","subject":"[PATCH 2/4] t6120: test name-rev --all and --stdin","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T14:02:21Z","receivedAt":"2017-09-07T14:02:51Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"name-rev is used in a few tests, but tested only in t6120 along with\ndescribe so far.\n\nAdd tests for name-rev with --all and --stdin.\n\nSigned-off-by: Michael J Gruber <git@grubix.eu>\n---\n t/t6120-describe.sh | 25 +++++++++++++++++++++++++\n 1 file changed, 25 insertions(+)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex aa74eb8f0d..7c5728ebd5 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -198,6 +198,31 @@ test_expect_success 'name-rev with exact tags' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'name-rev --all' '\n+\t>expect.unsorted &&\n+\tfor rev in $(git rev-list --all)\n+\tdo\n+\t\tgit name-rev $rev >>expect.unsorted\n+\tdone &&\n+\tsort <expect.unsorted >expect &&\n+\tgit name-rev --all >actual.unsorted &&\n+\tsort <actual.unsorted >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success 'name-rev --stdin' '\n+\t>expect.unsorted &&\n+\tfor rev in $(git rev-list --all)\n+\tdo\n+\t\tname=$(git name-rev --name-only $rev) &&\n+\t\techo \"$rev ($name)\" >>expect.unsorted\n+\tdone &&\n+\tsort <expect.unsorted >expect &&\n+\tgit rev-list --all | git name-rev --stdin >actual.unsorted &&\n+\tsort <actual.unsorted >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_expect_success 'describe --contains with the exact tags' '\n \techo \"A^0\" >expect &&\n \ttag_object=$(git rev-parse refs/tags/A) &&\n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327706","messageId":"3d30936525a83c6126155d1f32d43f3f09167904.1504792601.git.git@grubix.eu","threadId":"46684","inReplyTo":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","subject":"[PATCH 4/4] t6120: test describe and name-rev with deep repos","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T14:02:23Z","receivedAt":"2017-09-07T14:02:56Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Depending on the implementation of walks, limitted stack size may lead\nto problems (for recursion).\n\nTest name-rev and describe with deep repos and limitted stack size and\nmark the former with known failure.\n\nWe add these tests (which add gazillions of commits) last so as to keep\nthe runtime of other subtests the same.\n\nSigned-off-by: Michael J Gruber <git@grubix.eu>\n---\n t/t6120-describe.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 1997ccde56..dd6dd9df9b 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -279,4 +279,35 @@ test_expect_success 'describe ignoring a borken submodule' '\n \tgrep broken out\n '\n \n+# we require ulimit, this excludes Windows\n+test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '\n+\ti=1 &&\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+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+\techo \"HEAD~4000 tags/far-far-away~3999\" >expect &&\n+\tgit name-rev HEAD~4000 >actual &&\n+\ttest_cmp expect actual &&\n+\trun_with_limited_stack git name-rev HEAD~4000 >actual &&\n+\ttest_cmp expect actual\n+'\n+\n+test_expect_success ULIMIT_STACK_SIZE 'describe works in a deep repo' '\n+\tgit tag -f far-far-away HEAD~7999 &&\n+\techo \"far-far-away\" >expect &&\n+\tgit describe --tags --abbrev=0 HEAD~4000 >actual &&\n+\ttest_cmp expect actual &&\n+\trun_with_limited_stack git describe --tags --abbrev=0 HEAD~4000 >actual &&\n+\ttest_cmp expect actual\n+'\n+\n test_done\n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327707","messageId":"7917efead45441d5b3cb18b4d1608d5112445f62.1504792601.git.git@grubix.eu","threadId":"46684","inReplyTo":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","subject":"[PATCH 1/4] t7004: move limited stack prereq to test-lib","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T14:02:20Z","receivedAt":"2017-09-07T14:03:02Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"The lazy prerequisite  ULIMIT_STACK_SIZE is used only in t7004 so far.\n\nMove it to test-lib.sh so that it can be used in other tests (which it will\nbe in a follow-up commit).\n\nSigned-off-by: Michael J Gruber <git@grubix.eu>\n---\n t/t7004-tag.sh | 6 ------\n t/test-lib.sh  | 6 ++++++\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\nindex dbcd6f623c..5bf5ace56b 100755\n--- a/t/t7004-tag.sh\n+++ b/t/t7004-tag.sh\n@@ -1863,12 +1863,6 @@ test_expect_success 'version sort with very long prerelease suffix' '\n \tgit tag -l --sort=version:refname\n '\n \n-run_with_limited_stack () {\n-\t(ulimit -s 128 && \"$@\")\n-}\n-\n-test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'\n-\n # we require ulimit, this excludes Windows\n test_expect_success ULIMIT_STACK_SIZE '--contains and --no-contains work in a deep repo' '\n \t>expect &&\ndiff --git a/t/test-lib.sh b/t/test-lib.sh\nindex 5fbd8d4a90..f22c1b260a 100644\n--- a/t/test-lib.sh\n+++ b/t/test-lib.sh\n@@ -1167,6 +1167,12 @@ run_with_limited_cmdline () {\n \n test_lazy_prereq CMDLINE_LIMIT 'run_with_limited_cmdline true'\n \n+run_with_limited_stack () {\n+\t(ulimit -s 128 && \"$@\")\n+}\n+\n+test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'\n+\n build_option () {\n \tgit version --build-options |\n \tsed -ne \"s/^$1: //p\"\n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327708","messageId":"3c51bd03dd26a495845887b1213aca2af2fce8c0.1504792601.git.git@grubix.eu","threadId":"46684","inReplyTo":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","subject":"[PATCH 3/4] t6120: clean up state after breaking repo","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T14:02:22Z","receivedAt":"2017-09-07T14:03:07Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"t6120 breaks the repo state intentionally in the last tests.\n\nClean up the breakage afterwards (and before adding more tests).\n\nSigned-off-by: Michael J Gruber <git@grubix.eu>\n---\n t/t6120-describe.sh | 1 +\n 1 file changed, 1 insertion(+)\n\ndiff --git a/t/t6120-describe.sh b/t/t6120-describe.sh\nindex 7c5728ebd5..1997ccde56 100755\n--- a/t/t6120-describe.sh\n+++ b/t/t6120-describe.sh\n@@ -275,6 +275,7 @@ test_expect_success 'describe chokes on severely broken submodules' '\n '\n test_expect_success 'describe ignoring a borken submodule' '\n \tgit describe --broken >out &&\n+\ttest_when_finished \"mv .git/modules/sub_moved .git/modules/sub1\" &&\n \tgrep broken out\n '\n \n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327709","messageId":"cover.1504792601.git.git@grubix.eu","threadId":"46684","inReplyTo":"c1cb526d-a567-b598-d980-5dbe695b7d6a@grubix.eu","subject":"[PATCH 0/4] Test name-rev with small stack","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-07T14:02:19Z","receivedAt":"2017-09-07T14:03:12Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"name-rev segfaults for me in emacs.git with the typical 8102 stack size.\nThe reason is the recursive walk that name-rev uses.\n\nThis series adds a test to mark this as known failure, after some\nclean-ups.\n\nMichael J Gruber (4):\n  t7004: move limited stack prereq to test-lib\n  t6120: test name-rev --all and --stdin\n  t6120: clean up state after breaking repo\n  t6120: test describe and name-rev with deep repos\n\n t/t6120-describe.sh | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++\n t/t7004-tag.sh      |  6 ------\n t/test-lib.sh       |  6 ++++++\n 3 files changed, 63 insertions(+), 6 deletions(-)\n\n-- \n2.14.1.603.gf58147c36e\n\n"},{"id":"327712","messageId":"20170907145423.wz3iqxxz2yvxq5lm@sigill.intra.peff.net","threadId":"46684","inReplyTo":"cover.1504792601.git.git@grubix.eu","subject":"Re: [PATCH 0/4] Test name-rev with small stack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-07T14:54:23Z","receivedAt":"2017-09-07T14:54:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Sep 07, 2017 at 04:02:19PM +0200, Michael J Gruber wrote:\n\n> name-rev segfaults for me in emacs.git with the typical 8102 stack size.\n> The reason is the recursive walk that name-rev uses.\n> \n> This series adds a test to mark this as known failure, after some\n> clean-ups.\n\nThese all look reasonable to me. The size of the test case in the final\none is presumably arbitrary and just copied from t7004. I don't know if\nit's worth trying to shrink it. It could shorten a rather expensive\ntest. OTOH, if we shorten it too much then we might get a false pass\n(e.g., if the algorithm remains recursive but has a smaller stack\nfootprint).\n\n> Michael J Gruber (4):\n>   t7004: move limited stack prereq to test-lib\n>   t6120: test name-rev --all and --stdin\n>   t6120: clean up state after breaking repo\n>   t6120: test describe and name-rev with deep repos\n\nNow comes the hard part: rewriting the C code. :)\n\n-Peff\n"},{"id":"327767","messageId":"9b3275a2-7b47-9ed8-6f1f-dac999c3b46a@grubix.eu","threadId":"46684","inReplyTo":"20170907145423.wz3iqxxz2yvxq5lm@sigill.intra.peff.net","subject":"Re: [PATCH 0/4] Test name-rev with small stack","fromName":"Michael J Gruber","fromEmail":"git@grubix.eu","sentAt":"2017-09-08T12:33:35Z","receivedAt":"2017-09-08T12:33:49Z","isPatch":true,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Jeff King venit, vidit, dixit 07.09.2017 16:54:\n> On Thu, Sep 07, 2017 at 04:02:19PM +0200, Michael J Gruber wrote:\n> \n>> name-rev segfaults for me in emacs.git with the typical 8102 stack size.\n>> The reason is the recursive walk that name-rev uses.\n>>\n>> This series adds a test to mark this as known failure, after some\n>> clean-ups.\n> \n> These all look reasonable to me. The size of the test case in the final\n> one is presumably arbitrary and just copied from t7004. I don't know if\n> it's worth trying to shrink it. It could shorten a rather expensive\n> test. OTOH, if we shorten it too much then we might get a false pass\n> (e.g., if the algorithm remains recursive but has a smaller stack\n> footprint).\n> \n>> Michael J Gruber (4):\n>>   t7004: move limited stack prereq to test-lib\n>>   t6120: test name-rev --all and --stdin\n>>   t6120: clean up state after breaking repo\n>>   t6120: test describe and name-rev with deep repos\n> \n> Now comes the hard part: rewriting the C code. :)\n\nLooking at it more closely, the solution in cbc60b6720 (\"git tag\n--contains: avoid stack overflow\", 2014-04-24) seems to be a bit \"ad\nhoc\" to me:\n\nFirst of all, there is more than \"tag --contains\" that may exceed the\nstack by recursion. So I would expect the solution to be more general,\nand not localised and specialised to builtin/tag.c\n\nSecond, this is a walk, so I'm wondering whether our revision walk\nmachinery should be the place to add missing functionality (if any).\nThat way, everything would benefit from possible or existing\nimprovements there. For example, I think some of our \"extra walkers\"\ndon't heed object replacements. (I need to test more.)\n\nMichael\n"},{"id":"327855","messageId":"20170911180824.gf6jecxpx7d3d4a7@sigill.intra.peff.net","threadId":"46684","inReplyTo":"9b3275a2-7b47-9ed8-6f1f-dac999c3b46a@grubix.eu","subject":"Re: [PATCH 0/4] Test name-rev with small stack","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-09-11T18:08:25Z","receivedAt":"2017-09-11T18:08:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Sep 08, 2017 at 02:33:35PM +0200, Michael J Gruber wrote:\n\n> Looking at it more closely, the solution in cbc60b6720 (\"git tag\n> --contains: avoid stack overflow\", 2014-04-24) seems to be a bit \"ad\n> hoc\" to me:\n> \n> First of all, there is more than \"tag --contains\" that may exceed the\n> stack by recursion. So I would expect the solution to be more general,\n> and not localised and specialised to builtin/tag.c\n\nAt the time, tag was the only one using this depth-first contains\nalgorithm. It's since been adapted to ref-filter.c, but of course the\nstack handling went with it.\n\nMost traversals have a date-sorted queue, so are effectively doing a\nbreadth-first iteration with no recursion.\n\n> Second, this is a walk, so I'm wondering whether our revision walk\n> machinery should be the place to add missing functionality (if any).\n> That way, everything would benefit from possible or existing\n> improvements there. For example, I think some of our \"extra walkers\"\n> don't heed object replacements. (I need to test more.)\n\nIt's possible that name-rev could make better use of the existing\ntraversal machinery. It's often tough to do so, though, because that\nmachinery gives you a linearized ordering of the commits. Whereas\nsomething like name-rev really cares about the order that it visits the\ncommits, because it's building up the names.\n\nIt's the same for this \"tag --contains\" traversal. It _used_ to be a\nseries of merge-base computations. But by doing a custom traversal, we\ncan cache incremental results through the graph and avoid walking over\nthe same bits multiple times. There actually is a way to do it with the\nregular breadth-first traversal, but you have to store one bit per ref\nyou're checking for each commit.\n\nI played around with that a bit a while ago, and it did seem to work. I\ncan dig up the patches if you're interested. But one downside is that\none bit per ref per commit adds up if you have a lot of refs. A large\nnumber of those bitfields will be the same, so you could probably get by\nwith a copy-on-write scheme, but I never implemented that.\n\nOf course somebody may have a more clever algorithm, too. I don't claim\nthe above is a proof. ;)\n\n-Peff\n"}]}