patch, 15 partsname-rev: eliminate recursion

> +#       ,---o----o----o-----.
> +#      /   D,R   e           \
> +#  o--o-----o-------------o---o----x
> +#      \    B            /
> +#       `---o----o----o-'
> +#                A    c

> -                       B
> -        .--------------o---1o---2o----x
> -       /                   2    1
> - o----o----o----o----o----.    /
> -       \        A    c        /
> -        .------------o---o---o
> -                   D,R   e

> SZEDER Gábor <szeder.dev@gmail.com> writes:
> 
> > At the top of 't6120-describe.sh' an ASCII graph illustrates the
> > repository's history used in this test script.  This graph is a bit
> > misleading, because it swapped the second merge commit's first and
> > second parents.
> 
> Hmm...
> 
> > +#       ,---o----o----o-----.
> > +#      /   D,R   e           \
> > +#  o--o-----o-------------o---o----x
> > +#      \    B            /
> > +#       `---o----o----o-'
> > +#                A    c
> 
> What's the first parent of the merge between 'B' and 'c' in this
> picture and how does the reader figure it out?  What about the same
> question on the direct parent of 'x'?  Is it generally accepted that
> a straight line denotes the first ancestry, or something?

>> Hmm...
>> 
>> > +#       ,---o----o----o-----.
>> > +#      /   D,R   e           \
>> > +#  o--o-----o-------------o---o----x
>> > +#      \    B            /
>> > +#       `---o----o----o-'
>> > +#                A    c
>> 
>> What's the first parent of the merge between 'B' and 'c' in this
>> picture and how does the reader figure it out?  What about the same
>> question on the direct parent of 'x'?  Is it generally accepted that
>> a straight line denotes the first ancestry, or something?
>
> I've always thought that the parents are numbered from top to bottom,
> i.e. 'B' is the first parent of the first merge, and the unnamed
> commit at the top is the first parent of the second merge.
>
> Would it help if it were arranged like this:
>
>   o---o-----o----o----o-------o----x
>        \   D,R   e           /
>         \---o-------------o-'
>          \  B            /
>           `-o----o----o-'
>                  A    c
>
> This is basically how 'git log --graph' would show them, except that
> this is horizontal.

> The 'check_describe' helper function runs 'git describe' outside of
> 'test_expect_success' blocks, with extra hand-rolled code to record
> and examine its exit code.
>
> Update this helper and move the 'git decribe' invocation inside the
> 'test_expect_success' block.

>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  t/t6120-describe.sh | 10 ++++------
>  1 file changed, 4 insertions(+), 6 deletions(-)
>
> diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
> index 0bf7e0c8bc..07e6793e84 100755
> --- a/t/t6120-describe.sh
> +++ b/t/t6120-describe.sh
> @@ -14,14 +14,12 @@ test_description='test describe'
>  check_describe () {
>  	expect="$1"
>  	shift
> -	R=$(git describe "$@" 2>err.actual)
> -	S=$?
> -	cat err.actual >&3
> -	test_expect_success "describe $*" '
> -	test $S = 0 &&
> +	describe_opts="$@"
> +	test_expect_success "describe $describe_opts" '
> +	R=$(git describe $describe_opts 2>err.actual) &&
>  	case "$R" in
>  	$expect)	echo happy ;;
> -	*)	echo "Oops - $R is not $expect";
> +	*)	echo "Oops - $R is not $expect" &&
>  		false ;;
>  	esac
>  	'

> Use strip_suffix() instead of open-coding it, making the code more
> idiomatic.
>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index c785fe16ba..d345456656 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -317,11 +317,11 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
>  	if (!n->generation)
>  		return n->tip_name;
>  	else {
> -		int len = strlen(n->tip_name);
> -		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
> -			len -= 2;
> +		size_t len;
> +		strip_suffix(n->tip_name, "^0", &len);
>  		strbuf_reset(buf);
> -		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
> +		strbuf_addf(buf, "%.*s~%d", (int) len, n->tip_name,
> +			    n->generation);
>  		return buf->buf;
>  	}
>  }
>

> Am 19.09.19 um 23:46 schrieb SZEDER Gábor:
> > Use strip_suffix() instead of open-coding it, making the code more
> > idiomatic.
> >
> > Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> > ---
> >  builtin/name-rev.c | 8 ++++----
> >  1 file changed, 4 insertions(+), 4 deletions(-)
> >
> > diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> > index c785fe16ba..d345456656 100644
> > --- a/builtin/name-rev.c
> > +++ b/builtin/name-rev.c
> > @@ -317,11 +317,11 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
> >  	if (!n->generation)
> >  		return n->tip_name;
> >  	else {
> > -		int len = strlen(n->tip_name);
> > -		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
> > -			len -= 2;
> > +		size_t len;
> > +		strip_suffix(n->tip_name, "^0", &len);
> >  		strbuf_reset(buf);
> > -		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
> > +		strbuf_addf(buf, "%.*s~%d", (int) len, n->tip_name,
> > +			    n->generation);
> >  		return buf->buf;
> >  	}
> >  }
> >
> 
> This gets rid of the repeated magic string length constant 2, which is
> nice.  But why not go all the way to full strbuf-ness?  It's shorter,
> looks less busy, and the extra two copied bytes shouldn't matter in a
> measurable way.
> 
> 	else {
> 		strbuf_reset(buf);
> 		strbuf_addstr(buf, n->tip_name);
> 		strbuf_strip_suffix(buf, "^0");
> 		strbuf_addf(buf, "~%d", n->generation);
> 		return buf->buf;
> 	}

> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  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 e406ff8e17..dec2228cc7 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -98,7 +98,7 @@ static void name_rev(struct commit *commit,
>  	}
>  
>  	if (name == NULL) {
> -		name = xmalloc(sizeof(rev_name));
> +		name = xmalloc(sizeof(*name));

> On 9/19/2019 5:47 PM, SZEDER Gábor wrote:
> > Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> > ---
> >  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 e406ff8e17..dec2228cc7 100644
> > --- a/builtin/name-rev.c
> > +++ b/builtin/name-rev.c
> > @@ -98,7 +98,7 @@ static void name_rev(struct commit *commit,
> >  	}
> >  
> >  	if (name == NULL) {
> > -		name = xmalloc(sizeof(rev_name));
> > +		name = xmalloc(sizeof(*name));
> 
> Is this our preferred way to use xmalloc()? If so, then
> I've been doing it wrong and will correct myself in the
> future.

> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  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 e406ff8e17..dec2228cc7 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -98,7 +98,7 @@ static void name_rev(struct commit *commit,
>  	}
>
>  	if (name == NULL) {
> -		name = xmalloc(sizeof(rev_name));
> +		name = xmalloc(sizeof(*name));

> In 'builtin/name-rev.c' in the name_rev() function there is a loop
> iterating over all parents of the given commit, and the loop body
> looks like this:
> 
>   if (parent_number > 1) {
>     if (generation > 0)
>       // do stuff #1
>     else
>       // do stuff #2
>   } else {
>      // do stuff #3
>   }
> 
> These conditions are not covered properly in the test suite.  As far
> as purely test coverage goes, they are all executed several times over
> in 't6120-describe.sh'.  However, they don't directly influence the
> command's output, because the repository used in that test script
> contains several branches and tags pointing somewhere into the middle
> of the commit DAG, and thus result in a better name for the
> to-be-named commit.  In an early version of this patch series I
> managed to mess up those conditions (every single one of them at
> once!), but the whole test suite still passed successfully.
> 
> So add a new test case that operates on the following history:
> 
>     -----------master
>    /          /
>   A----------M2
>    \        /
>     \---M1-C
>      \ /
>       B
> 
> and names the commit 'B', where:
> 
>   - The merge commit at master makes sure that the 'do stuff #3'
>     affects the final name.
> 
>   - The merge commit M2 make sure that the 'do stuff #1' part
>     affects the final name.
> 
>   - And M1 makes sure that the 'do stuff #2' part affects the final
>     name.
> 
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  t/t6120-describe.sh | 43 +++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 43 insertions(+)
> 
> diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
> index 07e6793e84..2a0f2204c4 100755
> --- a/t/t6120-describe.sh
> +++ b/t/t6120-describe.sh
> @@ -421,4 +421,47 @@ test_expect_success 'describe complains about missing object' '
>  	test_must_fail git describe $ZERO_OID
>  '
>  
> +#   -----------master
> +#  /          /
> +# A----------M2
> +#  \        /
> +#   \---M1-C
> +#    \ /
> +#     B
> +test_expect_success 'test' '
> +	git init repo &&
> +	(
> +		cd repo &&
> +
> +		echo A >file &&
> +		git add file &&
> +		git commit -m A &&
> +		A=$(git rev-parse HEAD) &&

> +
> +		git checkout --detach &&
> +		echo B >file &&
> +		git commit -m B file &&
> +		B=$(git rev-parse HEAD) &&
> +
> +		git checkout $A &&
> +		git merge --no-ff $B &&  # M1
> +
> +		echo C >file &&
> +		git commit -m C file &&
> +
> +		git checkout $A &&
> +		git merge --no-ff HEAD@{1} && # M2
> +
> +		git checkout master &&
> +		git merge --no-ff HEAD@{1} &&
> +
> +		git log --graph --oneline &&
> +
> +		echo "$B master^2^2~1^2" >expect &&
> +		git name-rev $B >actual &&

> On 9/19/2019 5:47 PM, SZEDER Gábor wrote:
> > These conditions are not covered properly in the test suite.  As far
> > as purely test coverage goes, they are all executed several times over
> > in 't6120-describe.sh'.  However, they don't directly influence the
> > command's output, because the repository used in that test script
> > contains several branches and tags pointing somewhere into the middle
> > of the commit DAG, and thus result in a better name for the
> > to-be-named commit.

> > diff --git a/t/t6120-describe.sh b/t/t6120-describe.sh
> > index 07e6793e84..2a0f2204c4 100755
> > --- a/t/t6120-describe.sh
> > +++ b/t/t6120-describe.sh
> > @@ -421,4 +421,47 @@ test_expect_success 'describe complains about missing object' '
> >  	test_must_fail git describe $ZERO_OID
> >  '
> >  
> > +#   -----------master
> > +#  /          /
> > +# A----------M2
> > +#  \        /
> > +#   \---M1-C
> > +#    \ /
> > +#     B
> > +test_expect_success 'test' '
> > +	git init repo &&
> > +	(
> > +		cd repo &&
> > +
> > +		echo A >file &&
> > +		git add file &&
> > +		git commit -m A &&
> > +		A=$(git rev-parse HEAD) &&
> 
> Is it not enough to do something like test_commit here?

> > +
> > +		git checkout --detach &&
> > +		echo B >file &&
> > +		git commit -m B file &&
> > +		B=$(git rev-parse HEAD) &&
> > +
> > +		git checkout $A &&
> > +		git merge --no-ff $B &&  # M1
> > +
> > +		echo C >file &&
> > +		git commit -m C file &&
> > +
> > +		git checkout $A &&
> > +		git merge --no-ff HEAD@{1} && # M2
> > +
> > +		git checkout master &&
> > +		git merge --no-ff HEAD@{1} &&
> > +
> > +		git log --graph --oneline &&
> > +
> > +		echo "$B master^2^2~1^2" >expect &&
> > +		git name-rev $B >actual &&
> 
> This matches your description.
> 
> Thanks,
> -Stolee
>  

>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  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 d345456656..e406ff8e17 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -268,7 +268,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo

>  		int from_tag = starts_with(path, "refs/tags/");
>
>  		if (taggerdate == TIME_MAX)
> -			taggerdate = ((struct commit *)o)->date;
> +			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
>  		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
>  			 from_tag, deref);
>

> At the beginning of the recursive name_rev() function it creates a new
> 'struct rev_name' instance for each previously unvisited commit or, if
> this visit results in better name for an already visited commit, then
> updates the 'struct rev_name' instance attached to to the commit, or
> returns early.
> 
> Restructure this so it's caller creates or updates the 'struct
> rev_name' instance associated with the commit to be passed as
> parameter, i.e. both name_ref() before calling name_rev() and
> name_rev() itself as it iterates over the parent commits.
> 
> This makes eliminating the recursion a bit easier to follow, and it
> will be moved back to name_rev() after the recursion is eliminated.
> 
> This change also plugs the memory leak that was temporarily unplugged
> in the earlier "name-rev: pull out deref handling from the recursion"
> patch in this series.

>  
> @@ -276,11 +277,17 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		path = name_ref_abbrev(path, can_abbreviate_output);
>  		if (commit->date >= cutoff) {
>  			const char *tip_name;
> +			char *to_free = NULL;
>  			if (deref)
> -				tip_name = xstrfmt("%s^0", path);
> +				tip_name = to_free = xstrfmt("%s^0", path);
>  			else
>  				tip_name = xstrdup(path);

> -			name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);
> +			if (create_or_update_name(commit, tip_name, taggerdate,
> +						  0, 0, from_tag))
> +				name_rev(commit, tip_name, taggerdate, 0, 0,
> +					 from_tag);
> +			else
> +				free(to_free);
>  		}
>  	}
>  	return 0;
> 

> On 9/19/2019 5:47 PM, SZEDER Gábor wrote:
> > At the beginning of the recursive name_rev() function it creates a new
> > 'struct rev_name' instance for each previously unvisited commit or, if
> > this visit results in better name for an already visited commit, then
> > updates the 'struct rev_name' instance attached to to the commit, or
> > returns early.
> > 
> > Restructure this so it's caller creates or updates the 'struct
> > rev_name' instance associated with the commit to be passed as
> > parameter, i.e. both name_ref() before calling name_rev() and
> > name_rev() itself as it iterates over the parent commits.
> > 
> > This makes eliminating the recursion a bit easier to follow, and it
> > will be moved back to name_rev() after the recursion is eliminated.
> > 
> > This change also plugs the memory leak that was temporarily unplugged
> > in the earlier "name-rev: pull out deref handling from the recursion"
> > patch in this series.
> [snip]
> >  
> > @@ -276,11 +277,17 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
> >  		path = name_ref_abbrev(path, can_abbreviate_output);
> >  		if (commit->date >= cutoff) {
> >  			const char *tip_name;
> > +			char *to_free = NULL;
> >  			if (deref)
> > -				tip_name = xstrfmt("%s^0", path);
> > +				tip_name = to_free = xstrfmt("%s^0", path);
> >  			else
> >  				tip_name = xstrdup(path);
> 
> So this xstrdup(path) is not a leak?

> The 'if (deref) { ... }' condition near the beginning of the recursive
> name_rev() function can only ever be true in the first invocation,
> because the 'deref' parameter is always 0 in the subsequent recursive
> invocations.
> 
> Extract this condition from the recursion into name_rev()'s caller and
> drop the function's 'deref' parameter.  This makes eliminating the
> recursion a bit easier to follow, and it will be moved back into
> name_rev() after the recursion is elminated.
> 
> Furthermore, drop the condition that die()s when both 'deref' and
> 'generation' are non-null (which should have been a BUG() to begin
> with).

> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 27 ++++++++++-----------------
>  1 file changed, 10 insertions(+), 17 deletions(-)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index cb8ac2fa64..42cea5c881 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -102,30 +102,19 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>  
>  static void name_rev(struct commit *commit,
>  		const char *tip_name, timestamp_t taggerdate,
> -		int generation, int distance, int from_tag,
> -		int deref)
> +		int generation, int distance, int from_tag)
>  {
>  	struct commit_list *parents;
>  	int parent_number = 1;
> -	char *to_free = NULL;
>  
>  	parse_commit(commit);
>  
>  	if (commit->date < cutoff)
>  		return;
>  
> -	if (deref) {
> -		tip_name = to_free = xstrfmt("%s^0", tip_name);
> -
> -		if (generation)
> -			die("generation: %d, but deref?", generation);
> -	}
> -
>  	if (!create_or_update_name(commit, tip_name, taggerdate, generation,
> -				   distance, from_tag)) {
> -		free(to_free);
> +				   distance, from_tag))
>  		return;
> -	}
>  
>  	for (parents = commit->parents;
>  			parents;
> @@ -144,11 +133,11 @@ static void name_rev(struct commit *commit,
>  
>  			name_rev(parents->item, new_name, taggerdate, 0,
>  				 distance + MERGE_TRAVERSAL_WEIGHT,
> -				 from_tag, 0);
> +				 from_tag);
>  		} else {
>  			name_rev(parents->item, tip_name, taggerdate,
>  				 generation + 1, distance + 1,
> -				 from_tag, 0);
> +				 from_tag);
>  		}
>  	}
>  }
> @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  	if (o && o->type == OBJ_COMMIT) {
>  		struct commit *commit = (struct commit *)o;
>  		int from_tag = starts_with(path, "refs/tags/");
> +		const char *tip_name;
>  
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
> -		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
> -			 from_tag, deref);
> +		if (deref)
> +			tip_name = xstrfmt("%s^0", path);
> +		else
> +			tip_name = xstrdup(path);

> +		name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);
>  	}
>  	return 0;
>  }
> 

> On 9/19/2019 5:47 PM, SZEDER Gábor wrote:
> > The 'if (deref) { ... }' condition near the beginning of the recursive
> > name_rev() function can only ever be true in the first invocation,
> > because the 'deref' parameter is always 0 in the subsequent recursive
> > invocations.
> > 
> > Extract this condition from the recursion into name_rev()'s caller and
> > drop the function's 'deref' parameter.  This makes eliminating the
> > recursion a bit easier to follow, and it will be moved back into
> > name_rev() after the recursion is elminated.

> > Furthermore, drop the condition that die()s when both 'deref' and
> > 'generation' are non-null (which should have been a BUG() to begin
> > with).
> 
> These changes seem sensible. I look forward to seeing how deref is
> reintroduced.
> 
> > Note that this change reintroduces the memory leak that was plugged in
> > in commit 5308224633 (name-rev: avoid leaking memory in the `deref`
> > case, 2017-05-04), but a later patch in this series will plug it in
> > again.
> 
> The memory leak is now for "tip_name" correct? Just tracking to make
> sure it gets plugged later.

> The 'if (deref) { ... }' condition near the beginning of the recursive
> name_rev() function can only ever be true in the first invocation,
> because the 'deref' parameter is always 0 in the subsequent recursive
> invocations.
>
> Extract this condition from the recursion into name_rev()'s caller and
> drop the function's 'deref' parameter.  This makes eliminating the
> recursion a bit easier to follow, and it will be moved back into
> name_rev() after the recursion is elminated.
>
> Furthermore, drop the condition that die()s when both 'deref' and
> 'generation' are non-null (which should have been a BUG() to begin
> with).
>
> Note that this change reintroduces the memory leak that was plugged in
> in commit 5308224633 (name-rev: avoid leaking memory in the `deref`
> case, 2017-05-04), but a later patch in this series will plug it in
> again.
>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 27 ++++++++++-----------------
>  1 file changed, 10 insertions(+), 17 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index cb8ac2fa64..42cea5c881 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -102,30 +102,19 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>
>  static void name_rev(struct commit *commit,
>  		const char *tip_name, timestamp_t taggerdate,
> -		int generation, int distance, int from_tag,
> -		int deref)
> +		int generation, int distance, int from_tag)
>  {
>  	struct commit_list *parents;
>  	int parent_number = 1;
> -	char *to_free = NULL;
>
>  	parse_commit(commit);
>
>  	if (commit->date < cutoff)
>  		return;
>
> -	if (deref) {
> -		tip_name = to_free = xstrfmt("%s^0", tip_name);
> -
> -		if (generation)
> -			die("generation: %d, but deref?", generation);
> -	}
> -
>  	if (!create_or_update_name(commit, tip_name, taggerdate, generation,
> -				   distance, from_tag)) {
> -		free(to_free);
> +				   distance, from_tag))
>  		return;
> -	}
>
>  	for (parents = commit->parents;
>  			parents;
> @@ -144,11 +133,11 @@ static void name_rev(struct commit *commit,
>
>  			name_rev(parents->item, new_name, taggerdate, 0,
>  				 distance + MERGE_TRAVERSAL_WEIGHT,
> -				 from_tag, 0);
> +				 from_tag);
>  		} else {
>  			name_rev(parents->item, tip_name, taggerdate,
>  				 generation + 1, distance + 1,
> -				 from_tag, 0);
> +				 from_tag);
>  		}
>  	}
>  }
> @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  	if (o && o->type == OBJ_COMMIT) {
>  		struct commit *commit = (struct commit *)o;
>  		int from_tag = starts_with(path, "refs/tags/");
> +		const char *tip_name;

>
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
> -		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
> -			 from_tag, deref);
> +		if (deref)
> +			tip_name = xstrfmt("%s^0", path);
> +		else
> +			tip_name = xstrdup(path);
> +		name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);

> > @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
> >  	if (o && o->type == OBJ_COMMIT) {
> >  		struct commit *commit = (struct commit *)o;
> >  		int from_tag = starts_with(path, "refs/tags/");
> > +		const char *tip_name;
> 
> This should not be const because you allocate the buffer it points to
> right here in the function, in each execution path.

> >
> >  		if (taggerdate == TIME_MAX)
> >  			taggerdate = commit->date;
> >  		path = name_ref_abbrev(path, can_abbreviate_output);
> > -		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
> > -			 from_tag, deref);
> > +		if (deref)
> > +			tip_name = xstrfmt("%s^0", path);
> > +		else
> > +			tip_name = xstrdup(path);
> > +		name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);
> 
> tip_name should be free(3)'d here.  Except we can't do that because
> name_rev() sometimes stores that pointer in a commit slab.  Ugh.
> 
> If the (re)introduced leak doesn't impact performance and memory
> usage too much then duplicating tip_name again in name_rev() or
> rather your new create_or_update_name() would likely make the
> lifetimes of those string buffers easier to manage.

> > If the (re)introduced leak doesn't impact performance and memory
> > usage too much then duplicating tip_name again in name_rev() or
> > rather your new create_or_update_name() would likely make the
> > lifetimes of those string buffers easier to manage.
> 
> Yeah, the easiest would be when each 'struct rev_name' in the commit
> slab would have its own 'tip_name' string, but that would result in
> a lot of duplicated strings and increased memory usage.

> On Fri, Sep 20, 2019 at 08:13:02PM +0200, SZEDER Gábor wrote:
> > > If the (re)introduced leak doesn't impact performance and memory
> > > usage too much then duplicating tip_name again in name_rev() or
> > > rather your new create_or_update_name() would likely make the
> > > lifetimes of those string buffers easier to manage.
> > 
> > Yeah, the easiest would be when each 'struct rev_name' in the commit
> > slab would have its own 'tip_name' string, but that would result in
> > a lot of duplicated strings and increased memory usage.
> 
> I didn't measure how much more memory would be used, though.

> On Fri, Sep 20, 2019 at 08:14:07PM +0200, SZEDER Gábor wrote:
>> On Fri, Sep 20, 2019 at 08:13:02PM +0200, SZEDER Gábor wrote:
>>>> If the (re)introduced leak doesn't impact performance and memory
>>>> usage too much then duplicating tip_name again in name_rev() or
>>>> rather your new create_or_update_name() would likely make the
>>>> lifetimes of those string buffers easier to manage.
>>>
>>> Yeah, the easiest would be when each 'struct rev_name' in the commit
>>> slab would have its own 'tip_name' string, but that would result in
>>> a lot of duplicated strings and increased memory usage.
>>
>> I didn't measure how much more memory would be used, though.
>
> So, I tried the patch below to give each 'struct rev_name' instance
> its own copy of 'tip_name', and the memory usage of 'git name-rev
> --all' usually increased.
>
> The increase depends on how many merges and how many refs there are
> compared to the number of commits: the fewer merges and refs, the
> higher the more the memory usage increased:
>
>   linux:         +4.8%
>   gcc:           +7.2%
>   gecko-dev:     +9.2%
>   webkit:       +12.4%
>   llvm-project: +19.0%

>
>
>  --- >8 ---
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index 6969af76c4..62ab78242b 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -88,6 +88,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>  		set_commit_rev_name(commit, name);
>  		goto copy_data;
>  	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
> +		free((char*) name->tip_name);
>  copy_data:
>  		name->tip_name = tip_name;

>  		name->taggerdate = taggerdate;
> @@ -106,21 +107,19 @@ static void name_rev(struct commit *start_commit,
>  {
>  	struct commit_list *list = NULL;
>  	const char *tip_name;
> -	char *to_free = NULL;
>
>  	parse_commit(start_commit);
>  	if (start_commit->date < cutoff)
>  		return;
>
>  	if (deref) {
> -		tip_name = to_free = xstrfmt("%s^0", start_tip_name);
> -		free((char*) start_tip_name);
> +		tip_name = xstrfmt("%s^0", start_tip_name);
>  	} else
> -		tip_name = start_tip_name;
> +		tip_name = strdup(start_tip_name);

>
>  	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
>  				   from_tag)) {
> -		free(to_free);
> +		free((char*) tip_name);
>  		return;
>  	}
>
> @@ -139,7 +138,6 @@ static void name_rev(struct commit *start_commit,
>  			struct commit *parent = parents->item;
>  			const char *new_name;
>  			int generation, distance;
> -			const char *new_name_to_free = NULL;
>
>  			parse_commit(parent);
>  			if (parent->date < cutoff)
> @@ -159,11 +157,10 @@ static void name_rev(struct commit *start_commit,
>  					new_name = xstrfmt("%.*s^%d", (int)len,
>  							   name->tip_name,
>  							   parent_number);
> -				new_name_to_free = new_name;
>  				generation = 0;
>  				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
>  			} else {
> -				new_name = name->tip_name;
> +				new_name = strdup(name->tip_name);

>  				generation = name->generation + 1;
>  				distance = name->distance + 1;
>  			}
> @@ -174,7 +171,7 @@ static void name_rev(struct commit *start_commit,
>  				last_new_parent = commit_list_append(parent,
>  						  last_new_parent);
>  			else
> -				free((char*) new_name_to_free);
> +				free((char*) new_name);
>  		}
>
>  		*last_new_parent = list;
> @@ -313,7 +310,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
> -		name_rev(commit, xstrdup(path), taggerdate, from_tag, deref);
> +		name_rev(commit, path, taggerdate, from_tag, deref);
>  	}
>  	return 0;
>  }
>

> Am 21.09.19 um 11:57 schrieb SZEDER Gábor:
> > On Fri, Sep 20, 2019 at 08:14:07PM +0200, SZEDER Gábor wrote:
> >> On Fri, Sep 20, 2019 at 08:13:02PM +0200, SZEDER Gábor wrote:
> >>>> If the (re)introduced leak doesn't impact performance and memory
> >>>> usage too much then duplicating tip_name again in name_rev() or
> >>>> rather your new create_or_update_name() would likely make the
> >>>> lifetimes of those string buffers easier to manage.
> >>>
> >>> Yeah, the easiest would be when each 'struct rev_name' in the commit
> >>> slab would have its own 'tip_name' string, but that would result in
> >>> a lot of duplicated strings and increased memory usage.
> >>
> >> I didn't measure how much more memory would be used, though.
> >
> > So, I tried the patch below to give each 'struct rev_name' instance
> > its own copy of 'tip_name', and the memory usage of 'git name-rev
> > --all' usually increased.
> >
> > The increase depends on how many merges and how many refs there are
> > compared to the number of commits: the fewer merges and refs, the
> > higher the more the memory usage increased:
> >
> >   linux:         +4.8%
> >   gcc:           +7.2%
> >   gecko-dev:     +9.2%
> >   webkit:       +12.4%
> >   llvm-project: +19.0%
> 
> Is that the overall memory usage or just for struct rev_name instances
> and tip_name strings?

> > git.git is the exception with its unusually high number of merge
> > commits (about 25%), and the memory usage decresed by 4.4%.
> 
> Interesting.
> 
> I wonder why regular commits even need a struct name_rev.  Shouldn't
> only tips and roots need ones?  And perhaps merges and occasional
> regular "checkpoint" commits, to avoid too many duplicate traversals.

> >  --- >8 ---
> >
> > diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> > index 6969af76c4..62ab78242b 100644
> > --- a/builtin/name-rev.c
> > +++ b/builtin/name-rev.c
> > @@ -88,6 +88,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,
> >  		set_commit_rev_name(commit, name);
> >  		goto copy_data;
> >  	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
> > +		free((char*) name->tip_name);
> >  copy_data:
> >  		name->tip_name = tip_name;
> 
> I would have expected a xstrdup() call here.

> >  		name->taggerdate = taggerdate;
> > @@ -106,21 +107,19 @@ static void name_rev(struct commit *start_commit,
> >  {
> >  	struct commit_list *list = NULL;
> >  	const char *tip_name;
> > -	char *to_free = NULL;
> >
> >  	parse_commit(start_commit);
> >  	if (start_commit->date < cutoff)
> >  		return;
> >
> >  	if (deref) {
> > -		tip_name = to_free = xstrfmt("%s^0", start_tip_name);
> > -		free((char*) start_tip_name);
> > +		tip_name = xstrfmt("%s^0", start_tip_name);
> >  	} else
> > -		tip_name = start_tip_name;
> > +		tip_name = strdup(start_tip_name);
> 
> This would not be needed with the central xstrdup() call mentioned above.
> 
> >
> >  	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
> >  				   from_tag)) {
> > -		free(to_free);
> > +		free((char*) tip_name);
> >  		return;
> >  	}
> >
> > @@ -139,7 +138,6 @@ static void name_rev(struct commit *start_commit,
> >  			struct commit *parent = parents->item;
> >  			const char *new_name;
> >  			int generation, distance;
> > -			const char *new_name_to_free = NULL;
> >
> >  			parse_commit(parent);
> >  			if (parent->date < cutoff)
> > @@ -159,11 +157,10 @@ static void name_rev(struct commit *start_commit,
> >  					new_name = xstrfmt("%.*s^%d", (int)len,
> >  							   name->tip_name,
> >  							   parent_number);
> > -				new_name_to_free = new_name;
> >  				generation = 0;
> >  				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
> >  			} else {
> > -				new_name = name->tip_name;
> > +				new_name = strdup(name->tip_name);
> 
> ... and neither would this.
> 
> Sure the xstrfmt() result would be duplicated instead of being reused, but
> that doesn't increase memory usage overall.
> 
> >  				generation = name->generation + 1;
> >  				distance = name->distance + 1;
> >  			}
> > @@ -174,7 +171,7 @@ static void name_rev(struct commit *start_commit,
> >  				last_new_parent = commit_list_append(parent,
> >  						  last_new_parent);
> >  			else
> > -				free((char*) new_name_to_free);
> > +				free((char*) new_name);
> >  		}
> >
> >  		*last_new_parent = list;
> > @@ -313,7 +310,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
> >  		if (taggerdate == TIME_MAX)
> >  			taggerdate = commit->date;
> >  		path = name_ref_abbrev(path, can_abbreviate_output);
> > -		name_rev(commit, xstrdup(path), taggerdate, from_tag, deref);
> > +		name_rev(commit, path, taggerdate, from_tag, deref);
> >  	}
> >  	return 0;
> >  }
> >

> On Sat, Sep 21, 2019 at 02:37:18PM +0200, René Scharfe wrote:
>> Am 21.09.19 um 11:57 schrieb SZEDER Gábor:
>>> On Fri, Sep 20, 2019 at 08:14:07PM +0200, SZEDER Gábor wrote:
>>>> On Fri, Sep 20, 2019 at 08:13:02PM +0200, SZEDER Gábor wrote:
>>>>>> If the (re)introduced leak doesn't impact performance and memory
>>>>>> usage too much then duplicating tip_name again in name_rev() or
>>>>>> rather your new create_or_update_name() would likely make the
>>>>>> lifetimes of those string buffers easier to manage.
>>>>>
>>>>> Yeah, the easiest would be when each 'struct rev_name' in the commit
>>>>> slab would have its own 'tip_name' string, but that would result in
>>>>> a lot of duplicated strings and increased memory usage.
>>>>
>>>> I didn't measure how much more memory would be used, though.
>>>
>>> So, I tried the patch below to give each 'struct rev_name' instance
>>> its own copy of 'tip_name', and the memory usage of 'git name-rev
>>> --all' usually increased.
>>>
>>> The increase depends on how many merges and how many refs there are
>>> compared to the number of commits: the fewer merges and refs, the
>>> higher the more the memory usage increased:
>>>
>>>   linux:         +4.8%
>>>   gcc:           +7.2%
>>>   gecko-dev:     +9.2%
>>>   webkit:       +12.4%
>>>   llvm-project: +19.0%
>>
>> Is that the overall memory usage or just for struct rev_name instances
>> and tip_name strings?
>
> It's overall memory usage, the avarage of five runs of:
>
>   /usr/bin/time --format='%M' ~/src/git/git name-rev --all
>
>> And how much is that in absolute terms?
>
> git:     29801 ->  28514
> linux:  317018 -> 332218
> gcc:    106462 -> 114140
> gecko:  315448 -> 344486
> webkit:  55847 ->  62780
> llvm:   112867 -> 134384

>> (Perhaps
>> it's worth it to get the memory ownership question off the table at
>> least during the transformation to iterative processing.)
>
> I looked into it only because I got curious, but other than that I
> will definitely play the "beyond the scope of this patch series" card
> :)

>> I wonder why regular commits even need a struct name_rev.  Shouldn't
>> only tips and roots need ones?  And perhaps merges and occasional
>> regular "checkpoint" commits, to avoid too many duplicate traversals.
>
> The 'struct rev_name' holds all info that's necessary to determine the
> commit's name.  It seems to be much simpler to just attach one to each
> commit and then retrieve it from the commit slab when printing the
> name of the commit than to come up with an algorithm where only a
> sleect set of commits get a 'struct rev_name', including how to access
> those when naming a commit that doesn't have one.

>>>  --- >8 ---
>>>
>>> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
>>> index 6969af76c4..62ab78242b 100644
>>> --- a/builtin/name-rev.c
>>> +++ b/builtin/name-rev.c
>>> @@ -88,6 +88,7 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>>>  		set_commit_rev_name(commit, name);
>>>  		goto copy_data;
>>>  	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
>>> +		free((char*) name->tip_name);
>>>  copy_data:
>>>  		name->tip_name = tip_name;
>>
>> I would have expected a xstrdup() call here.
>
> But then we'd needed to release the results of all those xstrfmt()
> calls at the callsites of create_or_update_name(), so instead of those
> strdup() calls that you deem unnecessary we would need additional
> free() calls.

> > It's overall memory usage, the avarage of five runs of:
> >
> >   /usr/bin/time --format='%M' ~/src/git/git name-rev --all
> >
> >> And how much is that in absolute terms?
> >
> > git:     29801 ->  28514
> > linux:  317018 -> 332218
> > gcc:    106462 -> 114140
> > gecko:  315448 -> 344486
> > webkit:  55847 ->  62780
> > llvm:   112867 -> 134384
> 
> I only have the first two handy, and I get numbers like this with
> master:
> 
> git, lots of branches with long names: 3075476
> git, local clone, single branch:       1349016
> linux, single branch:                  1520468
> 
> O_o

> On Mon, Sep 23, 2019 at 08:43:11PM +0200, René Scharfe wrote:
>>> It's overall memory usage, the avarage of five runs of:
>>>
>>>   /usr/bin/time --format='%M' ~/src/git/git name-rev --all
>>>
>>>> And how much is that in absolute terms?
>>>
>>> git:     29801 ->  28514
>>> linux:  317018 -> 332218
>>> gcc:    106462 -> 114140
>>> gecko:  315448 -> 344486
>>> webkit:  55847 ->  62780
>>> llvm:   112867 -> 134384
>>
>> I only have the first two handy, and I get numbers like this with
>> master:
>>
>> git, lots of branches with long names: 3075476
>> git, local clone, single branch:       1349016
>> linux, single branch:                  1520468
>>
>> O_o
>
> I have commit graph present and enabled.  Without that I get approx.
> the same memory usage in my linux repo as you did (along with much
> longer runtime).

> -- >8 --
> Subject: [PATCH] name-rev: use FLEX_ARRAY for tip_name in struct rev_name
> 
> Give each rev_name its very own tip_name string.  This simplifies memory
> ownership, as callers of name_rev() only have to make sure the tip_name
> parameter exists for the duration of the call and don't have to preserve
> it for the whole run of the program.
> 
> It also saves four or eight bytes per object because this change removes
> the pointer indirection.  Memory usage is still higher for linear
> histories that previously shared the same tip_name value between
> multiple name_rev instances.

> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  builtin/name-rev.c | 18 ++++++++----------
>  1 file changed, 8 insertions(+), 10 deletions(-)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index c785fe16ba..4162fb29ee 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -12,11 +12,11 @@
>  #define CUTOFF_DATE_SLOP 86400 /* one day */
> 
>  typedef struct rev_name {
> -	const char *tip_name;
>  	timestamp_t taggerdate;
>  	int generation;
>  	int distance;
>  	int from_tag;
> +	char tip_name[FLEX_ARRAY];
>  } rev_name;
> 
>  define_commit_slab(commit_rev_name, struct rev_name *);
> @@ -97,17 +97,14 @@ static void name_rev(struct commit *commit,
>  			die("generation: %d, but deref?", generation);
>  	}
> 
> -	if (name == NULL) {
> -		name = xmalloc(sizeof(rev_name));
> -		set_commit_rev_name(commit, name);
> -		goto copy_data;
> -	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
> -copy_data:
> -		name->tip_name = tip_name;
> +	if (!name || is_better_name(name, taggerdate, distance, from_tag)) {
> +		free(name);
> +		FLEX_ALLOC_STR(name, tip_name, tip_name);
>  		name->taggerdate = taggerdate;
>  		name->generation = generation;
>  		name->distance = distance;
>  		name->from_tag = from_tag;
> +		set_commit_rev_name(commit, name);
>  	} else {
>  		free(to_free);
>  		return;
> @@ -131,12 +128,14 @@ static void name_rev(struct commit *commit,
>  			name_rev(parents->item, new_name, taggerdate, 0,
>  				 distance + MERGE_TRAVERSAL_WEIGHT,
>  				 from_tag, 0);
> +			free(new_name);
>  		} else {
>  			name_rev(parents->item, tip_name, taggerdate,
>  				 generation + 1, distance + 1,
>  				 from_tag, 0);
>  		}
>  	}
> +	free(to_free);
>  }
> 
>  static int subpath_matches(const char *path, const char *filter)
> @@ -270,8 +269,7 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  		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,
> -			 from_tag, deref);
> +		name_rev(commit, path, taggerdate, 0, 0, from_tag, deref);
>  	}
>  	return 0;
>  }
> --
> 2.23.0

> On Mon, Sep 23, 2019 at 09:55:11PM +0200, René Scharfe wrote:
>> -- >8 --
>> Subject: [PATCH] name-rev: use FLEX_ARRAY for tip_name in struct rev_name
>>
>> Give each rev_name its very own tip_name string.  This simplifies memory
>> ownership, as callers of name_rev() only have to make sure the tip_name
>> parameter exists for the duration of the call and don't have to preserve
>> it for the whole run of the program.
>>
>> It also saves four or eight bytes per object because this change removes
>> the pointer indirection.  Memory usage is still higher for linear
>> histories that previously shared the same tip_name value between
>> multiple name_rev instances.
>
> Besides looking at memory usage, have you run any performance
> benchmarks?  Here it seems to make 'git name-rev --all >out' slower by
> 17% in the git repo and by 19.5% in the linux repo.

> Am 23.09.19 um 22:47 schrieb SZEDER Gábor:
> > On Mon, Sep 23, 2019 at 09:55:11PM +0200, René Scharfe wrote:
> >> -- >8 --
> >> Subject: [PATCH] name-rev: use FLEX_ARRAY for tip_name in struct rev_name
> >>
> >> Give each rev_name its very own tip_name string.  This simplifies memory
> >> ownership, as callers of name_rev() only have to make sure the tip_name
> >> parameter exists for the duration of the call and don't have to preserve
> >> it for the whole run of the program.
> >>
> >> It also saves four or eight bytes per object because this change removes
> >> the pointer indirection.  Memory usage is still higher for linear
> >> histories that previously shared the same tip_name value between
> >> multiple name_rev instances.
> >
> > Besides looking at memory usage, have you run any performance
> > benchmarks?  Here it seems to make 'git name-rev --all >out' slower by
> > 17% in the git repo and by 19.5% in the linux repo.
> 
> Did measure now; I also see a slowdown with my patch applied:

>>> @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>>>  	if (o && o->type == OBJ_COMMIT) {
>>>  		struct commit *commit = (struct commit *)o;
>>>  		int from_tag = starts_with(path, "refs/tags/");
>>> +		const char *tip_name;
>>
>> This should not be const because you allocate the buffer it points to
>> right here in the function, in each execution path.
>
> Marking it as const indicates that this function doesn't modify the
> buffer where the pointer points at.

> Am 20.09.19 um 20:13 schrieb SZEDER Gábor:
> >>> @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
> >>>  	if (o && o->type == OBJ_COMMIT) {
> >>>  		struct commit *commit = (struct commit *)o;
> >>>  		int from_tag = starts_with(path, "refs/tags/");
> >>> +		const char *tip_name;
> >>
> >> This should not be const because you allocate the buffer it points to
> >> right here in the function, in each execution path.
> >
> > Marking it as const indicates that this function doesn't modify the
> > buffer where the pointer points at.
> 
> Right, and that's at odds with this code:
> 
> >>> +		if (deref)
> >>> +			tip_name = xstrfmt("%s^0", path);
> >>> +		else
> >>> +			tip_name = xstrdup(path);
> 
> ... which allocates said memory and writes a string to it.

> On Sat, Sep 21, 2019 at 02:37:05PM +0200, René Scharfe wrote:
>> Am 20.09.19 um 20:13 schrieb SZEDER Gábor:
>>>>> @@ -280,12 +269,16 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>>>>>  	if (o && o->type == OBJ_COMMIT) {
>>>>>  		struct commit *commit = (struct commit *)o;
>>>>>  		int from_tag = starts_with(path, "refs/tags/");
>>>>> +		const char *tip_name;
>>>>
>>>> This should not be const because you allocate the buffer it points to
>>>> right here in the function, in each execution path.
>>>
>>> Marking it as const indicates that this function doesn't modify the
>>> buffer where the pointer points at.
>>
>> Right, and that's at odds with this code:
>>
>>>>> +		if (deref)
>>>>> +			tip_name = xstrfmt("%s^0", path);
>>>>> +		else
>>>>> +			tip_name = xstrdup(path);
>>
>> ... which allocates said memory and writes a string to it.
>
> ... before assigning it to the const pointer.
>

> At the beginning of the recursive name_rev() function it parses the
> commit it got as parameter, and returns early if the commit is older
> than a cutoff limit.
>
> Restructure this so the caller parses the commit and checks its date,
> and doesn't invoke name_rev() if the commit to be passed as parameter
> is older than the cutoff, i.e. both name_ref() before calling
> name_rev() and name_rev() itself as it iterates over the parent
> commits.
>
> This makes eliminating the recursion a bit easier to follow, and it
> will be moved back to name_rev() after the recursion is eliminated.
>
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 29 ++++++++++++++++-------------
>  1 file changed, 16 insertions(+), 13 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index 42cea5c881..99643aa4dc 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -107,11 +107,6 @@ static void name_rev(struct commit *commit,
>  	struct commit_list *parents;
>  	int parent_number = 1;
>
> -	parse_commit(commit);
> -
> -	if (commit->date < cutoff)
> -		return;
> -
>  	if (!create_or_update_name(commit, tip_name, taggerdate, generation,
>  				   distance, from_tag))
>  		return;
> @@ -119,6 +114,12 @@ static void name_rev(struct commit *commit,
>  	for (parents = commit->parents;
>  			parents;
>  			parents = parents->next, parent_number++) {
> +		struct commit *parent = parents->item;
> +
> +		parse_commit(parent);
> +		if (parent->date < cutoff)
> +			continue;
> +
>  		if (parent_number > 1) {
>  			size_t len;
>  			char *new_name;
> @@ -131,11 +132,11 @@ static void name_rev(struct commit *commit,
>  				new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
>  						   parent_number);
>

> -			name_rev(parents->item, new_name, taggerdate, 0,
> +			name_rev(parent, new_name, taggerdate, 0,
>  				 distance + MERGE_TRAVERSAL_WEIGHT,
>  				 from_tag);
>  		} else {
> -			name_rev(parents->item, tip_name, taggerdate,
> +			name_rev(parent, tip_name, taggerdate,
>  				 generation + 1, distance + 1,
>  				 from_tag);
>  		}
> @@ -269,16 +270,18 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>  	if (o && o->type == OBJ_COMMIT) {
>  		struct commit *commit = (struct commit *)o;
>  		int from_tag = starts_with(path, "refs/tags/");
> -		const char *tip_name;
>
>  		if (taggerdate == TIME_MAX)
>  			taggerdate = commit->date;
>  		path = name_ref_abbrev(path, can_abbreviate_output);
> -		if (deref)
> -			tip_name = xstrfmt("%s^0", path);
> -		else
> -			tip_name = xstrdup(path);
> -		name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);
> +		if (commit->date >= cutoff) {
> +			const char *tip_name;
> +			if (deref)
> +				tip_name = xstrfmt("%s^0", path);
> +			else
> +				tip_name = xstrdup(path);

> +			name_rev(commit, tip_name, taggerdate, 0, 0, from_tag);
> +		}
>  	}
>  	return 0;
>  }
>

> In a later patch in this series we'll want to do this in two places.
> 
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 40 +++++++++++++++++++++++++++-------------
>  1 file changed, 27 insertions(+), 13 deletions(-)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index dec2228cc7..cb8ac2fa64 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -75,12 +75,36 @@ static int is_better_name(struct rev_name *name,
>  	return 0;
>  }
>  
> +static struct rev_name *create_or_update_name(struct commit *commit,
> +					      const char *tip_name,
> +					      timestamp_t taggerdate,
> +					      int generation, int distance,
> +					      int from_tag)
> +{
> +	struct rev_name *name = get_commit_rev_name(commit);
> +
> +	if (name == NULL) {
> +		name = xmalloc(sizeof(*name));
> +		set_commit_rev_name(commit, name);
> +		goto copy_data;
> +	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
> +copy_data:
> +		name->tip_name = tip_name;
> +		name->taggerdate = taggerdate;
> +		name->generation = generation;
> +		name->distance = distance;
> +		name->from_tag = from_tag;
> +
> +		return name;
> +	} else
> +		return NULL;
> +}
> +
>  static void name_rev(struct commit *commit,
>  		const char *tip_name, timestamp_t taggerdate,
>  		int generation, int distance, int from_tag,
>  		int deref)
>  {
> -	struct rev_name *name = get_commit_rev_name(commit);

>  	struct commit_list *parents;
>  	int parent_number = 1;
>  	char *to_free = NULL;
> @@ -97,18 +121,8 @@ static void name_rev(struct commit *commit,
>  			die("generation: %d, but deref?", generation);
>  	}
>  
> -	if (name == NULL) {
> -		name = xmalloc(sizeof(*name));
> -		set_commit_rev_name(commit, name);
> -		goto copy_data;
> -	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
> -copy_data:
> -		name->tip_name = tip_name;
> -		name->taggerdate = taggerdate;
> -		name->generation = generation;
> -		name->distance = distance;
> -		name->from_tag = from_tag;
> -	} else {
> +	if (!create_or_update_name(commit, tip_name, taggerdate, generation,
> +				   distance, from_tag)) {

> The name_rev() function's 'tip_name' parameter is a freshly
> xstrdup()ed string, so when name_rev() invokes:
> 
>   tip_name = xstrfmt("%s^0", tip_name);
> 
> then the original 'tip_name' string is leaked.
> 
> Make sure that this string is free()d after it has been used as input
> for that xstrfmt() call.
> 
> This only happens when name_rev() is invoked with a tag, i.e.
> relatively infrequently in a usual repository, so any reduction in
> memory usage is lost in the noise.
> 
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 10 +++++++---
>  1 file changed, 7 insertions(+), 3 deletions(-)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index e202835129..f867d45f0b 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -101,18 +101,22 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>  }
>  
>  static void name_rev(struct commit *start_commit,
> -		const char *tip_name, timestamp_t taggerdate,
> +		const char *start_tip_name, timestamp_t taggerdate,
>  		int from_tag, int deref)
>  {
>  	struct commit_list *list = NULL;
> +	const char *tip_name;
>  	char *to_free = NULL;
>  
>  	parse_commit(start_commit);
>  	if (start_commit->date < cutoff)
>  		return;
>  
> -	if (deref)
> -		tip_name = to_free = xstrfmt("%s^0", tip_name);
> +	if (deref) {
> +		tip_name = to_free = xstrfmt("%s^0", start_tip_name);
> +		free((char*) start_tip_name);
> +	} else
> +		tip_name = start_tip_name;
>  
>  	if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
>  				   from_tag)) {
> -- 
> 2.23.0.331.g4e51dcdf11
> 

> The loop iterating over the parent commits in the name_rev() function
> contains two xstrfmt() calls, and their result is leaked if the parent
> commit is not processed further (because that parent has already been
> visited before, and this further visit doesn't result in a better name
> for its ancestors).
> 
> Make sure that the result of those xstrfmt() calls is free()d if the
> parent commit is not processed further.
> 
> This results in slightly but measurably lower memory usage: the
> avarage maximum resident size of 5 'git name-rev --all' invocations in
> 'linux.git' shrinks from 3256124kB to 319990kB, just about 2% less.
> 
> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 4 ++++
>  1 file changed, 4 insertions(+)
> 
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index f867d45f0b..d65de04918 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -139,6 +139,7 @@ static void name_rev(struct commit *start_commit,
>  			struct commit *parent = parents->item;
>  			const char *new_name;
>  			int generation, distance;
> +			const char *new_name_to_free = NULL;
>  
>  			parse_commit(parent);
>  			if (parent->date < cutoff)
> @@ -158,6 +159,7 @@ static void name_rev(struct commit *start_commit,
>  					new_name = xstrfmt("%.*s^%d", (int)len,
>  							   name->tip_name,
>  							   parent_number);
> +				new_name_to_free = new_name;
>  				generation = 0;
>  				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
>  			} else {
> @@ -171,6 +173,8 @@ static void name_rev(struct commit *start_commit,
>  						  from_tag))
>  				last_new_parent = commit_list_append(parent,
>  						  last_new_parent);
> +			else
> +				free((char*) new_name_to_free);
>  		}
>  
>  		*last_new_parent = list;
> -- 
> 2.23.0.331.g4e51dcdf11
> 

> 'git name-rev' is implemented using a recursive algorithm, and,
> consequently, it can segfault in deep histories (e.g. WebKit), and
> thanks to a test case demonstrating this limitation every test run
> results in a dmesg entry logging the segfaulting git process.
> 
> This patch series eliminates the recursion.

> Patches 7-11 are preparatory refactorings that are supposed to make
> this series easier to follow, and make patch 12, the one finally
> eliminating the recursion, somewhat shorter, and even much shorter
> when viewed with '--ignore-all-space'.  Patch 13 cleans up after those
> preparatory steps.

> On 9/19/2019 5:46 PM, SZEDER Gábor wrote:
> > 'git name-rev' is implemented using a recursive algorithm, and,
> > consequently, it can segfault in deep histories (e.g. WebKit), and
> > thanks to a test case demonstrating this limitation every test run
> > results in a dmesg entry logging the segfaulting git process.
> > 
> > This patch series eliminates the recursion.
> 
> A noble goal! Recursion into commit history is much easier to get
> stack overflows than when we recurse into the directory hierarchy.
> 
> > Patches 1-5 and 14-15 are while-at-it cleanups I noticed on the way,
> > and patch 6 improves test coverage.
> 
> These cleanups are nice, and I think I followed them pretty closely.
>  
> > Patches 7-11 are preparatory refactorings that are supposed to make
> > this series easier to follow, and make patch 12, the one finally
> > eliminating the recursion, somewhat shorter, and even much shorter
> > when viewed with '--ignore-all-space'.  Patch 13 cleans up after those
> > preparatory steps.
> 
> I responded to several of these, mostly with questions and not actual
> recommendations. I do want to apply your patches locally so I can try
> this --ignore-all-space trick to really be sure patch 12 is doing the
> right thing.

> From: René Scharfe <l.s.r@web.de>
>
> get_name_rev() basically open-codes strip_suffix() before adding a
> string to a strbuf.
>
> Let's use the strbuf right from the beginning, i.e. add the whole
> string to the strbuf and then use strbuf_strip_suffix(), making the
> code more idiomatic.
>
> [TODO: René's signoff!]

> Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> ---
>  builtin/name-rev.c | 7 +++----
>  1 file changed, 3 insertions(+), 4 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index b0f0776947..15919adbdb 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -321,11 +321,10 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
>  	if (!n->generation)
>  		return n->tip_name;
>  	else {
> -		int len = strlen(n->tip_name);
> -		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
> -			len -= 2;
>  		strbuf_reset(buf);
> -		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
> +		strbuf_addstr(buf, n->tip_name);
> +		strbuf_strip_suffix(buf, "^0");
> +		strbuf_addf(buf, "~%d", n->generation);
>  		return buf->buf;
>  	}
>  }
>

> The 'check_describe' helper function runs 'git describe' outside of
> 'test_expect_success' blocks, with extra hand-rolled code to record
> and examine its exit code.
> 
> Update this helper and move the 'git decribe' invocation inside the
> 'test_expect_success' block.

>  		if (create_or_update_name(parent, new_name, taggerdate,
> -					  new_generation, new_distance,
> +					  generation, distance,
>  					  from_tag))
> -			name_rev(parent, new_name, taggerdate,
> -				 new_generation, new_distance, from_tag);
> +			name_rev(parent, new_name, taggerdate, from_tag);
>  	}
>  }

>  			if (create_or_update_name(commit, tip_name, taggerdate,
>  						  0, 0, from_tag))
> -				name_rev(commit, tip_name, taggerdate, 0, 0,
> +				name_rev(commit, tip_name, taggerdate,
>  					 from_tag);
>  			else
>  				free(to_free);

> Earlier patches in this series moved a couple of conditions from the
> recursive name_rev() function into its caller name_ref(), for no other
> reason than to make eliminating the recursion a bit easier to follow.
> 
> Since the previous patch name_rev() is not recursive anymore, so let's
> move all those conditions back into name_rev().

> > Earlier patches in this series moved a couple of conditions from the
> > recursive name_rev() function into its caller name_ref(), for no other
> > reason than to make eliminating the recursion a bit easier to follow.
> > 
> > Since the previous patch name_rev() is not recursive anymore, so let's
> > move all those conditions back into name_rev().
> 
> I don't really see the need for this code movement, to be honest. There
> is no big difference in doing the checks in one place or the other, and
> if you ask me, it might even be better to do it in the caller of
> name_rev(), and leave name_rev() to handle only the naming.

> > Note that this slightly changes the order of lines in the output of
> > 'git name-rev --all', usually swapping two lines every 35 lines in
> > git.git or every 150 lines in linux.git.  This shouldn't matter in
> > practice, because the output has always been unordered anyway.
> 
> I didn't verify that the changing of order is fine, but other than that,
> this patch looks great.

> > -static void name_rev(struct commit *commit,
> > +static void name_rev(struct commit *start_commit,
> >  		const char *tip_name, timestamp_t taggerdate,
> >  		int from_tag)
> 
> There are many changes from tip_name to name->tip_name in this function
> that mean that tip_name is no longer used within this function. Should
> this cleanup have been done in one of the earlier patches?

> 'git name-rev' is implemented using a recursive algorithm, and,
> consequently, it can segfault in deep histories (e.g. WebKit), and
> thanks to a test case demonstrating this limitation every test run
> results in a dmesg entry logging the segfaulting git process.
>
> This patch series eliminates the recursion.
>
> Patches 1-5 are while-at-it cleanups I noticed on the way, and patch 6
> improves test coverage.  Patches 7-11 are preparatory refactorings
> that are supposed to make this series easier to follow, and make patch
> 12, the one finally eliminating the recursion, somewhat shorter, and
> even much shorter when viewed with '--ignore-all-space'.  Patch 13
> cleans up after those preparatory steps.
>
> Changes since v1:
>
>   - Patch 12 now eliminates the recursion using a LIFO 'prio_queue'
>     instead of a 'commit_list' to avoid any performance penalty.
>
>   - Commit message updates, clarifications, typofixes, missing
>     signoffs, etc., most notably in patches 6 and 12.
>
>   - Updated ASCII art history graphs.
>
>   - Replaced the strbuf_suffix() cleanup in patch 3 with René's
>     suggestion; now that patch needs his signoff.
>
>   - Dropped the last two patches plugging memory leaks; René's plan
>     to clean up memory ownership looked more promising, and that
>     would make these two dropped patches moot anyway.
>
> v1: https://public-inbox.org/git/20190919214712.7348-1-szeder.dev@gmail.com/T/#u
>
> René Scharfe (1):
>   name-rev: use strbuf_strip_suffix() in get_rev_name()
>
> SZEDER Gábor (12):
>   t6120-describe: correct test repo history graph in comment
>   t6120-describe: modernize the 'check_describe' helper
>   name-rev: avoid unnecessary cast in name_ref()
>   name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
>   t6120: add a test to cover inner conditions in 'git name-rev's
>     name_rev()
>   name-rev: extract creating/updating a 'struct name_rev' into a helper
>   name-rev: pull out deref handling from the recursion
>   name-rev: restructure parsing commits and applying date cutoff
>   name-rev: restructure creating/updating 'struct rev_name' instances
>   name-rev: drop name_rev()'s 'generation' and 'distance' parameters
>   name-rev: eliminate recursion in name_rev()
>   name-rev: cleanup name_ref()
>
>  builtin/name-rev.c  | 147 +++++++++++++++++++++++++++++---------------
>  t/t6120-describe.sh |  72 +++++++++++++++++-----
>  2 files changed, 153 insertions(+), 66 deletions(-)
>
> Range-diff:
>  1:  673da20e3d !  1:  8d70ed050d t6120-describe: correct test repo history graph in comment
>     @@ t/t6120-describe.sh
>      -test_description='test describe
>      +test_description='test describe'
>      +
>     -+#       ,---o----o----o-----.
>     -+#      /   D,R   e           \
>     -+#  o--o-----o-------------o---o----x
>     -+#      \    B            /
>     -+#       `---o----o----o-'
>     -+#                A    c
>     ++#  o---o-----o----o----o-------o----x
>     ++#       \   D,R   e           /
>     ++#        \---o-------------o-'
>     ++#         \  B            /
>     ++#          `-o----o----o-'
>     ++#                 A    c
>     ++#
>     ++# First parent of a merge commit is on the same line, second parent below.
>
>      -                       B
>      -        .--------------o----o----o----x
>  2:  05df899693 =  2:  3720b6859d t6120-describe: modernize the 'check_describe' helper
>  3:  7b0227cfea !  3:  ad2f2eee68 name-rev: use strip_suffix() in get_rev_name()
>     @@
>       ## Metadata ##
>     -Author: SZEDER Gábor <szeder.dev@gmail.com>
>     +Author: René Scharfe <l.s.r@web.de>
>
>       ## Commit message ##
>     -    name-rev: use strip_suffix() in get_rev_name()
>     +    name-rev: use strbuf_strip_suffix() in get_rev_name()
>
>     -    Use strip_suffix() instead of open-coding it, making the code more
>     -    idiomatic.
>     +    get_name_rev() basically open-codes strip_suffix() before adding a
>     +    string to a strbuf.
>
>     +    Let's use the strbuf right from the beginning, i.e. add the whole
>     +    string to the strbuf and then use strbuf_strip_suffix(), making the
>     +    code more idiomatic.
>     +
>     +    [TODO: René's signoff!]
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>     @@ builtin/name-rev.c: static const char *get_rev_name(const struct object *o, stru
>      -		int len = strlen(n->tip_name);
>      -		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
>      -			len -= 2;
>     -+		size_t len;
>     -+		strip_suffix(n->tip_name, "^0", &len);
>       		strbuf_reset(buf);
>      -		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
>     -+		strbuf_addf(buf, "%.*s~%d", (int) len, n->tip_name,
>     -+			    n->generation);
>     ++		strbuf_addstr(buf, n->tip_name);
>     ++		strbuf_strip_suffix(buf, "^0");
>     ++		strbuf_addf(buf, "~%d", n->generation);
>       		return buf->buf;
>       	}
>       }
>  4:  40faecdc2a =  4:  c86a2ae2d0 name-rev: avoid unnecessary cast in name_ref()
>  5:  c71df3dadf =  5:  4fc960cc05 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
>  6:  1dcb76072f !  6:  1493cb4484 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()
>     @@ Commit message
>          looks like this:
>
>            if (parent_number > 1) {
>     -        if (generation > 0)
>     -          // do stuff #1
>     -        else
>     -          // do stuff #2
>     +          if (generation > 0)
>     +              // branch #1
>     +              new_name = ...
>     +          else
>     +              // branch #2
>     +              new_name = ...
>     +          name_rev(parent, new_name, ...);
>            } else {
>     -         // do stuff #3
>     +          // branch #3
>     +          name_rev(...);
>            }
>
>          These conditions are not covered properly in the test suite.  As far
>     @@ Commit message
>          command's output, because the repository used in that test script
>          contains several branches and tags pointing somewhere into the middle
>          of the commit DAG, and thus result in a better name for the
>     -    to-be-named commit.  In an early version of this patch series I
>     -    managed to mess up those conditions (every single one of them at
>     -    once!), but the whole test suite still passed successfully.
>     +    to-be-named commit.  This can hide bugs: e.g. by replacing the
>     +    'new_name' parameter of the first recursive name_rev() call with
>     +    'tip_name' (effectively making both branch #1 and #2 a noop) 'git
>     +    name-rev --all' shows thousands of bogus names in the Git repository,
>     +    but the whole test suite still passes successfully.  In an early
>     +    version of a later patch in this series I managed to mess up all three
>     +    branches (at once!), but the test suite still passed.
>
>          So add a new test case that operates on the following history:
>
>     -        -----------master
>     -       /          /
>     -      A----------M2
>     -       \        /
>     -        \---M1-C
>     -         \ /
>     -          B
>     +      A--------------master
>     +       \            /
>     +        \----------M2
>     +         \        /
>     +          \---M1-C
>     +           \ /
>     +            B
>
>     -    and names the commit 'B', where:
>     +    and names the commit 'B' to make sure that all three branches are
>     +    crucial to determine 'B's name:
>
>     -      - The merge commit at master makes sure that the 'do stuff #3'
>     -        affects the final name.
>     +      - There is only a single ref, so all names are based on 'master',
>     +        without any undesired interference from other refs.
>
>     -      - The merge commit M2 make sure that the 'do stuff #1' part
>     -        affects the final name.
>     +      - Each time name_rev() follows the second parent of a merge commit,
>     +        it appends "^2" to the name.  Following 'master's second parent
>     +        right at the start ensures that all commits on the ancestry path
>     +        from 'master' to 'B' have a different base name from the original
>     +        'tip_name' of the very first name_rev() invocation.  Currently,
>     +        while name_rev() is recursive, it doesn't matter, but it will be
>     +        necessary to properly cover all three branches after the recursion
>     +        is eliminated later in this series.
>
>     -      - And M1 makes sure that the 'do stuff #2' part affects the final
>     -        name.
>     +      - Following 'M2's second parent makes sure that branch #2 (i.e. when
>     +        'generation = 0') affects 'B's name.
>     +
>     +      - Following the only parent of the non-merge commit 'C' ensures that
>     +        branch #3 affects 'B's name, and that it increments 'generation'.
>     +
>     +      - Coming from 'C' 'generation' is 1, thus following 'M1's second
>     +        parent makes sure that branch #1 affects 'B's name.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## t/t6120-describe.sh ##
>     -@@ t/t6120-describe.sh: test_expect_success 'describe complains about missing object' '
>     - 	test_must_fail git describe $ZERO_OID
>     +@@ t/t6120-describe.sh: test_expect_success 'name-rev a rev shortly after epoch' '
>     + 	test_cmp expect actual
>       '
>
>     -+#   -----------master
>     -+#  /          /
>     -+# A----------M2
>     -+#  \        /
>     -+#   \---M1-C
>     -+#    \ /
>     -+#     B
>     -+test_expect_success 'test' '
>     ++# A--------------master
>     ++#  \            /
>     ++#   \----------M2
>     ++#    \        /
>     ++#     \---M1-C
>     ++#      \ /
>     ++#       B
>     ++test_expect_success 'name-rev covers all conditions while looking at parents' '
>      +	git init repo &&
>      +	(
>      +		cd repo &&
>     @@ t/t6120-describe.sh: test_expect_success 'describe complains about missing objec
>      +		git checkout master &&
>      +		git merge --no-ff HEAD@{1} &&
>      +
>     -+		git log --graph --oneline &&
>     -+
>      +		echo "$B master^2^2~1^2" >expect &&
>      +		git name-rev $B >actual &&
>      +
>  7:  bdd8378b06 =  7:  fc842e578b name-rev: extract creating/updating a 'struct name_rev' into a helper
>  8:  ce21c351f9 !  8:  7f182503e2 name-rev: pull out deref handling from the recursion
>     @@ Commit message
>          Extract this condition from the recursion into name_rev()'s caller and
>          drop the function's 'deref' parameter.  This makes eliminating the
>          recursion a bit easier to follow, and it will be moved back into
>     -    name_rev() after the recursion is elminated.
>     +    name_rev() after the recursion is eliminated.
>
>          Furthermore, drop the condition that die()s when both 'deref' and
>          'generation' are non-null (which should have been a BUG() to begin
>     @@ Commit message
>
>          Note that this change reintroduces the memory leak that was plugged in
>          in commit 5308224633 (name-rev: avoid leaking memory in the `deref`
>     -    case, 2017-05-04), but a later patch in this series will plug it in
>     -    again.
>     +    case, 2017-05-04), but a later patch (name-rev: restructure
>     +    creating/updating 'struct rev_name' instances) in this series will
>     +    plug it in again.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>  9:  c8acc6b597 !  9:  0cdd40b75b name-rev: restructure parsing commits and applying date cutoff
>     @@ Commit message
>          name_rev() and name_rev() itself as it iterates over the parent
>          commits.
>
>     -    This makes eliminating the recursion a bit easier to follow, and it
>     -    will be moved back to name_rev() after the recursion is eliminated.
>     +    This makes eliminating the recursion a bit easier to follow, and the
>     +    condition moved to name_ref() will be moved back to name_rev() after
>     +    the recursion is eliminated.
>
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
> 10:  c731f27158 ! 10:  e1733e3c56 name-rev: restructure creating/updating 'struct rev_name' instances
>     @@ Commit message
>          At the beginning of the recursive name_rev() function it creates a new
>          'struct rev_name' instance for each previously unvisited commit or, if
>          this visit results in better name for an already visited commit, then
>     -    updates the 'struct rev_name' instance attached to to the commit, or
>     +    updates the 'struct rev_name' instance attached to the commit, or
>          returns early.
>
>          Restructure this so it's caller creates or updates the 'struct
>     @@ Commit message
>          parameter, i.e. both name_ref() before calling name_rev() and
>          name_rev() itself as it iterates over the parent commits.
>
>     -    This makes eliminating the recursion a bit easier to follow, and it
>     -    will be moved back to name_rev() after the recursion is eliminated.
>     +    This makes eliminating the recursion a bit easier to follow, and the
>     +    condition moved to name_ref() will be moved back to name_rev() after
>     +    the recursion is eliminated.
>
>          This change also plugs the memory leak that was temporarily unplugged
>          in the earlier "name-rev: pull out deref handling from the recursion"
> 11:  ba14bde230 ! 11:  bd6e2e6d87 name-rev: drop name_rev()'s 'generation' and 'distance' parameters
>     @@ Commit message
>          'taggerdate' and 'from_tag' parameters as well, but those parameters
>          will be necessary later, after the recursion is eliminated.
>
>     -    Drop name_rev()'s 'generation' and 'distance' parameters.
>     +    Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
> 12:  2d03ac11f3 ! 12:  0cf63c6d64 name-rev: eliminate recursion in name_rev()
>     @@ Commit message
>          segfault when processing a deep history if it exhausts the available
>          stack space.  E.g. running 'git name-rev --all' and 'git name-rev
>          HEAD~100000' in the gcc, gecko-dev, llvm, and WebKit repositories
>     -    results in segfaults on my machine.
>     +    results in segfaults on my machine ('ulimit -s' reports 8192kB of
>     +    stack size limit), and nowadays the former segfaults in the Linux repo
>     +    as well (it reached the necessasry depth sometime between v5.3-rc4 and
>     +    -rc5).
>
>          Eliminate the recursion by inserting the interesting parents into a
>     -    'commit_list' and iteratating until the list becomes empty.
>     +    LIFO 'prio_queue' [1] and iterating until the queue becomes empty.
>
>     -    Note that the order in which the parent commits are added to that list
>     -    is important: they must be inserted at the beginning of the list, and
>     -    their relative order must be kept as well, because otherwise
>     -    performance suffers.
>     +    Note that the parent commits must be added in reverse order to the
>     +    LIFO 'prio_queue', so their relative order is preserved during
>     +    processing, i.e. the first parent should come out first from the
>     +    queue, because otherwise performance greatly suffers on mergy
>     +    histories [2].
>
>          The stacksize-limited test 'name-rev works in a deep repo' in
>          't6120-describe.sh' demonstrated this issue and expected failure.  Now
>     -    the recursion is gone, so flip it to expect success.
>     -
>     -    Also gone are the dmesg entries logging the segfault of the git
>     -    process on every execution of the test suite.
>     -
>     -    Unfortunately, eliminating the recursion comes with a performance
>     -    penaly: 'git name-rev --all' tends to be between 15-20% slower than
>     -    before.
>     +    the recursion is gone, so flip it to expect success.  Also gone are
>     +    the dmesg entries logging the segfault of that segfaulting 'git
>     +    name-rev' process on every execution of the test suite.
>
>          Note that this slightly changes the order of lines in the output of
>          'git name-rev --all', usually swapping two lines every 35 lines in
>     @@ Commit message
>
>          This patch is best viewed with '--ignore-all-space'.
>
>     +    [1] Early versions of this patch used a 'commit_list', resulting in
>     +        ~15% performance penalty for 'git name-rev --all' in 'linux.git',
>     +        presumably because of the memory allocation and release for each
>     +        insertion and removal. Using a LIFO 'prio_queue' has basically no
>     +        effect on performance.
>     +
>     +    [2] We prefer shorter names, i.e. 'v0.1~234' is preferred over
>     +        'v0.1^2~5', meaning that usually following the first parent of a
>     +        merge results in the best name for its ancestors.  So when later
>     +        we follow the remaining parent(s) of a merge, and reach an already
>     +        named commit, then we usually find that we can't give that commit
>     +        a better name, and thus we don't have to visit any of its
>     +        ancestors again.
>     +
>     +        OTOH, if we were to follow the Nth parent of the merge first, then
>     +        the name of all its ancestors would include a corresponding '^N'.
>     +        Those are not the best names for those commits, so when later we
>     +        reach an already named commit following the first parent of that
>     +        merge, then we would have to update the name of that commit and
>     +        the names of all of its ancestors as well.  Consequently, we would
>     +        have to visit many commits several times, resulting in a
>     +        significant slowdown.
>     +
>          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
>
>       ## builtin/name-rev.c ##
>     +@@
>     + #include "tag.h"
>     + #include "refs.h"
>     + #include "parse-options.h"
>     ++#include "prio-queue.h"
>     + #include "sha1-lookup.h"
>     + #include "commit-slab.h"
>     +
>      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
>       		return NULL;
>       }
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -		parse_commit(parent);
>      -		if (parent->date < cutoff)
>      -			continue;
>     -+	struct commit_list *list = NULL;
>     ++	struct prio_queue queue;
>     ++	struct commit *commit;
>     ++	struct commit **parents_to_queue = NULL;
>     ++	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
>      +
>     -+	commit_list_insert(start_commit, &list);
>     ++	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
>     ++	prio_queue_put(&queue, start_commit);
>      +
>     -+	while (list) {
>     -+		struct commit *commit = pop_commit(&list);
>     ++	while ((commit = prio_queue_get(&queue))) {
>      +		struct rev_name *name = get_commit_rev_name(commit);
>     -+		struct commit_list *parents, *new_parents = NULL;
>     -+		struct commit_list **last_new_parent = &new_parents;
>     ++		struct commit_list *parents;
>      +		int parent_number = 1;
>      +
>     ++		parents_to_queue_nr = 0;
>     ++
>      +		for (parents = commit->parents;
>      +				parents;
>      +				parents = parents->next, parent_number++) {
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -			distance = name->distance + 1;
>      +			if (create_or_update_name(parent, new_name, taggerdate,
>      +						  generation, distance,
>     -+						  from_tag))
>     -+				last_new_parent = commit_list_append(parent,
>     -+						  last_new_parent);
>     ++						  from_tag)) {
>     ++				ALLOC_GROW(parents_to_queue,
>     ++					   parents_to_queue_nr + 1,
>     ++					   parents_to_queue_alloc);
>     ++				parents_to_queue[parents_to_queue_nr] = parent;
>     ++				parents_to_queue_nr++;
>     ++			}
>       		}
>
>      -		if (create_or_update_name(parent, new_name, taggerdate,
>      -					  generation, distance,
>      -					  from_tag))
>      -			name_rev(parent, new_name, taggerdate, from_tag);
>     -+		*last_new_parent = list;
>     -+		list = new_parents;
>     ++		/* The first parent must come out first from the prio_queue */
>     ++		while (parents_to_queue_nr)
>     ++			prio_queue_put(&queue,
>     ++				       parents_to_queue[--parents_to_queue_nr]);
>       	}
>     ++
>     ++	clear_prio_queue(&queue);
>     ++	free(parents_to_queue);
>       }
>
>     + static int subpath_matches(const char *path, const char *filter)
>
>       ## t/t6120-describe.sh ##
>      @@ t/t6120-describe.sh: test_expect_success 'describe tag object' '
> 13:  1ef69550ca ! 13:  316f7af43c name-rev: cleanup name_ref()
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      -		int from_tag)
>      +		int from_tag, int deref)
>       {
>     - 	struct commit_list *list = NULL;
>     + 	struct prio_queue queue;
>     + 	struct commit *commit;
>     + 	struct commit **parents_to_queue = NULL;
>     + 	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
>      +	char *to_free = NULL;
>      +
>      +	parse_commit(start_commit);
>     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
>      +		return;
>      +	}
>
>     - 	commit_list_insert(start_commit, &list);
>     -
>     + 	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
>     + 	prio_queue_put(&queue, start_commit);
>      @@ builtin/name-rev.c: static int name_ref(const char *path, const struct object_id *oid, int flags, vo
>       		if (taggerdate == TIME_MAX)
>       			taggerdate = commit->date;
> 14:  9d513b3092 <  -:  ---------- name-rev: plug a memory leak in name_rev()
> 15:  8489abb62e <  -:  ---------- name-rev: plug a memory leak in name_rev() in the deref case
> --
> 2.24.0.388.gde53c094ea
>
>

>
> Hi,
>
> [Cc:ing Sebastian, as they indicated in
> https://public-inbox.org/git/CAE7Eq9hEiVf1rMNdWx55_nQsz2gVv0N%2Bs1KckK1evtmruqcHyA@mail.gmail.com/t/#u
> that they would be interested in testing this]
>
> Sebastian, could you test this patch series? Since you are on Windows,
> you should be able to do so by
>
> - installing Git for Windows' SDK
>   (https://gitforwindows.org/#download-sdk)
> - `sdk cd git` (possibly `sdk init git`, although that should be
>   implied)
> - `sdk init build-extra` followed by
>   `/usr/src/build-extra/apply-from-public-inbox.sh
>   https://public-inbox.org/git/20191112103821.30265-1-szeder.dev@gmail.com/`
> - `sdk build`
>
> The result should include a `git.exe` in `/usr/src/git/` that you can
> copy to your server and test via `/path/to/git.exe name-rev ...`.
>
> Ciao,
> Johannes
>
> On Tue, 12 Nov 2019, SZEDER Gábor wrote:
>
> > 'git name-rev' is implemented using a recursive algorithm, and,
> > consequently, it can segfault in deep histories (e.g. WebKit), and
> > thanks to a test case demonstrating this limitation every test run
> > results in a dmesg entry logging the segfaulting git process.
> >
> > This patch series eliminates the recursion.
> >
> > Patches 1-5 are while-at-it cleanups I noticed on the way, and patch 6
> > improves test coverage.  Patches 7-11 are preparatory refactorings
> > that are supposed to make this series easier to follow, and make patch
> > 12, the one finally eliminating the recursion, somewhat shorter, and
> > even much shorter when viewed with '--ignore-all-space'.  Patch 13
> > cleans up after those preparatory steps.
> >
> > Changes since v1:
> >
> >   - Patch 12 now eliminates the recursion using a LIFO 'prio_queue'
> >     instead of a 'commit_list' to avoid any performance penalty.
> >
> >   - Commit message updates, clarifications, typofixes, missing
> >     signoffs, etc., most notably in patches 6 and 12.
> >
> >   - Updated ASCII art history graphs.
> >
> >   - Replaced the strbuf_suffix() cleanup in patch 3 with René's
> >     suggestion; now that patch needs his signoff.
> >
> >   - Dropped the last two patches plugging memory leaks; René's plan
> >     to clean up memory ownership looked more promising, and that
> >     would make these two dropped patches moot anyway.
> >
> > v1: https://public-inbox.org/git/20190919214712.7348-1-szeder.dev@gmail.com/T/#u
> >
> > René Scharfe (1):
> >   name-rev: use strbuf_strip_suffix() in get_rev_name()
> >
> > SZEDER Gábor (12):
> >   t6120-describe: correct test repo history graph in comment
> >   t6120-describe: modernize the 'check_describe' helper
> >   name-rev: avoid unnecessary cast in name_ref()
> >   name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
> >   t6120: add a test to cover inner conditions in 'git name-rev's
> >     name_rev()
> >   name-rev: extract creating/updating a 'struct name_rev' into a helper
> >   name-rev: pull out deref handling from the recursion
> >   name-rev: restructure parsing commits and applying date cutoff
> >   name-rev: restructure creating/updating 'struct rev_name' instances
> >   name-rev: drop name_rev()'s 'generation' and 'distance' parameters
> >   name-rev: eliminate recursion in name_rev()
> >   name-rev: cleanup name_ref()
> >
> >  builtin/name-rev.c  | 147 +++++++++++++++++++++++++++++---------------
> >  t/t6120-describe.sh |  72 +++++++++++++++++-----
> >  2 files changed, 153 insertions(+), 66 deletions(-)
> >
> > Range-diff:
> >  1:  673da20e3d !  1:  8d70ed050d t6120-describe: correct test repo history graph in comment
> >     @@ t/t6120-describe.sh
> >      -test_description='test describe
> >      +test_description='test describe'
> >      +
> >     -+#       ,---o----o----o-----.
> >     -+#      /   D,R   e           \
> >     -+#  o--o-----o-------------o---o----x
> >     -+#      \    B            /
> >     -+#       `---o----o----o-'
> >     -+#                A    c
> >     ++#  o---o-----o----o----o-------o----x
> >     ++#       \   D,R   e           /
> >     ++#        \---o-------------o-'
> >     ++#         \  B            /
> >     ++#          `-o----o----o-'
> >     ++#                 A    c
> >     ++#
> >     ++# First parent of a merge commit is on the same line, second parent below.
> >
> >      -                       B
> >      -        .--------------o----o----o----x
> >  2:  05df899693 =  2:  3720b6859d t6120-describe: modernize the 'check_describe' helper
> >  3:  7b0227cfea !  3:  ad2f2eee68 name-rev: use strip_suffix() in get_rev_name()
> >     @@
> >       ## Metadata ##
> >     -Author: SZEDER Gábor <szeder.dev@gmail.com>
> >     +Author: René Scharfe <l.s.r@web.de>
> >
> >       ## Commit message ##
> >     -    name-rev: use strip_suffix() in get_rev_name()
> >     +    name-rev: use strbuf_strip_suffix() in get_rev_name()
> >
> >     -    Use strip_suffix() instead of open-coding it, making the code more
> >     -    idiomatic.
> >     +    get_name_rev() basically open-codes strip_suffix() before adding a
> >     +    string to a strbuf.
> >
> >     +    Let's use the strbuf right from the beginning, i.e. add the whole
> >     +    string to the strbuf and then use strbuf_strip_suffix(), making the
> >     +    code more idiomatic.
> >     +
> >     +    [TODO: René's signoff!]
> >          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> >       ## builtin/name-rev.c ##
> >     @@ builtin/name-rev.c: static const char *get_rev_name(const struct object *o, stru
> >      -                int len = strlen(n->tip_name);
> >      -                if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
> >      -                        len -= 2;
> >     -+                size_t len;
> >     -+                strip_suffix(n->tip_name, "^0", &len);
> >                       strbuf_reset(buf);
> >      -                strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
> >     -+                strbuf_addf(buf, "%.*s~%d", (int) len, n->tip_name,
> >     -+                            n->generation);
> >     ++                strbuf_addstr(buf, n->tip_name);
> >     ++                strbuf_strip_suffix(buf, "^0");
> >     ++                strbuf_addf(buf, "~%d", n->generation);
> >                       return buf->buf;
> >               }
> >       }
> >  4:  40faecdc2a =  4:  c86a2ae2d0 name-rev: avoid unnecessary cast in name_ref()
> >  5:  c71df3dadf =  5:  4fc960cc05 name-rev: use sizeof(*ptr) instead of sizeof(type) in allocation
> >  6:  1dcb76072f !  6:  1493cb4484 t6120: add a test to cover inner conditions in 'git name-rev's name_rev()
> >     @@ Commit message
> >          looks like this:
> >
> >            if (parent_number > 1) {
> >     -        if (generation > 0)
> >     -          // do stuff #1
> >     -        else
> >     -          // do stuff #2
> >     +          if (generation > 0)
> >     +              // branch #1
> >     +              new_name = ...
> >     +          else
> >     +              // branch #2
> >     +              new_name = ...
> >     +          name_rev(parent, new_name, ...);
> >            } else {
> >     -         // do stuff #3
> >     +          // branch #3
> >     +          name_rev(...);
> >            }
> >
> >          These conditions are not covered properly in the test suite.  As far
> >     @@ Commit message
> >          command's output, because the repository used in that test script
> >          contains several branches and tags pointing somewhere into the middle
> >          of the commit DAG, and thus result in a better name for the
> >     -    to-be-named commit.  In an early version of this patch series I
> >     -    managed to mess up those conditions (every single one of them at
> >     -    once!), but the whole test suite still passed successfully.
> >     +    to-be-named commit.  This can hide bugs: e.g. by replacing the
> >     +    'new_name' parameter of the first recursive name_rev() call with
> >     +    'tip_name' (effectively making both branch #1 and #2 a noop) 'git
> >     +    name-rev --all' shows thousands of bogus names in the Git repository,
> >     +    but the whole test suite still passes successfully.  In an early
> >     +    version of a later patch in this series I managed to mess up all three
> >     +    branches (at once!), but the test suite still passed.
> >
> >          So add a new test case that operates on the following history:
> >
> >     -        -----------master
> >     -       /          /
> >     -      A----------M2
> >     -       \        /
> >     -        \---M1-C
> >     -         \ /
> >     -          B
> >     +      A--------------master
> >     +       \            /
> >     +        \----------M2
> >     +         \        /
> >     +          \---M1-C
> >     +           \ /
> >     +            B
> >
> >     -    and names the commit 'B', where:
> >     +    and names the commit 'B' to make sure that all three branches are
> >     +    crucial to determine 'B's name:
> >
> >     -      - The merge commit at master makes sure that the 'do stuff #3'
> >     -        affects the final name.
> >     +      - There is only a single ref, so all names are based on 'master',
> >     +        without any undesired interference from other refs.
> >
> >     -      - The merge commit M2 make sure that the 'do stuff #1' part
> >     -        affects the final name.
> >     +      - Each time name_rev() follows the second parent of a merge commit,
> >     +        it appends "^2" to the name.  Following 'master's second parent
> >     +        right at the start ensures that all commits on the ancestry path
> >     +        from 'master' to 'B' have a different base name from the original
> >     +        'tip_name' of the very first name_rev() invocation.  Currently,
> >     +        while name_rev() is recursive, it doesn't matter, but it will be
> >     +        necessary to properly cover all three branches after the recursion
> >     +        is eliminated later in this series.
> >
> >     -      - And M1 makes sure that the 'do stuff #2' part affects the final
> >     -        name.
> >     +      - Following 'M2's second parent makes sure that branch #2 (i.e. when
> >     +        'generation = 0') affects 'B's name.
> >     +
> >     +      - Following the only parent of the non-merge commit 'C' ensures that
> >     +        branch #3 affects 'B's name, and that it increments 'generation'.
> >     +
> >     +      - Coming from 'C' 'generation' is 1, thus following 'M1's second
> >     +        parent makes sure that branch #1 affects 'B's name.
> >
> >          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> >       ## t/t6120-describe.sh ##
> >     -@@ t/t6120-describe.sh: test_expect_success 'describe complains about missing object' '
> >     -         test_must_fail git describe $ZERO_OID
> >     +@@ t/t6120-describe.sh: test_expect_success 'name-rev a rev shortly after epoch' '
> >     +         test_cmp expect actual
> >       '
> >
> >     -+#   -----------master
> >     -+#  /          /
> >     -+# A----------M2
> >     -+#  \        /
> >     -+#   \---M1-C
> >     -+#    \ /
> >     -+#     B
> >     -+test_expect_success 'test' '
> >     ++# A--------------master
> >     ++#  \            /
> >     ++#   \----------M2
> >     ++#    \        /
> >     ++#     \---M1-C
> >     ++#      \ /
> >     ++#       B
> >     ++test_expect_success 'name-rev covers all conditions while looking at parents' '
> >      +        git init repo &&
> >      +        (
> >      +                cd repo &&
> >     @@ t/t6120-describe.sh: test_expect_success 'describe complains about missing objec
> >      +                git checkout master &&
> >      +                git merge --no-ff HEAD@{1} &&
> >      +
> >     -+                git log --graph --oneline &&
> >     -+
> >      +                echo "$B master^2^2~1^2" >expect &&
> >      +                git name-rev $B >actual &&
> >      +
> >  7:  bdd8378b06 =  7:  fc842e578b name-rev: extract creating/updating a 'struct name_rev' into a helper
> >  8:  ce21c351f9 !  8:  7f182503e2 name-rev: pull out deref handling from the recursion
> >     @@ Commit message
> >          Extract this condition from the recursion into name_rev()'s caller and
> >          drop the function's 'deref' parameter.  This makes eliminating the
> >          recursion a bit easier to follow, and it will be moved back into
> >     -    name_rev() after the recursion is elminated.
> >     +    name_rev() after the recursion is eliminated.
> >
> >          Furthermore, drop the condition that die()s when both 'deref' and
> >          'generation' are non-null (which should have been a BUG() to begin
> >     @@ Commit message
> >
> >          Note that this change reintroduces the memory leak that was plugged in
> >          in commit 5308224633 (name-rev: avoid leaking memory in the `deref`
> >     -    case, 2017-05-04), but a later patch in this series will plug it in
> >     -    again.
> >     +    case, 2017-05-04), but a later patch (name-rev: restructure
> >     +    creating/updating 'struct rev_name' instances) in this series will
> >     +    plug it in again.
> >
> >          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> >  9:  c8acc6b597 !  9:  0cdd40b75b name-rev: restructure parsing commits and applying date cutoff
> >     @@ Commit message
> >          name_rev() and name_rev() itself as it iterates over the parent
> >          commits.
> >
> >     -    This makes eliminating the recursion a bit easier to follow, and it
> >     -    will be moved back to name_rev() after the recursion is eliminated.
> >     +    This makes eliminating the recursion a bit easier to follow, and the
> >     +    condition moved to name_ref() will be moved back to name_rev() after
> >     +    the recursion is eliminated.
> >
> >          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> > 10:  c731f27158 ! 10:  e1733e3c56 name-rev: restructure creating/updating 'struct rev_name' instances
> >     @@ Commit message
> >          At the beginning of the recursive name_rev() function it creates a new
> >          'struct rev_name' instance for each previously unvisited commit or, if
> >          this visit results in better name for an already visited commit, then
> >     -    updates the 'struct rev_name' instance attached to to the commit, or
> >     +    updates the 'struct rev_name' instance attached to the commit, or
> >          returns early.
> >
> >          Restructure this so it's caller creates or updates the 'struct
> >     @@ Commit message
> >          parameter, i.e. both name_ref() before calling name_rev() and
> >          name_rev() itself as it iterates over the parent commits.
> >
> >     -    This makes eliminating the recursion a bit easier to follow, and it
> >     -    will be moved back to name_rev() after the recursion is eliminated.
> >     +    This makes eliminating the recursion a bit easier to follow, and the
> >     +    condition moved to name_ref() will be moved back to name_rev() after
> >     +    the recursion is eliminated.
> >
> >          This change also plugs the memory leak that was temporarily unplugged
> >          in the earlier "name-rev: pull out deref handling from the recursion"
> > 11:  ba14bde230 ! 11:  bd6e2e6d87 name-rev: drop name_rev()'s 'generation' and 'distance' parameters
> >     @@ Commit message
> >          'taggerdate' and 'from_tag' parameters as well, but those parameters
> >          will be necessary later, after the recursion is eliminated.
> >
> >     -    Drop name_rev()'s 'generation' and 'distance' parameters.
> >     +    Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> >       ## builtin/name-rev.c ##
> >      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
> > 12:  2d03ac11f3 ! 12:  0cf63c6d64 name-rev: eliminate recursion in name_rev()
> >     @@ Commit message
> >          segfault when processing a deep history if it exhausts the available
> >          stack space.  E.g. running 'git name-rev --all' and 'git name-rev
> >          HEAD~100000' in the gcc, gecko-dev, llvm, and WebKit repositories
> >     -    results in segfaults on my machine.
> >     +    results in segfaults on my machine ('ulimit -s' reports 8192kB of
> >     +    stack size limit), and nowadays the former segfaults in the Linux repo
> >     +    as well (it reached the necessasry depth sometime between v5.3-rc4 and
> >     +    -rc5).
> >
> >          Eliminate the recursion by inserting the interesting parents into a
> >     -    'commit_list' and iteratating until the list becomes empty.
> >     +    LIFO 'prio_queue' [1] and iterating until the queue becomes empty.
> >
> >     -    Note that the order in which the parent commits are added to that list
> >     -    is important: they must be inserted at the beginning of the list, and
> >     -    their relative order must be kept as well, because otherwise
> >     -    performance suffers.
> >     +    Note that the parent commits must be added in reverse order to the
> >     +    LIFO 'prio_queue', so their relative order is preserved during
> >     +    processing, i.e. the first parent should come out first from the
> >     +    queue, because otherwise performance greatly suffers on mergy
> >     +    histories [2].
> >
> >          The stacksize-limited test 'name-rev works in a deep repo' in
> >          't6120-describe.sh' demonstrated this issue and expected failure.  Now
> >     -    the recursion is gone, so flip it to expect success.
> >     -
> >     -    Also gone are the dmesg entries logging the segfault of the git
> >     -    process on every execution of the test suite.
> >     -
> >     -    Unfortunately, eliminating the recursion comes with a performance
> >     -    penaly: 'git name-rev --all' tends to be between 15-20% slower than
> >     -    before.
> >     +    the recursion is gone, so flip it to expect success.  Also gone are
> >     +    the dmesg entries logging the segfault of that segfaulting 'git
> >     +    name-rev' process on every execution of the test suite.
> >
> >          Note that this slightly changes the order of lines in the output of
> >          'git name-rev --all', usually swapping two lines every 35 lines in
> >     @@ Commit message
> >
> >          This patch is best viewed with '--ignore-all-space'.
> >
> >     +    [1] Early versions of this patch used a 'commit_list', resulting in
> >     +        ~15% performance penalty for 'git name-rev --all' in 'linux.git',
> >     +        presumably because of the memory allocation and release for each
> >     +        insertion and removal. Using a LIFO 'prio_queue' has basically no
> >     +        effect on performance.
> >     +
> >     +    [2] We prefer shorter names, i.e. 'v0.1~234' is preferred over
> >     +        'v0.1^2~5', meaning that usually following the first parent of a
> >     +        merge results in the best name for its ancestors.  So when later
> >     +        we follow the remaining parent(s) of a merge, and reach an already
> >     +        named commit, then we usually find that we can't give that commit
> >     +        a better name, and thus we don't have to visit any of its
> >     +        ancestors again.
> >     +
> >     +        OTOH, if we were to follow the Nth parent of the merge first, then
> >     +        the name of all its ancestors would include a corresponding '^N'.
> >     +        Those are not the best names for those commits, so when later we
> >     +        reach an already named commit following the first parent of that
> >     +        merge, then we would have to update the name of that commit and
> >     +        the names of all of its ancestors as well.  Consequently, we would
> >     +        have to visit many commits several times, resulting in a
> >     +        significant slowdown.
> >     +
> >          Signed-off-by: SZEDER Gábor <szeder.dev@gmail.com>
> >
> >       ## builtin/name-rev.c ##
> >     +@@
> >     + #include "tag.h"
> >     + #include "refs.h"
> >     + #include "parse-options.h"
> >     ++#include "prio-queue.h"
> >     + #include "sha1-lookup.h"
> >     + #include "commit-slab.h"
> >     +
> >      @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit *commit,
> >                       return NULL;
> >       }
> >     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
> >      -                parse_commit(parent);
> >      -                if (parent->date < cutoff)
> >      -                        continue;
> >     -+        struct commit_list *list = NULL;
> >     ++        struct prio_queue queue;
> >     ++        struct commit *commit;
> >     ++        struct commit **parents_to_queue = NULL;
> >     ++        size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
> >      +
> >     -+        commit_list_insert(start_commit, &list);
> >     ++        memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
> >     ++        prio_queue_put(&queue, start_commit);
> >      +
> >     -+        while (list) {
> >     -+                struct commit *commit = pop_commit(&list);
> >     ++        while ((commit = prio_queue_get(&queue))) {
> >      +                struct rev_name *name = get_commit_rev_name(commit);
> >     -+                struct commit_list *parents, *new_parents = NULL;
> >     -+                struct commit_list **last_new_parent = &new_parents;
> >     ++                struct commit_list *parents;
> >      +                int parent_number = 1;
> >      +
> >     ++                parents_to_queue_nr = 0;
> >     ++
> >      +                for (parents = commit->parents;
> >      +                                parents;
> >      +                                parents = parents->next, parent_number++) {
> >     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
> >      -                        distance = name->distance + 1;
> >      +                        if (create_or_update_name(parent, new_name, taggerdate,
> >      +                                                  generation, distance,
> >     -+                                                  from_tag))
> >     -+                                last_new_parent = commit_list_append(parent,
> >     -+                                                  last_new_parent);
> >     ++                                                  from_tag)) {
> >     ++                                ALLOC_GROW(parents_to_queue,
> >     ++                                           parents_to_queue_nr + 1,
> >     ++                                           parents_to_queue_alloc);
> >     ++                                parents_to_queue[parents_to_queue_nr] = parent;
> >     ++                                parents_to_queue_nr++;
> >     ++                        }
> >                       }
> >
> >      -                if (create_or_update_name(parent, new_name, taggerdate,
> >      -                                          generation, distance,
> >      -                                          from_tag))
> >      -                        name_rev(parent, new_name, taggerdate, from_tag);
> >     -+                *last_new_parent = list;
> >     -+                list = new_parents;
> >     ++                /* The first parent must come out first from the prio_queue */
> >     ++                while (parents_to_queue_nr)
> >     ++                        prio_queue_put(&queue,
> >     ++                                       parents_to_queue[--parents_to_queue_nr]);
> >               }
> >     ++
> >     ++        clear_prio_queue(&queue);
> >     ++        free(parents_to_queue);
> >       }
> >
> >     + static int subpath_matches(const char *path, const char *filter)
> >
> >       ## t/t6120-describe.sh ##
> >      @@ t/t6120-describe.sh: test_expect_success 'describe tag object' '
> > 13:  1ef69550ca ! 13:  316f7af43c name-rev: cleanup name_ref()
> >     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
> >      -                int from_tag)
> >      +                int from_tag, int deref)
> >       {
> >     -         struct commit_list *list = NULL;
> >     +         struct prio_queue queue;
> >     +         struct commit *commit;
> >     +         struct commit **parents_to_queue = NULL;
> >     +         size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
> >      +        char *to_free = NULL;
> >      +
> >      +        parse_commit(start_commit);
> >     @@ builtin/name-rev.c: static struct rev_name *create_or_update_name(struct commit
> >      +                return;
> >      +        }
> >
> >     -         commit_list_insert(start_commit, &list);
> >     -
> >     +         memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
> >     +         prio_queue_put(&queue, start_commit);
> >      @@ builtin/name-rev.c: static int name_ref(const char *path, const struct object_id *oid, int flags, vo
> >                       if (taggerdate == TIME_MAX)
> >                               taggerdate = commit->date;
> > 14:  9d513b3092 <  -:  ---------- name-rev: plug a memory leak in name_rev()
> > 15:  8489abb62e <  -:  ---------- name-rev: plug a memory leak in name_rev() in the deref case
> > --
> > 2.24.0.388.gde53c094ea
> >
> >

> 'git name-rev' is implemented using a recursive algorithm, and,
> consequently, it can segfault in deep histories (e.g. WebKit), and
> thanks to a test case demonstrating this limitation every test run
> results in a dmesg entry logging the segfaulting git process.
> 
> This patch series eliminates the recursion.
> 
> Changes since v2:
> 
>   - Add the new patch 12 to use 'name->tip_name' instead of
>     'tip_name', to make the patch eliminating the recursion a bit even
>     easier to follow (only with '--ignore-all-space', though, without
>     that option that patch's diff is still mostly gibberish).
>     The end result is the still same, see the empty interdiff.

> On 12/9/2019 6:52 AM, SZEDER Gábor wrote:
>> 'git name-rev' is implemented using a recursive algorithm, and,
>> consequently, it can segfault in deep histories (e.g. WebKit), and
>> thanks to a test case demonstrating this limitation every test run
>> results in a dmesg entry logging the segfaulting git process.
>> 
>> This patch series eliminates the recursion.
>> 
>> Changes since v2:
>> 
>>   - Add the new patch 12 to use 'name->tip_name' instead of
>>     'tip_name', to make the patch eliminating the recursion a bit even
>>     easier to follow (only with '--ignore-all-space', though, without
>>     that option that patch's diff is still mostly gibberish).
>>     The end result is the still same, see the empty interdiff.
>
> This new commit makes sense, and I see how it adjusts the context lines
> in the patch that follows. This series looks good to me.