{"thread":{"id":"49640","subject":"[PATCH] commit-reach: fix sorting commits by generation","startedAt":"2018-10-22T21:10:45Z","lastAt":"2018-10-24T13:19:19Z","messageCount":4,"participants":["Thomas Gummerer","René Scharfe","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"361201","messageId":"20181022211037.22719-1-t.gummerer@gmail.com","threadId":"49640","inReplyTo":null,"subject":"[PATCH] commit-reach: fix sorting commits by generation","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2018-10-22T21:10:37Z","receivedAt":"2018-10-22T21:10:45Z","isPatch":true,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"compare_commit_by_gen is used to sort a list of pointers to 'struct\ncommit'. The comparison function for qsort is called with pointers to\nthe objects it needs to compare, so when sorting a list of 'struct\ncommit *', the arguments are of type 'struct commit **'. However,\ncurrently the comparison function casts it's arguments to 'struct\ncommit *' and uses those, leading to out of bounds memory access and\npotentially to wrong results. Fix that.\n\nSigned-off-by: Thomas Gummerer \n---\n\nI noticed this by running the test suite through valgrind. I'm not\nfamiliar with this code, so I'm not sure why this didn't cause any\nissues or how they would manifest, but this seems like the right fix\nfor this function either way.\n\n commit-reach.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex bc522d6840..9efddfd7a0 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -516,8 +516,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n \n static int compare_commits_by_gen(const void *_a, const void *_b)\n {\n-\tconst struct commit *a = (const struct commit *)_a;\n-\tconst struct commit *b = (const struct commit *)_b;\n+\tconst struct commit *a = *(const struct commit **)_a;\n+\tconst struct commit *b = *(const struct commit **)_b;\n \n \tif (a->generation < b->generation)\n \t\treturn -1;\n-- \n2.19.1.759.g500967bb5e\n\n"},{"id":"361211","messageId":"13bdda53-b751-182b-4aa8-d9a5c03f422d@web.de","threadId":"49640","inReplyTo":"20181022211037.22719-1-t.gummerer@gmail.com","subject":"Re: [PATCH] commit-reach: fix sorting commits by generation","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2018-10-22T21:53:19Z","receivedAt":"2018-10-22T21:53:23Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:\n> compare_commit_by_gen is used to sort a list of pointers to 'struct\n> commit'. The comparison function for qsort is called with pointers to\n> the objects it needs to compare, so when sorting a list of 'struct\n> commit *', the arguments are of type 'struct commit **'. However,\n> currently the comparison function casts it's arguments to 'struct\n> commit *' and uses those, leading to out of bounds memory access and\n> potentially to wrong results. Fix that.\n> \n> Signed-off-by: Thomas Gummerer \n> ---\n> \n> I noticed this by running the test suite through valgrind. I'm not\n> familiar with this code, so I'm not sure why this didn't cause any\n> issues or how they would manifest, but this seems like the right fix\n> for this function either way.\n\nRight; I sent a similar patch a while ago, but it seems to have fallen\nthrough the cracks:\n\nhttps://public-inbox.org/git/d1b58614-989f-5998-6c53-c19eee409a2f@web.de/\n\nAnyway, your implied question was discussed back then. Derrick wrote:\n\n The reason to sort is to hopefully minimize the amount we walk by \n exploring the \"lower\" commits first. This is a performance-only thing, \n not a correctness issue (which is why the bug exists). Even then, it is \n just a heuristic.\n\nDoes b6723e4671 in pu (commit-reach: fix first-parent heuristic) change\nthat picture? Did a quick test and found no performance difference with\nand without the fix on top, i.e. proper sorting didn't seem to matter.\n\n> commit-reach.c | 4 ++--\n> 1 file changed, 2 insertions(+), 2 deletions(-)\n> \n> diff --git a/commit-reach.c b/commit-reach.c\n> index bc522d6840..9efddfd7a0 100644\n> --- a/commit-reach.c\n> +++ b/commit-reach.c\n> @@ -516,8 +516,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n> \n> static int compare_commits_by_gen(const void *_a, const void *_b)\n> {\n> -\tconst struct commit *a = (const struct commit *)_a;\n> -\tconst struct commit *b = (const struct commit *)_b;\n> +\tconst struct commit *a = *(const struct commit **)_a;\n> +\tconst struct commit *b = *(const struct commit **)_b;\n> \n> \tif (a->generation < b->generation)\n> \t\treturn -1;\n> \n\nLooks good to me.\n\nRené\n"},{"id":"361326","messageId":"20181023203237.GF4883@hank.intra.tgummerer.com","threadId":"49640","inReplyTo":"13bdda53-b751-182b-4aa8-d9a5c03f422d@web.de","subject":"Re: [PATCH] commit-reach: fix sorting commits by generation","fromName":"Thomas Gummerer","fromEmail":"t.gummerer@gmail.com","sentAt":"2018-10-23T20:32:38Z","receivedAt":"2018-10-23T20:32:43Z","isPatch":true,"sender":{"key":"t.gummerer@gmail.com","avatar":"https://avatars.githubusercontent.com/u/191004?v=4"},"body":"On 10/22, René Scharfe wrote:\n> Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:\n> > compare_commit_by_gen is used to sort a list of pointers to 'struct\n> > commit'. The comparison function for qsort is called with pointers to\n> > the objects it needs to compare, so when sorting a list of 'struct\n> > commit *', the arguments are of type 'struct commit **'. However,\n> > currently the comparison function casts it's arguments to 'struct\n> > commit *' and uses those, leading to out of bounds memory access and\n> > potentially to wrong results. Fix that.\n> > \n> > Signed-off-by: Thomas Gummerer \n> > ---\n> > \n> > I noticed this by running the test suite through valgrind. I'm not\n> > familiar with this code, so I'm not sure why this didn't cause any\n> > issues or how they would manifest, but this seems like the right fix\n> > for this function either way.\n> \n> Right; I sent a similar patch a while ago, but it seems to have fallen\n> through the cracks:\n> \n> https://public-inbox.org/git/d1b58614-989f-5998-6c53-c19eee409a2f@web.de/\n\nWhoops I didn't notice that, I only checked whether the problem still\nexists in pu. I'd be more than happy to go with your patch instead.\n\n> Anyway, your implied question was discussed back then. Derrick wrote:\n> \n> The reason to sort is to hopefully minimize the amount we walk by \n> exploring the \"lower\" commits first. This is a performance-only thing, \n> not a correctness issue (which is why the bug exists). Even then, it is \n> just a heuristic.\n\nThanks for pointing that out!\n\n> Does b6723e4671 in pu (commit-reach: fix first-parent heuristic) change\n> that picture? Did a quick test and found no performance difference with\n> and without the fix on top, i.e. proper sorting didn't seem to matter.\n\nI just gave 'test-tool reach can_all_from_reach' a try and got the\nsame results, with or without the fix the times are very similar. I\nhaven't had time to follow the commit-graph series though, so I'm not\nsure I used it correctly. I tried it on the linux repository with the\nfollowing input:\n\nX:v4.10\nX:v4.9\nX:v4.8\nX:v4.7\nX:v4.6\nX:v4.5\nX:v4.4\nX:v4.3\nX:v4.2\nX:v4.1\nY:v3.10\nY:v3.9\nY:v3.8\nY:v3.7\nY:v3.6\nY:v3.5\nY:v3.4\nY:v3.3\nY:v3.2\nY:v3.1\n\n> > commit-reach.c | 4 ++--\n> > 1 file changed, 2 insertions(+), 2 deletions(-)\n> > \n> > diff --git a/commit-reach.c b/commit-reach.c\n> > index bc522d6840..9efddfd7a0 100644\n> > --- a/commit-reach.c\n> > +++ b/commit-reach.c\n> > @@ -516,8 +516,8 @@ int commit_contains(struct ref_filter *filter, struct commit *commit,\n> > \n> > static int compare_commits_by_gen(const void *_a, const void *_b)\n> > {\n> > -\tconst struct commit *a = (const struct commit *)_a;\n> > -\tconst struct commit *b = (const struct commit *)_b;\n> > +\tconst struct commit *a = *(const struct commit **)_a;\n> > +\tconst struct commit *b = *(const struct commit **)_b;\n> > \n> > \tif (a->generation < b->generation)\n> > \t\treturn -1;\n> > \n> \n> Looks good to me.\n> \n> René\n"},{"id":"361409","messageId":"e2e1bfd8-bb43-0567-0eb7-770ae16da7e2@gmail.com","threadId":"49640","inReplyTo":"20181023203237.GF4883@hank.intra.tgummerer.com","subject":"Re: [PATCH] commit-reach: fix sorting commits by generation","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2018-10-24T13:19:15Z","receivedAt":"2018-10-24T13:19:19Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 10/23/2018 4:32 PM, Thomas Gummerer wrote:\n> On 10/22, René Scharfe wrote:\n>> Am 22.10.2018 um 23:10 schrieb Thomas Gummerer:\n>>\n>> Anyway, your implied question was discussed back then. Derrick wrote:\n>>\n>> The reason to sort is to hopefully minimize the amount we walk by\n>> exploring the \"lower\" commits first. This is a performance-only thing,\n>> not a correctness issue (which is why the bug exists). Even then, it is\n>> just a heuristic.\n> Thanks for pointing that out!\n>\n>> Does b6723e4671 in pu (commit-reach: fix first-parent heuristic) change\n>> that picture? Did a quick test and found no performance difference with\n>> and without the fix on top, i.e. proper sorting didn't seem to matter.\n> I just gave 'test-tool reach can_all_from_reach' a try and got the\n> same results, with or without the fix the times are very similar. I\n> haven't had time to follow the commit-graph series though, so I'm not\n> sure I used it correctly.\n\nThanks for your attention here. I've been thinking a lot about this \nheuristic and have concluded the following two things are true:\n\n(1) When we return 1, the order that we explore the 'from' commits does \nnot change the explored set of commits.\n\n(2) When we return 0, the order that we explore the 'to' commits will \nchange the explored set, but it is difficult to say that the heuristic \nhelps more than it hurts.\n\nItem (1) is contrary to what I had thought when I first created the \nheuristic.\n\nThe details are tricky, but essentially each DFS starting at a 'from' \ncommit may be short-circuited due to a prior walk, but swapping the \norder of those two 'from' commits would lead to the same set of commits \nto be explored (with the short-circuit happening in the other commit). \nThe only change is that we can terminate early if we fully explore a \n'from' commit and do not find a commit marked with 'with_flag'. In this \nsense, it would be best to explore the commits that are \"closest\" to the \ngeneration number cutoff first, as we can maybe find a negative answer \nearlier in the search.\n\nIn this sense, we could remove the sort entirely and probably not have \nmuch performance hit. But since the set of 'from' commits is probably \nmuch smaller than the set of commits to explore, the sort is likely \ninexpensive.\n\nIn conclusion: I cannot say that this sort is super-important. As for \nthe potential benefits in (2), I'll leave that to people who run git as \na server who may have telemetry around fetch negotiation. How often do \nwe actually say we need more rounds of negotiation? What kinds of data \nshapes matter there?\n\nThanks,\n-Stolee\n"}]}