{"thread":{"id":"56914","subject":"[PATCH] mergesort: avoid left shift overflow","startedAt":"2021-11-15T23:22:13Z","lastAt":"2021-11-19T21:16:56Z","messageCount":10,"participants":["René Scharfe","Johannes Schindelin","Junio C Hamano","Philip Oakley"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"441192","messageId":"5eabbe1c-4c0f-559a-da21-423afec89e7e@web.de","threadId":"56914","inReplyTo":null,"subject":"[PATCH] mergesort: avoid left shift overflow","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-11-15T23:19:38Z","receivedAt":"2021-11-15T23:22:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Use size_t to match n when building the bitmask for checking whether a\nrank is occupied, instead of the default signed int.\n\nSigned-off-by: René Scharfe \n---\nUgh, sorry. :(\n\n mergesort.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/mergesort.c b/mergesort.c\nindex 6216835566..bd9c6ef8ee 100644\n--- a/mergesort.c\n+++ b/mergesort.c\n@@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n \t\tvoid *next = get_next_fn(list);\n \t\tif (next)\n \t\t\tset_next_fn(list, NULL);\n-\t\tfor (i = 0; n & (1 << i); i++)\n+\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n \t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n \t\t\t\t\t set_next_fn, compare_fn);\n \t\tn++;\n--\n2.33.1\n"},{"id":"441326","messageId":"nycvar.QRO.7.76.6.2111161505500.21127@tvgsbejvaqbjf.bet","threadId":"56914","inReplyTo":"5eabbe1c-4c0f-559a-da21-423afec89e7e@web.de","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-16T14:08:28Z","receivedAt":"2021-11-16T14:08:40Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi René,\n\nOn Tue, 16 Nov 2021, René Scharfe wrote:\n\n> Use size_t to match n when building the bitmask for checking whether a\n> rank is occupied, instead of the default signed int.\n>\n> Signed-off-by: René Scharfe \n> ---\n> Ugh, sorry. :(\n>\n> mergesort.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/mergesort.c b/mergesort.c\n> index 6216835566..bd9c6ef8ee 100644\n> --- a/mergesort.c\n> +++ b/mergesort.c\n> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n> \t\tvoid *next = get_next_fn(list);\n> \t\tif (next)\n> \t\t\tset_next_fn(list, NULL);\n> -\t\tfor (i = 0; n & (1 << i); i++)\n> +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n\nI was a bit concerned about the operator precedence (some of which I\nremember by heart, some not), but according to\nhttps://en.cppreference.com/w/c/language/operator_precedence the cast has\na higher precedence than the shift operator.\n\nI would have preferred an extra pair of parentheses around `(size_t)1` so\nthat I (and other readers) do not have to remember or look up the operator\nprecedence, but it _is_ correct.\n\nCiao,\nDscho\n\n> \t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n> \t\t\t\t\t set_next_fn, compare_fn);\n> \t\tn++;\n> --\n> 2.33.1\n>\n"},{"id":"441422","messageId":"xmqqr1bf2l83.fsf@gitster.g","threadId":"56914","inReplyTo":"nycvar.QRO.7.76.6.2111161505500.21127@tvgsbejvaqbjf.bet","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-11-17T09:19:08Z","receivedAt":"2021-11-17T09:19:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin writes:\n\n>> diff --git a/mergesort.c b/mergesort.c\n>> index 6216835566..bd9c6ef8ee 100644\n>> --- a/mergesort.c\n>> +++ b/mergesort.c\n>> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n>> \t\tvoid *next = get_next_fn(list);\n>> \t\tif (next)\n>> \t\t\tset_next_fn(list, NULL);\n>> -\t\tfor (i = 0; n & (1 << i); i++)\n>> +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n>\n> I was a bit concerned about the operator precedence (some of which I\n> remember by heart, some not), but according to\n> https://en.cppreference.com/w/c/language/operator_precedence the cast has\n> a higher precedence than the shift operator.\n>\n> I would have preferred an extra pair of parentheses around `(size_t)1` so\n> that I (and other readers) do not have to remember or look up the operator\n> precedence, but it _is_ correct.\n\nInteresting.\n\nI do not quite see the need for it myself, but if we wanted to, we\ncan smoke them out with this, I think.\n\n\t$ cat >contrib/coccinelle/cast.cocci <<-\\EOF\n\t@@\n\ttype T;\n\texpression V, C;\n\t@@\n\t-(T) V << C\n\t+((T) V) << C\n\tEOF\n\t$ make contrib/coccinelle/cast.cocci.patch\n\t$ git apply --stat contrib/coccinelle/cast.cocci.patch\n compat/mingw.c | 2 +-\n compat/mingw.c | 2 +-\n ewah/bitmap.c | 2 +-\n ewah/ewok_rlw.h | 6 +++---\n ewah/ewah_bitmap.c | 8 ++++----\n ewah/ewok_rlw.h | 6 +++---\n ppc/sha1.c | 2 +-\n wrapper.c | 2 +-\n 8 files changed, 15 insertions(+), 15 deletions(-)\n\n\n"},{"id":"441535","messageId":"nycvar.QRO.7.76.6.2111180026580.11028@tvgsbejvaqbjf.bet","threadId":"56914","inReplyTo":"xmqqr1bf2l83.fsf@gitster.g","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-17T23:31:04Z","receivedAt":"2021-11-17T23:31:13Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Junio,\n\nOn Wed, 17 Nov 2021, Junio C Hamano wrote:\n\n> Johannes Schindelin writes:\n>\n> >> diff --git a/mergesort.c b/mergesort.c\n> >> index 6216835566..bd9c6ef8ee 100644\n> >> --- a/mergesort.c\n> >> +++ b/mergesort.c\n> >> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n> >> \t\tvoid *next = get_next_fn(list);\n> >> \t\tif (next)\n> >> \t\t\tset_next_fn(list, NULL);\n> >> -\t\tfor (i = 0; n & (1 << i); i++)\n> >> +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n> >\n> > I was a bit concerned about the operator precedence (some of which I\n> > remember by heart, some not), but according to\n> > https://en.cppreference.com/w/c/language/operator_precedence the cast has\n> > a higher precedence than the shift operator.\n> >\n> > I would have preferred an extra pair of parentheses around `(size_t)1` so\n> > that I (and other readers) do not have to remember or look up the operator\n> > precedence, but it _is_ correct.\n>\n> Interesting.\n>\n> I do not quite see the need for it myself, but if we wanted to, we\n> can smoke them out with this, I think.\n>\n> \t$ cat >contrib/coccinelle/cast.cocci <<-\\EOF\n> \t@@\n> \ttype T;\n> \texpression V, C;\n> \t@@\n> \t-(T) V << C\n> \t+((T) V) << C\n> \tEOF\n\nCute.\n\nHowever, I am not a fan of fixing what ain't broken (the many refactorings\nin v2.34.0 did cause quite some fall-out work in git-for-windows/git and\nmicrosoft/git, after all, and at least _I_ do not yet see much benefit to\nshow for that price we paid for those refactorings).\n\nAnd the primary benefit of enclosing the left operand in parentheses is to\nmake reviews easier, so I would prefer to leave existing (read:\n_already-reviewed_) code alone.\n\nThanks,\nDscho\n\n> \t$ make contrib/coccinelle/cast.cocci.patch\n> \t$ git apply --stat contrib/coccinelle/cast.cocci.patch\n> compat/mingw.c | 2 +-\n> compat/mingw.c | 2 +-\n> ewah/bitmap.c | 2 +-\n> ewah/ewok_rlw.h | 6 +++---\n> ewah/ewah_bitmap.c | 8 ++++----\n> ewah/ewok_rlw.h | 6 +++---\n> ppc/sha1.c | 2 +-\n> wrapper.c | 2 +-\n> 8 files changed, 15 insertions(+), 15 deletions(-)\n>\n>\n>\n"},{"id":"441673","messageId":"7fbd4cf4-5f66-a4cd-0c41-e5b12d14d761@iee.email","threadId":"56914","inReplyTo":"5eabbe1c-4c0f-559a-da21-423afec89e7e@web.de","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-11-18T23:27:31Z","receivedAt":"2021-11-18T23:27:34Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 15/11/2021 23:19, René Scharfe wrote:\n> Use size_t to match n when building the bitmask for checking whether a\n> rank is occupied, instead of the default signed int.\n>\n> Signed-off-by: René Scharfe \n> ---\n> Ugh, sorry. :(\n>\n> mergesort.c | 2 +-\n> 1 file changed, 1 insertion(+), 1 deletion(-)\n>\n> diff --git a/mergesort.c b/mergesort.c\n> index 6216835566..bd9c6ef8ee 100644\n> --- a/mergesort.c\n> +++ b/mergesort.c\n> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n> \t\tvoid *next = get_next_fn(list);\n> \t\tif (next)\n> \t\t\tset_next_fn(list, NULL);\n> -\t\tfor (i = 0; n & (1 << i); i++)\n> +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n> \t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n> \t\t\t\t\t set_next_fn, compare_fn);\n> \t\tn++;\n> --\n> 2.33.1\nLooks good to me.\n\nI already had this locally as part of an MSVC (Visual Studio) fix for\nthe various C4334 warnings.\n\nThe other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,\nand repack.c.\n\nMy patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n\nPhilip\n"},{"id":"441759","messageId":"nycvar.QRO.7.76.6.2111191750400.63@tvgsbejvaqbjf.bet","threadId":"56914","inReplyTo":"7fbd4cf4-5f66-a4cd-0c41-e5b12d14d761@iee.email","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-11-19T16:51:59Z","receivedAt":"2021-11-19T16:52:09Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Philip,\n\nOn Thu, 18 Nov 2021, Philip Oakley wrote:\n\n> On 15/11/2021 23:19, René Scharfe wrote:\n> > Use size_t to match n when building the bitmask for checking whether a\n> > rank is occupied, instead of the default signed int.\n> >\n> > Signed-off-by: René Scharfe \n> > ---\n> > Ugh, sorry. :(\n> >\n> > mergesort.c | 2 +-\n> > 1 file changed, 1 insertion(+), 1 deletion(-)\n> >\n> > diff --git a/mergesort.c b/mergesort.c\n> > index 6216835566..bd9c6ef8ee 100644\n> > --- a/mergesort.c\n> > +++ b/mergesort.c\n> > @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n> > \t\tvoid *next = get_next_fn(list);\n> > \t\tif (next)\n> > \t\t\tset_next_fn(list, NULL);\n> > -\t\tfor (i = 0; n & (1 << i); i++)\n> > +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n> > \t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n> > \t\t\t\t\t set_next_fn, compare_fn);\n> > \t\tn++;\n> > --\n> > 2.33.1\n> Looks good to me.\n>\n> I already had this locally as part of an MSVC (Visual Studio) fix for\n> the various C4334 warnings.\n>\n> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,\n> and repack.c.\n>\n> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n\nHow about rebasing the remaining patches from\nhttps://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t\non top of `rs/mergesort` and then submitting them, to avoid duplicate\nefforts?\n\nCiao,\nDscho\n"},{"id":"441766","messageId":"fb70a801-369b-c1b1-457b-bab06688b2bc@web.de","threadId":"56914","inReplyTo":"nycvar.QRO.7.76.6.2111191750400.63@tvgsbejvaqbjf.bet","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2021-11-19T17:15:34Z","receivedAt":"2021-11-19T17:15:45Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 19.11.21 um 17:51 schrieb Johannes Schindelin:\n> Hi Philip,\n>\n> On Thu, 18 Nov 2021, Philip Oakley wrote:\n>\n>> I already had this locally as part of an MSVC (Visual Studio) fix for\n>> the various C4334 warnings.\n>>\n>> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,\n>> and repack.c.\n>>\n>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n\nGood warning, that. And scary stuff.\n\nbuiltin/repack.c shifts by 5, diffcore-delta.c by at most 17 IIUC, and\nobject-file.c by at most 31, which should all be safe. Shifting by 32\nor more would push the 1 off the right end, leaving only a surprising 0.\nPhew! Definitely worth fixing regardless.\n\n> How about rebasing the remaining patches from\n> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t\n> on top of `rs/mergesort` and then submitting them, to avoid duplicate\n> efforts?\n\nThat would be nice. I'd also don't mind if Junio took the whole set\nincl. the mergesort.c change instead.\n\nRené\n"},{"id":"441768","messageId":"05e6c0ab-7364-56d8-f0b2-e93c11b327e3@iee.email","threadId":"56914","inReplyTo":"nycvar.QRO.7.76.6.2111191750400.63@tvgsbejvaqbjf.bet","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-11-19T17:27:23Z","receivedAt":"2021-11-19T17:27:25Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 19/11/2021 16:51, Johannes Schindelin wrote:\n> Hi Philip,\n>\n> On Thu, 18 Nov 2021, Philip Oakley wrote:\n>\n>> On 15/11/2021 23:19, René Scharfe wrote:\n>>> Use size_t to match n when building the bitmask for checking whether a\n>>> rank is occupied, instead of the default signed int.\n>>>\n>>> Signed-off-by: René Scharfe \n>>> ---\n>>> Ugh, sorry. :(\n>>>\n>>> mergesort.c | 2 +-\n>>> 1 file changed, 1 insertion(+), 1 deletion(-)\n>>>\n>>> diff --git a/mergesort.c b/mergesort.c\n>>> index 6216835566..bd9c6ef8ee 100644\n>>> --- a/mergesort.c\n>>> +++ b/mergesort.c\n>>> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,\n>>> \t\tvoid *next = get_next_fn(list);\n>>> \t\tif (next)\n>>> \t\t\tset_next_fn(list, NULL);\n>>> -\t\tfor (i = 0; n & (1 << i); i++)\n>>> +\t\tfor (i = 0; n & ((size_t)1 << i); i++)\n>>> \t\t\tlist = llist_merge(ranks[i], list, get_next_fn,\n>>> \t\t\t\t\t set_next_fn, compare_fn);\n>>> \t\tn++;\n>>> --\n>>> 2.33.1\n>> Looks good to me.\n>>\n>> I already had this locally as part of an MSVC (Visual Studio) fix for\n>> the various C4334 warnings.\n>>\n>> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,\n>> and repack.c.\n>>\n>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n> How about rebasing the remaining patches from\n> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t\n> on top of `rs/mergesort` and then submitting them, to avoid duplicate\n> efforts?\n>\nI'm not finding a `rs/mergesort` at the  moment. Any particular remote I\nshould find it on, or maybe a different spelling?\nP.\n"},{"id":"441776","messageId":"xmqqlf1kosgp.fsf@gitster.g","threadId":"56914","inReplyTo":"05e6c0ab-7364-56d8-f0b2-e93c11b327e3@iee.email","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-11-19T19:28:38Z","receivedAt":"2021-11-19T19:28:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Philip Oakley writes:\n\n>>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n>> How about rebasing the remaining patches from\n>> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t\n>> on top of `rs/mergesort` and then submitting them, to avoid duplicate\n>> efforts?\n>>\n> I'm not finding a `rs/mergesort` at the moment. Any particular remote I\n> should find it on, or maybe a different spelling?\n> P.\n\nAt https://github.com/gitster/git/, I publish the \"broken out\"\nbranches.\n\nBut resurrecting the tips of the topics should be fairly easy.\n\n$ git log --first-parent --oneline origin/master..origin/seen |\n grep rs/mergesort\n\nThe second parent of that merge is the tip of rs/mergesort topic\nback when the 'seen' integration branch was created.\n\n"},{"id":"441792","messageId":"d9cdb708-1cd1-03e1-ea17-4195faafda76@iee.email","threadId":"56914","inReplyTo":"xmqqlf1kosgp.fsf@gitster.g","subject":"Re: [PATCH] mergesort: avoid left shift overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-11-19T21:16:52Z","receivedAt":"2021-11-19T21:16:56Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 19/11/2021 19:28, Junio C Hamano wrote:\n> Philip Oakley writes:\n>\n>>>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t\n>>> How about rebasing the remaining patches from\n>>> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t\n>>> on top of `rs/mergesort` and then submitting them, to avoid duplicate\n>>> efforts?\n>>>\n>> I'm not finding a `rs/mergesort` at the moment. Any particular remote I\n>> should find it on, or maybe a different spelling?\n>> P.\n> At https://github.com/gitster/git/, I publish the \"broken out\"\n> branches.\n>\n> But resurrecting the tips of the topics should be fairly easy.\n>\n> $ git log --first-parent --oneline origin/master..origin/seen |\n> grep rs/mergesort\n>\n> The second parent of that merge is the tip of rs/mergesort topic\n> back when the 'seen' integration branch was created.\n>\nThanks. I'd been browsing via `gitk` and hadn't included all the tips,\nso couldn't find it at that point. I've got it now:  42c456ff81\n(mergesort: avoid left shift overflow, 2021-11-16).\n\nPhilip\n"}]}