| Message ID | 5eabbe1c-4c0f-559a-da21-423afec89e7e@web.de (mailing list archive) |
|---|---|
| State | Accepted |
| Commit | 0490b0ffbd6a769b2297947ade97caa93a8d9b95 |
| Headers | show |
| Series | mergesort: avoid left shift overflow | expand |
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 >
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(-)
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(-) > > >
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
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
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é
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.
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.
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
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++;
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(-) -- 2.33.1