threads / patch / 46684

patchname-rev: change ULONG_MAX to TIME_MAX

Subject: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

## tl;dr

14 messages between Aug 30, 2017 and Sep 11, 2017. Diffs are folded; open one to read it.

replies: 13people: 5as markdown or json

Michael J Gruber· Aug 30, 2017, 09:46 UTC · lore

Earlier, dddbad728c ("timestamp_t: a new data type for timestamps", 2017-04-26) changed several types to timestamp_t.

5589e87fd8 ("name-rev: change a "long" variable to timestamp_t", 2017-05-20) cleaned up a missed variable, but both missed a _MAX constant.

Change the remaining constant to the one appropriate for the current type

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 builtin/name-rev.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Show changes to builtin/name-rev.c +1 −1
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index c41ea7c2a6..598da6c8bc 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		struct commit *commit = (struct commit *)o;
 		int from_tag = starts_with(path, "refs/tags/");
 
-		if (taggerdate == ULONG_MAX)
+		if (taggerdate == TIME_MAX)
 			taggerdate = ((struct commit *)o)->date;
 		path = name_ref_abbrev(path, can_abbreviate_output);
 		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
-- 
2.14.1.603.gf58147c36e
Johannes Schindelin· Aug 30, 2017, 20:23 UTC · re: Michael J Gruber · lore

Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

Hi Michael,
On Wed, 30 Aug 2017, Michael J Gruber wrote:
Show 11 quoted lines
> Earlier, dddbad728c ("timestamp_t: a new data type for timestamps",
> 2017-04-26) changed several types to timestamp_t.
> 
> 5589e87fd8 ("name-rev: change a "long" variable to timestamp_t",
> 2017-05-20) cleaned up a missed variable, but both missed a _MAX
> constant.
> 
> Change the remaining constant to the one appropriate for the current
> type
> 
> Signed-off-by: Michael J Gruber <git@grubix.eu>
Good catch!

ACK, Dscho

Junio C Hamano· Sep 6, 2017, 03:35 UTC · re: Michael J Gruber · lore

Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

Michael J Gruber <git@grubix.eu> writes:
Show 12 quoted lines
> Earlier, dddbad728c ("timestamp_t: a new data type for timestamps",
> 2017-04-26) changed several types to timestamp_t.
>
> 5589e87fd8 ("name-rev: change a "long" variable to timestamp_t",
> 2017-05-20) cleaned up a missed variable, but both missed a _MAX
> constant.
>
> Change the remaining constant to the one appropriate for the current
> type
>
> Signed-off-by: Michael J Gruber <git@grubix.eu>
> ---
Thanks.

I think this (and the earlier 5589e8) was caused by an unnoticed semantic conflict at 78089b71 ("Merge branch 'jc/name-rev-lw-tag'", 2017-05-30). Merging is sometimes hard ;-)

Will queue.
Show 16 quoted lines
>  builtin/name-rev.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index c41ea7c2a6..598da6c8bc 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		struct commit *commit = (struct commit *)o;
>  		int from_tag = starts_with(path, "refs/tags/");
>  
> -		if (taggerdate == ULONG_MAX)
> +		if (taggerdate == TIME_MAX)
>  			taggerdate = ((struct commit *)o)->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
>  		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
Michael J Gruber· Sep 6, 2017, 11:59 UTC · re: Junio C Hamano · lore

Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

Junio C Hamano venit, vidit, dixit 06.09.2017 05:35:
Show 20 quoted lines
> Michael J Gruber <git@grubix.eu> writes:
> 
>> Earlier, dddbad728c ("timestamp_t: a new data type for timestamps",
>> 2017-04-26) changed several types to timestamp_t.
>>
>> 5589e87fd8 ("name-rev: change a "long" variable to timestamp_t",
>> 2017-05-20) cleaned up a missed variable, but both missed a _MAX
>> constant.
>>
>> Change the remaining constant to the one appropriate for the current
>> type
>>
>> Signed-off-by: Michael J Gruber <git@grubix.eu>
>> ---
> 
> Thanks.
> 
> I think this (and the earlier 5589e8) was caused by an unnoticed
> semantic conflict at 78089b71 ("Merge branch 'jc/name-rev-lw-tag'",
> 2017-05-30).  Merging is sometimes hard ;-)
Simple merges and semi-simple merges...

BTW, there's more fallout from those name-rev changes: In connection with that other thread about surprising describe results for emacs.git I noticed that I can easily get "git name-rev --stdin" to segfault there. As easy as

echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin
for example.
That's unfortunate for the use-case of name-rev to amend git log output.

The reason seems to be that with "--stdin" or "--all", "name-rev" walks and names all commits before beginning to use that those names for even a single commit as above.

That segfault bisects to the logic changing commit in jc/name-rev-lw-tag, but I think the changed logic simply leads to more xmallocs() the segfault sooner now. Or something that I dind't spot even after a few hours.

On the other hand, nearly every time that I try to understand describe or name-rev I want get rid of insert_commit_by_date() and the like and replace this by generations, and maybe a simple rev-walk (per ref)...

Show 18 quoted lines
> Will queue.
> 
>>  builtin/name-rev.c | 2 +-
>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
>> index c41ea7c2a6..598da6c8bc 100644
>> --- a/builtin/name-rev.c
>> +++ b/builtin/name-rev.c
>> @@ -253,7 +253,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>>  		struct commit *commit = (struct commit *)o;
>>  		int from_tag = starts_with(path, "refs/tags/");
>>  
>> -		if (taggerdate == ULONG_MAX)
>> +		if (taggerdate == TIME_MAX)
>>  			taggerdate = ((struct commit *)o)->date;
>>  		path = name_ref_abbrev(path, can_abbreviate_output);
>>  		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
Jeff King· Sep 6, 2017, 13:35 UTC · re: Michael J Gruber · lore

Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

On Wed, Sep 06, 2017 at 01:59:31PM +0200, Michael J Gruber wrote:
Show 19 quoted lines
> BTW, there's more fallout from those name-rev changes: In connection
> with that other thread about surprising describe results for emacs.git I
> noticed that I can easily get "git name-rev --stdin" to segfault there.
> As easy as
> 
> echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin
> 
> for example.
> 
> That's unfortunate for the use-case of name-rev to amend git log output.
> 
> The reason seems to be that with "--stdin" or "--all", "name-rev" walks
> and names all commits before beginning to use that those names for even
> a single commit as above.
> 
> That segfault bisects to the logic changing commit in
> jc/name-rev-lw-tag, but I think the changed logic simply leads to more
> xmallocs() the segfault sooner now. Or something that I dind't spot even
> after a few hours.

The segfault seems to be due to running out of stack space. The problem is that name_rev() is recursive over the history graph. That topic added a parameter to the function, which increased the memory used for each level of the recursion. But the fundamental problem has always been there. The right solution is to switch to iteration (with our own stack structure if necessary).

We had similar problems with the recursive --contains traversal in tag, and ended up with cbc60b6720 (git tag --contains: avoid stack overflow, 2014-04-24).

-Peff
Michael J Gruber· Sep 7, 2017, 12:17 UTC · re: Jeff King · lore

Re: [PATCH] name-rev: change ULONG_MAX to TIME_MAX

Jeff King venit, vidit, dixit 06.09.2017 15:35:
Show 32 quoted lines
> On Wed, Sep 06, 2017 at 01:59:31PM +0200, Michael J Gruber wrote:
> 
>> BTW, there's more fallout from those name-rev changes: In connection
>> with that other thread about surprising describe results for emacs.git I
>> noticed that I can easily get "git name-rev --stdin" to segfault there.
>> As easy as
>>
>> echo bc5d96a0b2a1dccf7eeeec459e40d21b54c977f4 | git name-rev --stdin
>>
>> for example.
>>
>> That's unfortunate for the use-case of name-rev to amend git log output.
>>
>> The reason seems to be that with "--stdin" or "--all", "name-rev" walks
>> and names all commits before beginning to use that those names for even
>> a single commit as above.
>>
>> That segfault bisects to the logic changing commit in
>> jc/name-rev-lw-tag, but I think the changed logic simply leads to more
>> xmallocs() the segfault sooner now. Or something that I dind't spot even
>> after a few hours.
> 
> The segfault seems to be due to running out of stack space. The problem
> is that name_rev() is recursive over the history graph.  That topic
> added a parameter to the function, which increased the memory used for
> each level of the recursion. But the fundamental problem has always been
> there. The right solution is to switch to iteration (with our own stack
> structure if necessary).
> 
> We had similar problems with the recursive --contains traversal in tag,
> and ended up with cbc60b6720 (git tag --contains: avoid stack overflow,
> 2014-04-24).
Cool, thanks for the pointer. ulimit -s is a great way to test this.
Michael
Michael J Gruber· Sep 7, 2017, 14:02 UTC · re: Michael J Gruber · lore

[PATCH 2/4] t6120: test name-rev --all and --stdin

name-rev is used in a few tests, but tested only in t6120 along with describe so far.

Add tests for name-rev with --all and --stdin.
Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t6120-describe.sh | 25 +++++++++++++++++++++++++
 1 file changed, 25 insertions(+)
Show changes to t/t6120-describe.sh +25 −0
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index aa74eb8f0d..7c5728ebd5 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -198,6 +198,31 @@ test_expect_success 'name-rev with exact tags' '
 	test_cmp expect actual
 '
 
+test_expect_success 'name-rev --all' '
+	>expect.unsorted &&
+	for rev in $(git rev-list --all)
+	do
+		git name-rev $rev >>expect.unsorted
+	done &&
+	sort <expect.unsorted >expect &&
+	git name-rev --all >actual.unsorted &&
+	sort <actual.unsorted >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'name-rev --stdin' '
+	>expect.unsorted &&
+	for rev in $(git rev-list --all)
+	do
+		name=$(git name-rev --name-only $rev) &&
+		echo "$rev ($name)" >>expect.unsorted
+	done &&
+	sort <expect.unsorted >expect &&
+	git rev-list --all | git name-rev --stdin >actual.unsorted &&
+	sort <actual.unsorted >actual &&
+	test_cmp expect actual
+'
+
 test_expect_success 'describe --contains with the exact tags' '
 	echo "A^0" >expect &&
 	tag_object=$(git rev-parse refs/tags/A) &&
-- 
2.14.1.603.gf58147c36e
Michael J Gruber· Sep 7, 2017, 14:02 UTC · re: Michael J Gruber · lore

[PATCH 4/4] t6120: test describe and name-rev with deep repos

Depending on the implementation of walks, limitted stack size may lead to problems (for recursion).

Test name-rev and describe with deep repos and limitted stack size and mark the former with known failure.

We add these tests (which add gazillions of commits) last so as to keep the runtime of other subtests the same.

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t6120-describe.sh | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)
Show changes to t/t6120-describe.sh +31 −0
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 1997ccde56..dd6dd9df9b 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -279,4 +279,35 @@ test_expect_success 'describe ignoring a borken submodule' '
 	grep broken out
 '
 
+# we require ulimit, this excludes Windows
+test_expect_failure ULIMIT_STACK_SIZE 'name-rev works in a deep repo' '
+	i=1 &&
+	while test $i -lt 8000
+	do
+		echo "commit refs/heads/master
+committer A U Thor <author@example.com> $((1000000000 + $i * 100)) +0200
+data <<EOF
+commit #$i
+EOF"
+		test $i = 1 && echo "from refs/heads/master^0"
+		i=$(($i + 1))
+	done | git fast-import &&
+	git checkout master &&
+	git tag far-far-away HEAD^ &&
+	echo "HEAD~4000 tags/far-far-away~3999" >expect &&
+	git name-rev HEAD~4000 >actual &&
+	test_cmp expect actual &&
+	run_with_limited_stack git name-rev HEAD~4000 >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success ULIMIT_STACK_SIZE 'describe works in a deep repo' '
+	git tag -f far-far-away HEAD~7999 &&
+	echo "far-far-away" >expect &&
+	git describe --tags --abbrev=0 HEAD~4000 >actual &&
+	test_cmp expect actual &&
+	run_with_limited_stack git describe --tags --abbrev=0 HEAD~4000 >actual &&
+	test_cmp expect actual
+'
+
 test_done
-- 
2.14.1.603.gf58147c36e
Michael J Gruber· Sep 7, 2017, 14:02 UTC · re: Michael J Gruber · lore

[PATCH 1/4] t7004: move limited stack prereq to test-lib

The lazy prerequisite  ULIMIT_STACK_SIZE is used only in t7004 so far.

Move it to test-lib.sh so that it can be used in other tests (which it will be in a follow-up commit).

Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t7004-tag.sh | 6 ------
 t/test-lib.sh  | 6 ++++++
 2 files changed, 6 insertions(+), 6 deletions(-)
Show changes to 2 files +6 −6

t/t7004-tag.sh, t/test-lib.sh

diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh
index dbcd6f623c..5bf5ace56b 100755
--- a/t/t7004-tag.sh
+++ b/t/t7004-tag.sh
@@ -1863,12 +1863,6 @@ test_expect_success 'version sort with very long prerelease suffix' '
 	git tag -l --sort=version:refname
 '
 
-run_with_limited_stack () {
-	(ulimit -s 128 && "$@")
-}
-
-test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
-
 # we require ulimit, this excludes Windows
 test_expect_success ULIMIT_STACK_SIZE '--contains and --no-contains work in a deep repo' '
 	>expect &&
diff --git a/t/test-lib.sh b/t/test-lib.sh
index 5fbd8d4a90..f22c1b260a 100644
--- a/t/test-lib.sh
+++ b/t/test-lib.sh
@@ -1167,6 +1167,12 @@ run_with_limited_cmdline () {
 
 test_lazy_prereq CMDLINE_LIMIT 'run_with_limited_cmdline true'
 
+run_with_limited_stack () {
+	(ulimit -s 128 && "$@")
+}
+
+test_lazy_prereq ULIMIT_STACK_SIZE 'run_with_limited_stack true'
+
 build_option () {
 	git version --build-options |
 	sed -ne "s/^$1: //p"
-- 
2.14.1.603.gf58147c36e
Michael J Gruber· Sep 7, 2017, 14:02 UTC · re: Michael J Gruber · lore

[PATCH 3/4] t6120: clean up state after breaking repo

t6120 breaks the repo state intentionally in the last tests.
Clean up the breakage afterwards (and before adding more tests).
Signed-off-by: Michael J Gruber <git@grubix.eu>
---
 t/t6120-describe.sh | 1 +
 1 file changed, 1 insertion(+)
Show changes to t/t6120-describe.sh +1 −0
diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
index 7c5728ebd5..1997ccde56 100755
--- a/t/t6120-describe.sh
+++ b/t/t6120-describe.sh
@@ -275,6 +275,7 @@ test_expect_success 'describe chokes on severely broken submodules' '
 '
 test_expect_success 'describe ignoring a borken submodule' '
 	git describe --broken >out &&
+	test_when_finished "mv .git/modules/sub_moved .git/modules/sub1" &&
 	grep broken out
 '
 
-- 
2.14.1.603.gf58147c36e
Michael J Gruber· Sep 7, 2017, 14:02 UTC · re: Michael J Gruber · lore

[PATCH 0/4] Test name-rev with small stack

name-rev segfaults for me in emacs.git with the typical 8102 stack size. The reason is the recursive walk that name-rev uses.

This series adds a test to mark this as known failure, after some clean-ups.

Michael J Gruber (4):
  t7004: move limited stack prereq to test-lib
  t6120: test name-rev --all and --stdin
  t6120: clean up state after breaking repo
  t6120: test describe and name-rev with deep repos
 t/t6120-describe.sh | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 t/t7004-tag.sh      |  6 ------
 t/test-lib.sh       |  6 ++++++
 3 files changed, 63 insertions(+), 6 deletions(-)
-- 
2.14.1.603.gf58147c36e
Jeff King· Sep 7, 2017, 14:54 UTC · re: Michael J Gruber · lore

Re: [PATCH 0/4] Test name-rev with small stack

On Thu, Sep 07, 2017 at 04:02:19PM +0200, Michael J Gruber wrote:
Show 5 quoted lines
> name-rev segfaults for me in emacs.git with the typical 8102 stack size.
> The reason is the recursive walk that name-rev uses.
> 
> This series adds a test to mark this as known failure, after some
> clean-ups.

These all look reasonable to me. The size of the test case in the final one is presumably arbitrary and just copied from t7004. I don't know if it's worth trying to shrink it. It could shorten a rather expensive test. OTOH, if we shorten it too much then we might get a false pass (e.g., if the algorithm remains recursive but has a smaller stack footprint).

Show 5 quoted lines
> Michael J Gruber (4):
>   t7004: move limited stack prereq to test-lib
>   t6120: test name-rev --all and --stdin
>   t6120: clean up state after breaking repo
>   t6120: test describe and name-rev with deep repos
Now comes the hard part: rewriting the C code. :)
-Peff
Michael J Gruber· Sep 8, 2017, 12:33 UTC · re: Jeff King · lore

Re: [PATCH 0/4] Test name-rev with small stack

Jeff King venit, vidit, dixit 07.09.2017 16:54:
Show 22 quoted lines
> On Thu, Sep 07, 2017 at 04:02:19PM +0200, Michael J Gruber wrote:
> 
>> name-rev segfaults for me in emacs.git with the typical 8102 stack size.
>> The reason is the recursive walk that name-rev uses.
>>
>> This series adds a test to mark this as known failure, after some
>> clean-ups.
> 
> These all look reasonable to me. The size of the test case in the final
> one is presumably arbitrary and just copied from t7004. I don't know if
> it's worth trying to shrink it. It could shorten a rather expensive
> test. OTOH, if we shorten it too much then we might get a false pass
> (e.g., if the algorithm remains recursive but has a smaller stack
> footprint).
> 
>> Michael J Gruber (4):
>>   t7004: move limited stack prereq to test-lib
>>   t6120: test name-rev --all and --stdin
>>   t6120: clean up state after breaking repo
>>   t6120: test describe and name-rev with deep repos
> 
> Now comes the hard part: rewriting the C code. :)

Looking at it more closely, the solution in cbc60b6720 ("git tag --contains: avoid stack overflow", 2014-04-24) seems to be a bit "ad hoc" to me:

First of all, there is more than "tag --contains" that may exceed the stack by recursion. So I would expect the solution to be more general, and not localised and specialised to builtin/tag.c

Second, this is a walk, so I'm wondering whether our revision walk machinery should be the place to add missing functionality (if any). That way, everything would benefit from possible or existing improvements there. For example, I think some of our "extra walkers" don't heed object replacements. (I need to test more.)

Michael
Jeff King· Sep 11, 2017, 18:08 UTC · re: Michael J Gruber · lore

Re: [PATCH 0/4] Test name-rev with small stack

On Fri, Sep 08, 2017 at 02:33:35PM +0200, Michael J Gruber wrote:
Show 7 quoted lines
> Looking at it more closely, the solution in cbc60b6720 ("git tag
> --contains: avoid stack overflow", 2014-04-24) seems to be a bit "ad
> hoc" to me:
> 
> First of all, there is more than "tag --contains" that may exceed the
> stack by recursion. So I would expect the solution to be more general,
> and not localised and specialised to builtin/tag.c

At the time, tag was the only one using this depth-first contains algorithm. It's since been adapted to ref-filter.c, but of course the stack handling went with it.

Most traversals have a date-sorted queue, so are effectively doing a breadth-first iteration with no recursion.

Show 5 quoted lines
> Second, this is a walk, so I'm wondering whether our revision walk
> machinery should be the place to add missing functionality (if any).
> That way, everything would benefit from possible or existing
> improvements there. For example, I think some of our "extra walkers"
> don't heed object replacements. (I need to test more.)

It's possible that name-rev could make better use of the existing traversal machinery. It's often tough to do so, though, because that machinery gives you a linearized ordering of the commits. Whereas something like name-rev really cares about the order that it visits the commits, because it's building up the names.

It's the same for this "tag --contains" traversal. It _used_ to be a series of merge-base computations. But by doing a custom traversal, we can cache incremental results through the graph and avoid walking over the same bits multiple times. There actually is a way to do it with the regular breadth-first traversal, but you have to store one bit per ref you're checking for each commit.

I played around with that a bit a while ago, and it did seem to work. I can dig up the patches if you're interested. But one downside is that one bit per ref per commit adds up if you have a lot of refs. A large number of those bitfields will be the same, so you could probably get by with a copy-on-write scheme, but I never implemented that.

Of course somebody may have a more clever algorithm, too. I don't claim the above is a proof. ;)

-Peff

← back to recent threads