Date:   Tue, 23 Oct 2018 21:32:38 +0100
From:   Thomas Gummerer <t.gummerer@gmail.com>
To:     =?iso-8859-1?Q?Ren=E9?= Scharfe <l.s.r@web.de>
Cc:     git@vger.kernel.org, Derrick Stolee <stolee@gmail.com>
Subject: Re: [PATCH] commit-reach: fix sorting commits by generation
Message-ID: <20181023203237.GF4883@hank.intra.tgummerer.com>
References: <20181022211037.22719-1-t.gummerer@gmail.com>
 <13bdda53-b751-182b-4aa8-d9a5c03f422d@web.de>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <13bdda53-b751-182b-4aa8-d9a5c03f422d@web.de>
User-Agent: Mutt/1.10.1 (2018-07-13)
Sender: git-owner@vger.kernel.org
Precedence: bulk

On 10/22, René Scharfe wrote:
> Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:
> > compare_commit_by_gen is used to sort a list of pointers to 'struct
> > commit'.  The comparison function for qsort is called with pointers to
> > the objects it needs to compare, so when sorting a list of 'struct
> > commit *', the arguments are of type 'struct commit **'.  However,
> > currently the comparison function casts it's arguments to 'struct
> > commit *' and uses those, leading to out of bounds memory access and
> > potentially to wrong results.  Fix that.
> > 
> > Signed-off-by: Thomas Gummerer <t.gummerer@gmail.com>
> > ---
> > 
> > I noticed this by running the test suite through valgrind.  I'm not
> > familiar with this code, so I'm not sure why this didn't cause any
> > issues or how they would manifest, but this seems like the right fix
> > for this function either way.
> 
> Right; I sent a similar patch a while ago, but it seems to have fallen
> through the cracks:
> 
> https://public-inbox.org/git/d1b58614-989f-5998-6c53-c19eee409a2f@web.de/

Whoops I didn't notice that, I only checked whether the problem still
exists in pu.  I'd be more than happy to go with your patch instead.

> Anyway, your implied question was discussed back then.  Derrick wrote:
> 
>    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.

Thanks for pointing that out!

> Does b6723e4671 in pu (commit-reach: fix first-parent heuristic) change
> that picture?  Did a quick test and found no performance difference with
> and without the fix on top, i.e. proper sorting didn't seem to matter.

I just gave 'test-tool reach can_all_from_reach' a try and got the
same results, with or without the fix the times are very similar.  I
haven't had time to follow the commit-graph series though, so I'm not
sure I used it correctly.  I tried it on the linux repository with the
following input:

X:v4.10
X:v4.9
X:v4.8
X:v4.7
X:v4.6
X:v4.5
X:v4.4
X:v4.3
X:v4.2
X:v4.1
Y:v3.10
Y:v3.9
Y:v3.8
Y:v3.7
Y:v3.6
Y:v3.5
Y:v3.4
Y:v3.3
Y:v3.2
Y:v3.1

> >  commit-reach.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> > 
> > diff --git a/commit-reach.c b/commit-reach.c
> > index bc522d6840..9efddfd7a0 100644
> > --- a/commit-reach.c
> > +++ b/commit-reach.c
> > @@ -516,8 +516,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 **)_a;
> > +	const struct commit *b = *(const struct commit **)_b;
> >  
> >  	if (a->generation < b->generation)
> >  		return -1;
> > 
> 
> Looks good to me.
> 
> René