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 <[email protected]>
> > ---
> >
> > 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/[email protected]/
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é
