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@xxxxxxxxx> > > --- > > > > 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@xxxxxx/ 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é
