[PATCH] mergesort: avoid left shift overflow

[PATCH] mergesort: avoid left shift overflow

[René Scharfe]

Use size_t to match n when building the bitmask for checking whether a
rank is occupied, instead of the default signed int.

Signed-off-by: René Scharfe <l.s.r@web.de>
---
Ugh, sorry. :(

 mergesort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/mergesort.c b/mergesort.c
index 6216835566..bd9c6ef8ee 100644
--- a/mergesort.c
+++ b/mergesort.c
@@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
 		void *next = get_next_fn(list);
 		if (next)
 			set_next_fn(list, NULL);
-		for (i = 0; n & (1 << i); i++)
+		for (i = 0; n & ((size_t)1 << i); i++)
 			list = llist_merge(ranks[i], list, get_next_fn,
 					   set_next_fn, compare_fn);
 		n++;
--
2.33.1

Re: [PATCH] mergesort: avoid left shift overflow

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 1257 bytes --]

Hi René,

On Tue, 16 Nov 2021, René Scharfe wrote:

> Use size_t to match n when building the bitmask for checking whether a
> rank is occupied, instead of the default signed int.
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> Ugh, sorry. :(
>
>  mergesort.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/mergesort.c b/mergesort.c
> index 6216835566..bd9c6ef8ee 100644
> --- a/mergesort.c
> +++ b/mergesort.c
> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
>  		void *next = get_next_fn(list);
>  		if (next)
>  			set_next_fn(list, NULL);
> -		for (i = 0; n & (1 << i); i++)
> +		for (i = 0; n & ((size_t)1 << i); i++)

I was a bit concerned about the operator precedence (some of which I
remember by heart, some not), but according to
https://en.cppreference.com/w/c/language/operator_precedence the cast has
a higher precedence than the shift operator.

I would have preferred an extra pair of parentheses around `(size_t)1` so
that I (and other readers) do not have to remember or look up the operator
precedence, but it _is_ correct.

Ciao,
Dscho

>  			list = llist_merge(ranks[i], list, get_next_fn,
>  					   set_next_fn, compare_fn);
>  		n++;
> --
> 2.33.1
>

Re: [PATCH] mergesort: avoid left shift overflow

[Junio C Hamano]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

>> diff --git a/mergesort.c b/mergesort.c
>> index 6216835566..bd9c6ef8ee 100644
>> --- a/mergesort.c
>> +++ b/mergesort.c
>> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
>>  		void *next = get_next_fn(list);
>>  		if (next)
>>  			set_next_fn(list, NULL);
>> -		for (i = 0; n & (1 << i); i++)
>> +		for (i = 0; n & ((size_t)1 << i); i++)
>
> I was a bit concerned about the operator precedence (some of which I
> remember by heart, some not), but according to
> https://en.cppreference.com/w/c/language/operator_precedence the cast has
> a higher precedence than the shift operator.
>
> I would have preferred an extra pair of parentheses around `(size_t)1` so
> that I (and other readers) do not have to remember or look up the operator
> precedence, but it _is_ correct.

Interesting.

I do not quite see the need for it myself, but if we wanted to, we
can smoke them out with this, I think.

	$ cat >contrib/coccinelle/cast.cocci <<-\EOF
	@@
	type T;
	expression V, C;
	@@
	-(T) V << C
	+((T) V) << C
	EOF
	$ make contrib/coccinelle/cast.cocci.patch
	$ git apply --stat contrib/coccinelle/cast.cocci.patch
         compat/mingw.c     |    2 +-
         compat/mingw.c     |    2 +-
         ewah/bitmap.c      |    2 +-
         ewah/ewok_rlw.h    |    6 +++---
         ewah/ewah_bitmap.c |    8 ++++----
         ewah/ewok_rlw.h    |    6 +++---
         ppc/sha1.c         |    2 +-
         wrapper.c          |    2 +-
         8 files changed, 15 insertions(+), 15 deletions(-)

Re: [PATCH] mergesort: avoid left shift overflow

[Johannes Schindelin]

Hi Junio,

On Wed, 17 Nov 2021, Junio C Hamano wrote:

> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:
>
> >> diff --git a/mergesort.c b/mergesort.c
> >> index 6216835566..bd9c6ef8ee 100644
> >> --- a/mergesort.c
> >> +++ b/mergesort.c
> >> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
> >>  		void *next = get_next_fn(list);
> >>  		if (next)
> >>  			set_next_fn(list, NULL);
> >> -		for (i = 0; n & (1 << i); i++)
> >> +		for (i = 0; n & ((size_t)1 << i); i++)
> >
> > I was a bit concerned about the operator precedence (some of which I
> > remember by heart, some not), but according to
> > https://en.cppreference.com/w/c/language/operator_precedence the cast has
> > a higher precedence than the shift operator.
> >
> > I would have preferred an extra pair of parentheses around `(size_t)1` so
> > that I (and other readers) do not have to remember or look up the operator
> > precedence, but it _is_ correct.
>
> Interesting.
>
> I do not quite see the need for it myself, but if we wanted to, we
> can smoke them out with this, I think.
>
> 	$ cat >contrib/coccinelle/cast.cocci <<-\EOF
> 	@@
> 	type T;
> 	expression V, C;
> 	@@
> 	-(T) V << C
> 	+((T) V) << C
> 	EOF

Cute.

However, I am not a fan of fixing what ain't broken (the many refactorings
in v2.34.0 did cause quite some fall-out work in git-for-windows/git and
microsoft/git, after all, and at least _I_ do not yet see much benefit to
show for that price we paid for those refactorings).

And the primary benefit of enclosing the left operand in parentheses is to
make reviews easier, so I would prefer to leave existing (read:
_already-reviewed_) code alone.

Thanks,
Dscho

> 	$ make contrib/coccinelle/cast.cocci.patch
> 	$ git apply --stat contrib/coccinelle/cast.cocci.patch
>          compat/mingw.c     |    2 +-
>          compat/mingw.c     |    2 +-
>          ewah/bitmap.c      |    2 +-
>          ewah/ewok_rlw.h    |    6 +++---
>          ewah/ewah_bitmap.c |    8 ++++----
>          ewah/ewok_rlw.h    |    6 +++---
>          ppc/sha1.c         |    2 +-
>          wrapper.c          |    2 +-
>          8 files changed, 15 insertions(+), 15 deletions(-)
>
>
>

Re: [PATCH] mergesort: avoid left shift overflow

[Philip Oakley]

On 15/11/2021 23:19, René Scharfe wrote:
> Use size_t to match n when building the bitmask for checking whether a
> rank is occupied, instead of the default signed int.
>
> Signed-off-by: René Scharfe <l.s.r@web.de>
> ---
> Ugh, sorry. :(
>
>  mergesort.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/mergesort.c b/mergesort.c
> index 6216835566..bd9c6ef8ee 100644
> --- a/mergesort.c
> +++ b/mergesort.c
> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
>  		void *next = get_next_fn(list);
>  		if (next)
>  			set_next_fn(list, NULL);
> -		for (i = 0; n & (1 << i); i++)
> +		for (i = 0; n & ((size_t)1 << i); i++)
>  			list = llist_merge(ranks[i], list, get_next_fn,
>  					   set_next_fn, compare_fn);
>  		n++;
> --
> 2.33.1
Looks good to me.

I already had this locally as part of an MSVC (Visual Studio) fix for
the various C4334 warnings.

The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,
and repack.c.

My patches are in https://github.com/PhilipOakley/git/tree/oneU_t

Philip

Re: [PATCH] mergesort: avoid left shift overflow

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 1421 bytes --]

Hi Philip,

On Thu, 18 Nov 2021, Philip Oakley wrote:

> On 15/11/2021 23:19, René Scharfe wrote:
> > Use size_t to match n when building the bitmask for checking whether a
> > rank is occupied, instead of the default signed int.
> >
> > Signed-off-by: René Scharfe <l.s.r@web.de>
> > ---
> > Ugh, sorry. :(
> >
> >  mergesort.c | 2 +-
> >  1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/mergesort.c b/mergesort.c
> > index 6216835566..bd9c6ef8ee 100644
> > --- a/mergesort.c
> > +++ b/mergesort.c
> > @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
> >  		void *next = get_next_fn(list);
> >  		if (next)
> >  			set_next_fn(list, NULL);
> > -		for (i = 0; n & (1 << i); i++)
> > +		for (i = 0; n & ((size_t)1 << i); i++)
> >  			list = llist_merge(ranks[i], list, get_next_fn,
> >  					   set_next_fn, compare_fn);
> >  		n++;
> > --
> > 2.33.1
> Looks good to me.
>
> I already had this locally as part of an MSVC (Visual Studio) fix for
> the various C4334 warnings.
>
> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,
> and repack.c.
>
> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t

How about rebasing the remaining patches from
https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t
on top of `rs/mergesort` and then submitting them, to avoid duplicate
efforts?

Ciao,
Dscho

Re: [PATCH] mergesort: avoid left shift overflow

[René Scharfe]

Am 19.11.21 um 17:51 schrieb Johannes Schindelin:
> Hi Philip,
>
> On Thu, 18 Nov 2021, Philip Oakley wrote:
>
>> I already had this locally as part of an MSVC (Visual Studio) fix for
>> the various C4334 warnings.
>>
>> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,
>> and repack.c.
>>
>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t

Good warning, that.  And scary stuff.

builtin/repack.c shifts by 5, diffcore-delta.c by at most 17 IIUC, and
object-file.c by at most 31, which should all be safe.  Shifting by 32
or more would push the 1 off the right end, leaving only a surprising 0.
Phew!  Definitely worth fixing regardless.

> How about rebasing the remaining patches from
> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t
> on top of `rs/mergesort` and then submitting them, to avoid duplicate
> efforts?

That would be nice.  I'd also don't mind if Junio took the whole set
incl. the mergesort.c change instead.

René

Re: [PATCH] mergesort: avoid left shift overflow

[Philip Oakley]

On 19/11/2021 16:51, Johannes Schindelin wrote:
> Hi Philip,
>
> On Thu, 18 Nov 2021, Philip Oakley wrote:
>
>> On 15/11/2021 23:19, René Scharfe wrote:
>>> Use size_t to match n when building the bitmask for checking whether a
>>> rank is occupied, instead of the default signed int.
>>>
>>> Signed-off-by: René Scharfe <l.s.r@web.de>
>>> ---
>>> Ugh, sorry. :(
>>>
>>>  mergesort.c | 2 +-
>>>  1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/mergesort.c b/mergesort.c
>>> index 6216835566..bd9c6ef8ee 100644
>>> --- a/mergesort.c
>>> +++ b/mergesort.c
>>> @@ -63,7 +63,7 @@ void *llist_mergesort(void *list,
>>>  		void *next = get_next_fn(list);
>>>  		if (next)
>>>  			set_next_fn(list, NULL);
>>> -		for (i = 0; n & (1 << i); i++)
>>> +		for (i = 0; n & ((size_t)1 << i); i++)
>>>  			list = llist_merge(ranks[i], list, get_next_fn,
>>>  					   set_next_fn, compare_fn);
>>>  		n++;
>>> --
>>> 2.33.1
>> Looks good to me.
>>
>> I already had this locally as part of an MSVC (Visual Studio) fix for
>> the various C4334 warnings.
>>
>> The other cases are in object-file.c, diffcore-delta.c (2 occurrences) ,
>> and repack.c.
>>
>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t
> How about rebasing the remaining patches from
> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t
> on top of `rs/mergesort` and then submitting them, to avoid duplicate
> efforts?
>
I'm not finding a `rs/mergesort` at the  moment. Any particular remote I
should find it on, or maybe a different spelling?
P.

Re: [PATCH] mergesort: avoid left shift overflow

[Junio C Hamano]

Philip Oakley <philipoakley@iee.email> writes:

>>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t
>> How about rebasing the remaining patches from
>> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t
>> on top of `rs/mergesort` and then submitting them, to avoid duplicate
>> efforts?
>>
> I'm not finding a `rs/mergesort` at the moment. Any particular remote I
> should find it on, or maybe a different spelling?
> P.

At https://github.com/gitster/git/, I publish the "broken out"
branches.

But resurrecting the tips of the topics should be fairly easy.

$ git log --first-parent --oneline origin/master..origin/seen |
  grep rs/mergesort

The second parent of that merge is the tip of rs/mergesort topic
back when the 'seen' integration branch was created.

Re: [PATCH] mergesort: avoid left shift overflow

[Philip Oakley]

On 19/11/2021 19:28, Junio C Hamano wrote:
> Philip Oakley <philipoakley@iee.email> writes:
>
>>>> My patches are in https://github.com/PhilipOakley/git/tree/oneU_t
>>> How about rebasing the remaining patches from
>>> https://github.com/git-for-windows/git/compare/main...PhilipOakley:oneU_t
>>> on top of `rs/mergesort` and then submitting them, to avoid duplicate
>>> efforts?
>>>
>> I'm not finding a `rs/mergesort` at the moment. Any particular remote I
>> should find it on, or maybe a different spelling?
>> P.
> At https://github.com/gitster/git/, I publish the "broken out"
> branches.
>
> But resurrecting the tips of the topics should be fairly easy.
>
> $ git log --first-parent --oneline origin/master..origin/seen |
>   grep rs/mergesort
>
> The second parent of that merge is the tip of rs/mergesort topic
> back when the 'seen' integration branch was created.
>
Thanks. I'd been browsing via `gitk` and hadn't included all the tips,
so couldn't find it at that point. I've got it now:  42c456ff81
(mergesort: avoid left shift overflow, 2021-11-16).

Philip