Corrupt name-rev output

> I've noticed a series of about 20 commits in the HardenedBSD repository
> fairly reliably produce garbage names from git name-rev - usually
> fragments of another commit, sometimes unprintable nonsense.  Sometimes
> it works just fine...
>
> Here's a quick demo showing how to reproduce the problem:
>
> % uname -mrs
> FreeBSD 13.0-RELEASE-p11 amd64
> % git --version
> git version 2.35.2
> % git clone --bare --mirror https://github.com/HardenedBSD/hardenedBSD.git
> % cd hardenedBSD.git
> % git rev-list --branches=\* |
>   git name-rev --stdin --refs=heads/\* |
>   egrep -v '^[0-9a-f]{40}( \([a-zA-Z0-9_/.^~-]+\))?$'
> 3eb67b534cab6a78b44b13e4323fd60353003089 (y:    marcel
> MFC after:      3 days
> Relnotes:       yes
> Sponsored by:   ScaleEngine Inc.
> Differential Revision:  https://reviews.freebsd.org/D3065
> ~3)
> 3ac660fc0c6eb0f876972e7e415c89f1ebed1939 (y:    marcel
> ...
> Passing these commits into name-rev as arguments finds them under
> hardened/current/relro~199^2
>
> git fsck --full does not reveal or fix anything, and the problem also
> persists with a build from source from the next branch.
>
> I was unable to reproduce on an Ubuntu machine with 2.32.0, so I used
> that as a starting point for bisection and landed here:
>
>   3656f842789d25d75da41c6c029470052a573b54
>   name-rev: prefer shorter names over following merges

>
> Thomas Hurst <tom@hur.st> writes:
>
> > I've noticed a series of about 20 commits in the HardenedBSD repository
> > fairly reliably produce garbage names from git name-rev - usually
> > fragments of another commit, sometimes unprintable nonsense.  Sometimes
> > it works just fine...
> >
> > Here's a quick demo showing how to reproduce the problem:
> >
> > % uname -mrs
> > FreeBSD 13.0-RELEASE-p11 amd64
> > % git --version
> > git version 2.35.2
> > % git clone --bare --mirror https://github.com/HardenedBSD/hardenedBSD.git
> > % cd hardenedBSD.git
> > % git rev-list --branches=\* |
> >   git name-rev --stdin --refs=heads/\* |
> >   egrep -v '^[0-9a-f]{40}( \([a-zA-Z0-9_/.^~-]+\))?$'
> > 3eb67b534cab6a78b44b13e4323fd60353003089 (y:    marcel
> > MFC after:      3 days
> > Relnotes:       yes
> > Sponsored by:   ScaleEngine Inc.
> > Differential Revision:  https://reviews.freebsd.org/D3065
> > ~3)
> > 3ac660fc0c6eb0f876972e7e415c89f1ebed1939 (y:    marcel
> > ...
> > Passing these commits into name-rev as arguments finds them under
> > hardened/current/relro~199^2
> >
> > git fsck --full does not reveal or fix anything, and the problem also
> > persists with a build from source from the next branch.
> >
> > I was unable to reproduce on an Ubuntu machine with 2.32.0, so I used
> > that as a starting point for bisection and landed here:
> >
> >   3656f842789d25d75da41c6c029470052a573b54
> >   name-rev: prefer shorter names over following merges
>
> commit 3656f842789d25d75da41c6c029470052a573b54
> Author: Elijah Newren <newren@gmail.com>
>
> Hmph, Elijah, does this ring a bell?

> On Tue, Apr 19, 2022 at 8:13 PM Junio C Hamano <gitster@pobox.com> wrote:
>>
>> Thomas Hurst <tom@hur.st> writes:
>>
>>> I've noticed a series of about 20 commits in the HardenedBSD repository
>>> fairly reliably produce garbage names from git name-rev - usually
>>> fragments of another commit, sometimes unprintable nonsense.  Sometimes
>>> it works just fine...
>>>
>>> Here's a quick demo showing how to reproduce the problem:
>>>
>>> % uname -mrs
>>> FreeBSD 13.0-RELEASE-p11 amd64
>>> % git --version
>>> git version 2.35.2
>>> % git clone --bare --mirror https://github.com/HardenedBSD/hardenedBSD.git
>>> % cd hardenedBSD.git
>>> % git rev-list --branches=\* |
>>>   git name-rev --stdin --refs=heads/\* |
>>>   egrep -v '^[0-9a-f]{40}( \([a-zA-Z0-9_/.^~-]+\))?$'
>>> 3eb67b534cab6a78b44b13e4323fd60353003089 (y:    marcel
>>> MFC after:      3 days
>>> Relnotes:       yes
>>> Sponsored by:   ScaleEngine Inc.
>>> Differential Revision:  https://reviews.freebsd.org/D3065
>>> ~3)
>>> 3ac660fc0c6eb0f876972e7e415c89f1ebed1939 (y:    marcel
>>> ...
>>> Passing these commits into name-rev as arguments finds them under
>>> hardened/current/relro~199^2
>>>
>>> git fsck --full does not reveal or fix anything, and the problem also
>>> persists with a build from source from the next branch.
>>>
>>> I was unable to reproduce on an Ubuntu machine with 2.32.0, so I used
>>> that as a starting point for bisection and landed here:
>>>
>>>   3656f842789d25d75da41c6c029470052a573b54
>>>   name-rev: prefer shorter names over following merges
>>
>> commit 3656f842789d25d75da41c6c029470052a573b54
>> Author: Elijah Newren <newren@gmail.com>
>>
>> Hmph, Elijah, does this ring a bell?
>
> After digging around last night and tonight, this appears to be a poor
> interaction with commit 2d53975488 ("name-rev: release unused name
> strings", 2020-02-04), which frees shared strings and relies on all
> other users of that shared string to update their name, which
> apparently seemed to rely on some intricacies of how the algorithm
> worked that are no longer valid with my change, resulting in some
> use-after-frees (though for some reason valgrind isn't spotting them
> for me, which made it harder to track these down).

>  Adding Rene to the cc
> for comments.  Rene: If it helps, there's a slightly simpler
> reproduction: clone the repo Thomas mentions, and then instead of his
> "rev-list | name-rev | grep" sequence just run:
>
>     git name-rev --refs=heads/\* 3eb67b534cab6a78b44b13e4323fd60353003089

> Am 21.04.22 um 04:11 schrieb Elijah Newren:
>
>> Reverting 2d53975488 fixes the problem.
>
> That's a good band-aid.

> Subject: [PATCH] Revert "name-rev: release unused name strings"
>
> This reverts commit 2d53975488df195e1431c3f90bfb5b60018d5bf6.
>
> 3656f84278 (name-rev: prefer shorter names over following merges,
> 2021-12-04) broke the assumption of 2d53975488 (name-rev: release unused
> name strings, 2020-02-04) that a better name for a child is a better
> name for all of its ancestors as well, because it added a penalty for
> generation > 0.  This leads to strings being free(3)'d that are still
> needed.

> Am 21.04.22 um 19:55 schrieb René Scharfe:
>> Am 21.04.22 um 04:11 schrieb Elijah Newren:
>>
>>> Reverting 2d53975488 fixes the problem.
>>
>> That's a good band-aid.
> Or perhaps it's all we need.  I can't replicate the original reduction
> of peak memory usage for the Chromium repo anymore.  In fact, the very
> next commit, 079f970971 (name-rev: sort tip names before applying,
> 2020-02-05), reduced the number of times free(3) is called there from
> 44245 to 5, and 3656f84278 (name-rev: prefer shorter names over
> following merges, 2021-12-04) brought that number down to zero.
>
> I can't reproduce the issue with the hardenedBSD repo, by the way, but
> e.g. with 'git name-rev 58b82150da' in the Linux repo.
>
> --- >8 ---
> Subject: [PATCH] Revert "name-rev: release unused name strings"
>
> This reverts commit 2d53975488df195e1431c3f90bfb5b60018d5bf6.
>
> 3656f84278 (name-rev: prefer shorter names over following merges,
> 2021-12-04) broke the assumption of 2d53975488 (name-rev: release unused
> name strings, 2020-02-04) that a better name for a child is a better
> name for all of its ancestors as well, because it added a penalty for
> generation > 0.  This leads to strings being free(3)'d that are still
> needed.
>
> 079f970971 (name-rev: sort tip names before applying, 2020-02-05)
> already reduced the number of free(3) calls for the use case that
> motivated the original patch (name-rev --all in the Chromium repository)
> from ca. 44000 to 5, and 3656f84278 eliminated even those few.  So this
> revert won't affect name-rev's performance on that particular repo.
>
> Reported-by: Thomas Hurst <tom@hur.st>
> Helped-by: Elijah Newren <newren@gmail.com>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
>  builtin/name-rev.c | 21 +++++----------------
>  1 file changed, 5 insertions(+), 16 deletions(-)
>
> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> index c59b5699fe..02ea9d1633 100644
> --- a/builtin/name-rev.c
> +++ b/builtin/name-rev.c
> @@ -18,7 +18,7 @@
>  #define CUTOFF_DATE_SLOP 86400
>
>  struct rev_name {
> -	char *tip_name;
> +	const char *tip_name;
>  	timestamp_t taggerdate;
>  	int generation;
>  	int distance;
> @@ -84,7 +84,7 @@ static int commit_is_before_cutoff(struct commit *commit)
>
>  static int is_valid_rev_name(const struct rev_name *name)
>  {
> -	return name && (name->generation || name->tip_name);
> +	return name && name->tip_name;
>  }
>
>  static struct rev_name *get_commit_rev_name(const struct commit *commit)
> @@ -146,20 +146,9 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>  {
>  	struct rev_name *name = commit_rev_name_at(&rev_names, commit);
>
> -	if (is_valid_rev_name(name)) {
> -		if (!is_better_name(name, taggerdate, generation, distance, from_tag))
> -			return NULL;
> -
> -		/*
> -		 * This string might still be shared with ancestors
> -		 * (generation > 0).  We can release it here regardless,
> -		 * because the new name that has just won will be better
> -		 * for them as well, so name_rev() will replace these
> -		 * stale pointers when it processes the parents.
> -		 */
> -		if (!name->generation)
> -			free(name->tip_name);
> -	}
> +	if (is_valid_rev_name(name) &&
> +	    !is_better_name(name, taggerdate, generation, distance, from_tag))
> +		return NULL;
>
>  	name->taggerdate = taggerdate;
>  	name->generation = generation;

>
> On Fri, Apr 22 2022, René Scharfe wrote:
>
>> Am 21.04.22 um 19:55 schrieb René Scharfe:
>>> Am 21.04.22 um 04:11 schrieb Elijah Newren:
>>>
>>>> Reverting 2d53975488 fixes the problem.
>>>
>>> That's a good band-aid.
>> Or perhaps it's all we need.  I can't replicate the original reduction
>> of peak memory usage for the Chromium repo anymore.  In fact, the very
>> next commit, 079f970971 (name-rev: sort tip names before applying,
>> 2020-02-05), reduced the number of times free(3) is called there from
>> 44245 to 5, and 3656f84278 (name-rev: prefer shorter names over
>> following merges, 2021-12-04) brought that number down to zero.
>>
>> I can't reproduce the issue with the hardenedBSD repo, by the way, but
>> e.g. with 'git name-rev 58b82150da' in the Linux repo.
>>
>> --- >8 ---
>> Subject: [PATCH] Revert "name-rev: release unused name strings"
>>
>> This reverts commit 2d53975488df195e1431c3f90bfb5b60018d5bf6.
>>
>> 3656f84278 (name-rev: prefer shorter names over following merges,
>> 2021-12-04) broke the assumption of 2d53975488 (name-rev: release unused
>> name strings, 2020-02-04) that a better name for a child is a better
>> name for all of its ancestors as well, because it added a penalty for
>> generation > 0.  This leads to strings being free(3)'d that are still
>> needed.
>>
>> 079f970971 (name-rev: sort tip names before applying, 2020-02-05)
>> already reduced the number of free(3) calls for the use case that
>> motivated the original patch (name-rev --all in the Chromium repository)
>> from ca. 44000 to 5, and 3656f84278 eliminated even those few.  So this
>> revert won't affect name-rev's performance on that particular repo.
>>
>> Reported-by: Thomas Hurst <tom@hur.st>
>> Helped-by: Elijah Newren <newren@gmail.com>
>> Signed-off-by: René Scharfe <l.s.r@web.de>
>> ---
>>  builtin/name-rev.c | 21 +++++----------------
>>  1 file changed, 5 insertions(+), 16 deletions(-)
>>
>> diff --git a/builtin/name-rev.c b/builtin/name-rev.c
>> index c59b5699fe..02ea9d1633 100644
>> --- a/builtin/name-rev.c
>> +++ b/builtin/name-rev.c
>> @@ -18,7 +18,7 @@
>>  #define CUTOFF_DATE_SLOP 86400
>>
>>  struct rev_name {
>> -	char *tip_name;
>> +	const char *tip_name;
>>  	timestamp_t taggerdate;
>>  	int generation;
>>  	int distance;
>> @@ -84,7 +84,7 @@ static int commit_is_before_cutoff(struct commit *commit)
>>
>>  static int is_valid_rev_name(const struct rev_name *name)
>>  {
>> -	return name && (name->generation || name->tip_name);
>> +	return name && name->tip_name;
>>  }
>>
>>  static struct rev_name *get_commit_rev_name(const struct commit *commit)
>> @@ -146,20 +146,9 @@ static struct rev_name *create_or_update_name(struct commit *commit,
>>  {
>>  	struct rev_name *name = commit_rev_name_at(&rev_names, commit);
>>
>> -	if (is_valid_rev_name(name)) {
>> -		if (!is_better_name(name, taggerdate, generation, distance, from_tag))
>> -			return NULL;
>> -
>> -		/*
>> -		 * This string might still be shared with ancestors
>> -		 * (generation > 0).  We can release it here regardless,
>> -		 * because the new name that has just won will be better
>> -		 * for them as well, so name_rev() will replace these
>> -		 * stale pointers when it processes the parents.
>> -		 */
>> -		if (!name->generation)
>> -			free(name->tip_name);
>> -	}
>> +	if (is_valid_rev_name(name) &&
>> +	    !is_better_name(name, taggerdate, generation, distance, from_tag))
>> +		return NULL;
>>
>>  	name->taggerdate = taggerdate;
>>  	name->generation = generation;
>
> I haven't dug into whether it's a false positive, but with this change
> GCC's -fanalyzer has started complaining about a potential NULL
> dereference:
>
>     builtin/name-rev.c:230:50: error: dereference of NULL ‘name’ [CWE-476] [-Werror=analyzer-null-dereference]
>       230 |                                 generation = name->generation + 1;
>
> This "fixes" it, and passes all tests, but presumably a better fix
> involves the callers of get_commit_rev_name() (or that function itself)
> deciding if they're OK with NULL here earlier?:
>
> 	diff --git a/builtin/name-rev.c b/builtin/name-rev.c
> 	index 02ea9d16330..1d3a620ac72 100644
> 	--- a/builtin/name-rev.c
> 	+++ b/builtin/name-rev.c
> 	@@ -209,6 +209,7 @@ static void name_rev(struct commit *start_commit,
> 	 		struct rev_name *name = get_commit_rev_name(commit);
> 	 		struct commit_list *parents;
> 	 		int parent_number = 1;
> 	+		assert(name);
>
> 	 		parents_to_queue_nr = 0;
>
>