Re: [PATCH 15/16] commit-reach: make can_all_from_reach... linear

From: Derrick Stolee <stolee@gmail.com>
Date: Oct 1, 2018, 19:26 UTC
Message-ID: <dd798e76-922f-a113-4408-e3892bee3b44@gmail.com>
In-Reply-To: <d1b58614-989f-5998-6c53-c19eee409a2f@web.de>

On 10/1/2018 3:16 PM, René Scharfe wrote:

Show 19 quoted lines

> Am 28.06.2018 um 14:31 schrieb Derrick Stolee via GitGitGadget:
>> diff --git a/commit-reach.c b/commit-reach.c
>> index c58e50fbb..ac132c8e4 100644
>> --- a/commit-reach.c
>> +++ b/commit-reach.c
>> @@ -513,65 +513,88 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
>>   	return is_descendant_of(commit, list);
>>   }
>>   
>> -int reachable(struct commit *from, int with_flag, int assign_flag,
>> -	      time_t min_commit_date)
>> +static int compare_commits_by_gen(const void *_a, const void *_b)
>>   {
>> -	struct prio_queue work = { compare_commits_by_commit_date };
>> +	const struct commit *a = (const struct commit *)_a;
>> +	const struct commit *b = (const struct commit *)_b;
> This cast is bogus.  QSORT gets handed a struct commit **, i.e. an array
> of pointers, and qsort(1) passes references to those pointers to the
> compare function, and not the pointer values.

Good catch! I'm disappointed that we couldn't use type-checking here, as it is quite difficult to discover that the types are wrong here.

> As a result it's unlikely that the array is sorted in the intended
> order.  Given that, a silly question: Is sorting even necessary here?

The reason to sort is to hopefully minimize the amount we walk by exploring the "lower" commits first. This is a performance-only thing, not a correctness issue (which is why the bug exists). Even then, it is just a heuristic.

Show 31 quoted lines

> Anyway, the patch below should fix it.
>
> -- >8 --
> Subject: [PATCH] commit-reach: fix cast in compare_commits_by_gen()
>
> The elements of the array to be sorted are commit pointers, so the
> comparison function gets handed references to these pointers, not
> pointers to commit objects.  Cast to the right type and dereference
> once to correctly get the commit reference.
>
> Found using Clang's ASan and t5500.
>
> Signed-off-by: Rene Scharfe <l.s.r@web.de>
> ---
> Has this patch a performance impact?
>
>   commit-reach.c | 4 ++--
>   1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/commit-reach.c b/commit-reach.c
> index 00e5ceee6f..2f5e592d16 100644
> --- a/commit-reach.c
> +++ b/commit-reach.c
> @@ -529,8 +529,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,
>   
>   static int compare_commits_by_gen(const void *_a, const void *_b)
>   {
> -	const struct commit *a = (const struct commit *)_a;
> -	const struct commit *b = (const struct commit *)_b;
> +	const struct commit *a = *(const struct commit * const *)_a;
> +	const struct commit *b = *(const struct commit * const *)_b;

I would expect s/* const */**/ here, but I'm guessing your formulation is a bit extra careful about types.

Thanks!

Reviewed-by: Derrick Stolee <dstolee@microsoft.com>