[Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

It seems like there's no good reason for the compiler to exploit the
undefinedness of left shifts.  GCC explicitly documents that they do not
use at all this possibility and, while they also say this is subject
to change, they have been saying this for 10 years (since the wording
appeared in the GCC 4.0 manual).

Any workaround for this particular case of undefined behavior uglifies the
code.  Using unsigned is unsafe (https://github.com/madler/zlib/pull/112
is the proof) because the value becomes positive when extended; -(a << b)
works but does not express that the intention is to compute -a * 2^N,
especially if "a" is a constant.

<rant>
The straw that broke the camel back is Clang's latest obnoxious,
pointless, unsafe---and did I mention *totally* useless---warning about
left shifting a negative integer.  It's obnoxious and pointless because
the compiler is not using the latitude that the standard gives it, so
the warning just adds noise.  It is useless and unsafe because it does
not catch the widely more common case where the LHS is a variable, and
thus gives a false sense of security.  The noisy nature of the warning
means that it should have never been added to -Wall.  The uselessness
means that it probably should not have even been added to -Wextra.

(It would have made sense to enable the warning for -fsanitize=shift,
as the program would always crash if the point is reached.  But this was
probably too sophisticated to come up with, when you're so busy giving
birth to gems such as -Wabsolute-value).
</rant>

Ubsan also has warnings for undefined behavior of left shifts.  Checks for
left shift overflow and left shift of negative numbers, unfortunately,
cannot be silenced without also silencing the useful ones about out-of-range
shift amounts. -fwrapv ought to shut them up, but doesn't yet
(https://llvm.org/bugs/show_bug.cgi?id=25552; I am taking care of fixing
the same issues in GCC).  Luckily ubsan is optional, and the easy
workaround is to use -fsanitize-recover.

Anyhow, this patch documents our assumptions explicitly, and shuts up the
stupid warning.  -fwrapv is a bit of a heavy hammer, but it is the safest
option and it ought to just work long term as the compilers improve.

Thanks to everyone involved in the discussion!

Cc: Peter Maydell <peter.maydell@linaro.org>
Cc: Markus Armbruster <armbru@redhat.com>
Cc: Laszlo Ersek <lersek@redhat.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
---
 HACKING   | 6 ++++++
 configure | 4 ++--
 2 files changed, 8 insertions(+), 2 deletions(-)

diff --git a/HACKING b/HACKING
index 12fbc8a..71ad23b 100644
--- a/HACKING
+++ b/HACKING
@@ -157,3 +157,9 @@ painful. These are:
  * you may assume that integers are 2s complement representation
  * you may assume that right shift of a signed integer duplicates
    the sign bit (ie it is an arithmetic shift, not a logical shift)
+
+In addition, QEMU assumes that the compiler does not use the latitude
+given in C99 and C11 to treat aspects of signed '<<' as undefined, as
+documented in the GNU Compiler Collection manual starting at version 4.0.
+If a compiler does not respect this when passed the -fwrapv option,
+it is not supported for compilation of QEMU.
diff --git a/configure b/configure
index 6bfa6f5..aa0a6c8 100755
--- a/configure
+++ b/configure
@@ -380,7 +380,7 @@ sdl2_config="${SDL2_CONFIG-${cross_prefix}sdl2-config}"
 ARFLAGS="${ARFLAGS-rv}"
 
 # default flags for all hosts
-QEMU_CFLAGS="-fno-strict-aliasing -fno-common $QEMU_CFLAGS"
+QEMU_CFLAGS="-fno-strict-aliasing -fno-common -fwrapv $QEMU_CFLAGS"
 QEMU_CFLAGS="-Wall -Wundef -Wwrite-strings -Wmissing-prototypes $QEMU_CFLAGS"
 QEMU_CFLAGS="-Wstrict-prototypes -Wredundant-decls $QEMU_CFLAGS"
 QEMU_CFLAGS="-D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE $QEMU_CFLAGS"
@@ -1428,7 +1428,7 @@ fi
 gcc_flags="-Wold-style-declaration -Wold-style-definition -Wtype-limits"
 gcc_flags="-Wformat-security -Wformat-y2k -Winit-self -Wignored-qualifiers $gcc_flags"
 gcc_flags="-Wmissing-include-dirs -Wempty-body -Wnested-externs $gcc_flags"
-gcc_flags="-Wendif-labels $gcc_flags"
+gcc_flags="-Wendif-labels -Wno-shift-negative-value $gcc_flags"
 gcc_flags="-Wno-initializer-overrides $gcc_flags"
 gcc_flags="-Wno-string-plus-int $gcc_flags"
 # Note that we do not add -Werror to gcc_flags here, because that would
-- 
2.5.0

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Laszlo Ersek]

On 11/17/15 15:09, Paolo Bonzini wrote:
> It seems like there's no good reason for the compiler to exploit the
> undefinedness of left shifts.  GCC explicitly documents that they do not
> use at all this possibility and, while they also say this is subject
> to change, they have been saying this for 10 years (since the wording
> appeared in the GCC 4.0 manual).
> 
> Any workaround for this particular case of undefined behavior uglifies the
> code.  Using unsigned is unsafe (https://github.com/madler/zlib/pull/112
> is the proof) because the value becomes positive when extended; -(a << b)
> works but does not express that the intention is to compute -a * 2^N,
> especially if "a" is a constant.
> 
> <rant>
> The straw that broke the camel back is Clang's latest obnoxious,
> pointless, unsafe---and did I mention *totally* useless---warning about
> left shifting a negative integer.  It's obnoxious and pointless because
> the compiler is not using the latitude that the standard gives it, so
> the warning just adds noise.  It is useless and unsafe because it does
> not catch the widely more common case where the LHS is a variable, and
> thus gives a false sense of security.  The noisy nature of the warning
> means that it should have never been added to -Wall.  The uselessness
> means that it probably should not have even been added to -Wextra.
> 
> (It would have made sense to enable the warning for -fsanitize=shift,
> as the program would always crash if the point is reached.  But this was
> probably too sophisticated to come up with, when you're so busy giving
> birth to gems such as -Wabsolute-value).
> </rant>
> 
> Ubsan also has warnings for undefined behavior of left shifts.  Checks for
> left shift overflow and left shift of negative numbers, unfortunately,
> cannot be silenced without also silencing the useful ones about out-of-range
> shift amounts. -fwrapv ought to shut them up, but doesn't yet
> (https://llvm.org/bugs/show_bug.cgi?id=25552; I am taking care of fixing
> the same issues in GCC).  Luckily ubsan is optional, and the easy
> workaround is to use -fsanitize-recover.
> 
> Anyhow, this patch documents our assumptions explicitly, and shuts up the
> stupid warning.  -fwrapv is a bit of a heavy hammer, but it is the safest
> option and it ought to just work long term as the compilers improve.
> 
> Thanks to everyone involved in the discussion!
> 
> Cc: Peter Maydell <peter.maydell@linaro.org>
> Cc: Markus Armbruster <armbru@redhat.com>
> Cc: Laszlo Ersek <lersek@redhat.com>
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
> ---
>  HACKING   | 6 ++++++
>  configure | 4 ++--
>  2 files changed, 8 insertions(+), 2 deletions(-)
> 
> diff --git a/HACKING b/HACKING
> index 12fbc8a..71ad23b 100644
> --- a/HACKING
> +++ b/HACKING
> @@ -157,3 +157,9 @@ painful. These are:
>   * you may assume that integers are 2s complement representation
>   * you may assume that right shift of a signed integer duplicates
>     the sign bit (ie it is an arithmetic shift, not a logical shift)
> +
> +In addition, QEMU assumes that the compiler does not use the latitude
> +given in C99 and C11 to treat aspects of signed '<<' as undefined, as
> +documented in the GNU Compiler Collection manual starting at version 4.0.
> +If a compiler does not respect this when passed the -fwrapv option,
> +it is not supported for compilation of QEMU.
> diff --git a/configure b/configure
> index 6bfa6f5..aa0a6c8 100755
> --- a/configure
> +++ b/configure
> @@ -380,7 +380,7 @@ sdl2_config="${SDL2_CONFIG-${cross_prefix}sdl2-config}"
>  ARFLAGS="${ARFLAGS-rv}"
>  
>  # default flags for all hosts
> -QEMU_CFLAGS="-fno-strict-aliasing -fno-common $QEMU_CFLAGS"
> +QEMU_CFLAGS="-fno-strict-aliasing -fno-common -fwrapv $QEMU_CFLAGS"
>  QEMU_CFLAGS="-Wall -Wundef -Wwrite-strings -Wmissing-prototypes $QEMU_CFLAGS"
>  QEMU_CFLAGS="-Wstrict-prototypes -Wredundant-decls $QEMU_CFLAGS"
>  QEMU_CFLAGS="-D_GNU_SOURCE -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE $QEMU_CFLAGS"
> @@ -1428,7 +1428,7 @@ fi
>  gcc_flags="-Wold-style-declaration -Wold-style-definition -Wtype-limits"
>  gcc_flags="-Wformat-security -Wformat-y2k -Winit-self -Wignored-qualifiers $gcc_flags"
>  gcc_flags="-Wmissing-include-dirs -Wempty-body -Wnested-externs $gcc_flags"
> -gcc_flags="-Wendif-labels $gcc_flags"
> +gcc_flags="-Wendif-labels -Wno-shift-negative-value $gcc_flags"
>  gcc_flags="-Wno-initializer-overrides $gcc_flags"
>  gcc_flags="-Wno-string-plus-int $gcc_flags"
>  # Note that we do not add -Werror to gcc_flags here, because that would
> 

I accept this is a defensible, maybe even reasonable choice to make in
the QEMU project. On the other hand, I personally cannot stop hating
shifting negative values (any direction) -- indeed, the *original* code
from <https://github.com/madler/zlib/pull/112> makes me barf too.

Therefore,

Grudgingly-reviewed-by: Laszlo Ersek <lersek@redhat.com>

(I realize the flag for the pointer wraparound has been separated; this
is strictly about shifts.)

Thanks
Laszlo

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Laszlo Ersek <lersek@redhat.com> writes:

> I accept this is a defensible, maybe even reasonable choice to make in
> the QEMU project. On the other hand, I personally cannot stop hating
> shifting negative values (any direction) -- indeed, the *original* code
> from <https://github.com/madler/zlib/pull/112> makes me barf too.
>
> Therefore,
>
> Grudgingly-reviewed-by: Laszlo Ersek <lersek@redhat.com>
>
> (I realize the flag for the pointer wraparound has been separated; this
> is strictly about shifts.)

What's so abhorrent about shifting negative values?  I know machines
with signed integer representations other than twos complement exist, as
do machines that can't do both logical and arithmetic shifts.  Mostly
inside computer museums, though.

C was standardized at a time when keeping the language sufficiently
loose to permit efficient implementation on these oddball machines made
a lot more sense than it does now.  Making it undefined behavior went
too far, though.  Implementation-defined or unspecified behavior would
have sufficed.

Learn to stop worrying and love the signed shifts :)

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Laszlo Ersek]

On 11/17/15 16:47, Markus Armbruster wrote:
> Laszlo Ersek <lersek@redhat.com> writes:
> 
>> I accept this is a defensible, maybe even reasonable choice to make in
>> the QEMU project. On the other hand, I personally cannot stop hating
>> shifting negative values (any direction) -- indeed, the *original* code
>> from <https://github.com/madler/zlib/pull/112> makes me barf too.
>>
>> Therefore,
>>
>> Grudgingly-reviewed-by: Laszlo Ersek <lersek@redhat.com>
>>
>> (I realize the flag for the pointer wraparound has been separated; this
>> is strictly about shifts.)
> 
> What's so abhorrent about shifting negative values?  I know machines
> with signed integer representations other than twos complement exist, as
> do machines that can't do both logical and arithmetic shifts.  Mostly
> inside computer museums, though.
> 
> C was standardized at a time when keeping the language sufficiently
> loose to permit efficient implementation on these oddball machines made
> a lot more sense than it does now.  Making it undefined behavior went
> too far, though.  Implementation-defined or unspecified behavior would
> have sufficed.
> 
> Learn to stop worrying and love the signed shifts :)

I'm not worried. I hate it for the mental load it represents.

For me, the fact that the negative sign is encoded (with *any* kind of
representation) within the bit pattern subject to shifting, makes the
negative sign *inherently* incompatible with shifting.

In real life, *you don't shift a sign*. It just makes no sense. The sign
is not a digit. You can append or cut off zeroes from the right, but the
sign is not subject to that. The sign doesn't care.

When you shift nonzero bits out of an unsigned variable to the left, its
value changes in an intuitive, modular way. When you shift nonzero bits
out of a signed, negative value variable, to the left, it might easily
turn positive, in a completely screwed up way.

Imagine that you have five cells on paper, in real life, decimal:

+---+---+---+---+---+
| - | 3 | 0 | 9 | 0 |
+---+---+---+---+---+

you multiply it by ten ("just append a zero"), and you end up with

+---+---+---+---+---+
| 3 | 0 | 9 | 0 | 0 |
+---+---+---+---+---+

It changed sign because you ran out of cells. Now does that make any sense?

In any such case, in real life you have sign and magnitude, and the
shifting doesn't effect the sign at all!

    +---+---+---+---+
  - | 3 | 0 | 9 | 0 |
    +---+---+---+---+

You might run out of magnitude, but that's a *completely* different,
controlled and intuitive phenomenon.

... Paolo wrote

    -(a << b) works but does not express that the intention is to
    compute -a * 2^N, especially if "a" is a constant

So apparently that's where I disagree.

To me, the << operator doesn't communicate "multiply by 2^N"; it
massages the bit pattern instead. For unsigned values, said massaging
implies the multiplication *intuitively*. ("Append a zero", remember?)
It remains intuitive even if the result gets truncated.

For signed / negative values, the shifting only *happens* to imply the
multiplication, and only because of two's complement. If you shift the
negative value out of range, you're busto (the sign might change). And
even if you stay within range, two's complement is a non-intuitive, ugly
hack. It has useful properties, yes, but it's hard to reason about safely.

The problem with two's complement is not that "there could be other
representations". (No, there aren't other representations; not today.)
The problem with two's complement is that it is a mathematical construct
that is hard to reason about, despite its intentionally useful properties.

Nevermind, anyway.

Thanks
Laszlo

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

On 17/11/2015 17:54, Laszlo Ersek wrote:
> I'm not worried. I hate it for the mental load it represents.
> 
> For me, the fact that the negative sign is encoded (with *any* kind of
> representation) within the bit pattern subject to shifting, makes the
> negative sign *inherently* incompatible with shifting.
> 
> In real life, *you don't shift a sign*. It just makes no sense. The sign
> is not a digit. You can append or cut off zeroes from the right, but the
> sign is not subject to that. The sign doesn't care.

I agree.  That's why I said elsewhere that it's *okay* for me if e.g.
0xC0000000u << 2 is undefined behavior.  In fact, it's mostly okay for
me if shift _into_ the sign bit were undefined behavior.

Basically, I avoid the "mental load" with a rule that left shift is just
multiplication by 2^N.

Paolo

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Paolo Bonzini <pbonzini@redhat.com> writes:

> It seems like there's no good reason for the compiler to exploit the
> undefinedness of left shifts.  GCC explicitly documents that they do not
> use at all this possibility and, while they also say this is subject
> to change, they have been saying this for 10 years (since the wording
> appeared in the GCC 4.0 manual).
>
> Any workaround for this particular case of undefined behavior uglifies the
> code.  Using unsigned is unsafe (https://github.com/madler/zlib/pull/112
> is the proof) because the value becomes positive when extended; -(a << b)
> works but does not express that the intention is to compute -a * 2^N,
> especially if "a" is a constant.
>
> <rant>
> The straw that broke the camel back is Clang's latest obnoxious,
> pointless, unsafe---and did I mention *totally* useless---warning about
> left shifting a negative integer.  It's obnoxious and pointless because
> the compiler is not using the latitude that the standard gives it, so
> the warning just adds noise.  It is useless and unsafe because it does
> not catch the widely more common case where the LHS is a variable, and
> thus gives a false sense of security.  The noisy nature of the warning
> means that it should have never been added to -Wall.  The uselessness
> means that it probably should not have even been added to -Wextra.
>
> (It would have made sense to enable the warning for -fsanitize=shift,
> as the program would always crash if the point is reached.  But this was
> probably too sophisticated to come up with, when you're so busy giving
> birth to gems such as -Wabsolute-value).
> </rant>
>
> Ubsan also has warnings for undefined behavior of left shifts.  Checks for
> left shift overflow and left shift of negative numbers, unfortunately,
> cannot be silenced without also silencing the useful ones about out-of-range
> shift amounts. -fwrapv ought to shut them up, but doesn't yet
> (https://llvm.org/bugs/show_bug.cgi?id=25552; I am taking care of fixing
> the same issues in GCC).  Luckily ubsan is optional, and the easy
> workaround is to use -fsanitize-recover.
>
> Anyhow, this patch documents our assumptions explicitly, and shuts up the
> stupid warning.  -fwrapv is a bit of a heavy hammer, but it is the safest
> option and it ought to just work long term as the compilers improve.

The kernel switched from -fwrapv to -fno-strict-overflow in '09, because
-fwrapv was buggy in gcc 4.1 (already old then, completely irrelevant
now), and because it "seems to be much less disturbing to gcc too: the
difference in the generated code by -fno-strict-overflow are smaller
(compared to using neither flag) than when using -fwrapv", which may or
may not be still the case with compilers that matter today.

Could you briefly explain why you picked -fwrapv and not
-fno-strict-overflow?

> Thanks to everyone involved in the discussion!
>
> Cc: Peter Maydell <peter.maydell@linaro.org>
> Cc: Markus Armbruster <armbru@redhat.com>
> Cc: Laszlo Ersek <lersek@redhat.com>
> Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

On 17/11/2015 18:39, Markus Armbruster wrote:
> The kernel switched from -fwrapv to -fno-strict-overflow in '09, because
> -fwrapv was buggy in gcc 4.1 (already old then, completely irrelevant
> now), and because it "seems to be much less disturbing to gcc too: the
> difference in the generated code by -fno-strict-overflow are smaller
> (compared to using neither flag) than when using -fwrapv", which may or
> may not be still the case with compilers that matter today.
> 
> Could you briefly explain why you picked -fwrapv and not
> -fno-strict-overflow?

Because -fno-strict-overflow doesn't silence ubsan, only -fwrapv does
(it doesn't silence it for negative left shifts, but I've asked on
gcc-patches whether they'd like to have that fixed as well).

In the meanwhile I got some good news from the GCC folks:

>> I think we should remove the ", but this is subject to change" in 
>> implement-c.texi (while replacing it with noting that ubsan will still 
>> diagnose such cases, and they will also be diagnosed where constant 
>> expressions are required).

Paolo

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Peter Maydell]

On 17 November 2015 at 17:45, Paolo Bonzini <pbonzini@redhat.com> wrote:
> In the meanwhile I got some good news from the GCC folks:
>
>>> I think we should remove the ", but this is subject to change" in
>>> implement-c.texi (while replacing it with noting that ubsan will still
>>> diagnose such cases, and they will also be diagnosed where constant
>>> expressions are required).

That doesn't seem like more than half-good news to me. In particular,
if ubsan is still diagnosing these cases and they're still a
problem in some constant expressions then it is not true
that -fwrapv means "shifts of negative numbers etc are well
defined and valid in this dialect of C".

If the GCC folks don't want to go any further than that then
I think we should prefer to avoid this UB. (And there's still
the question of clang's position on this.)

thanks
-- PMM

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

On 17/11/2015 19:19, Peter Maydell wrote:
> That doesn't seem like more than half-good news to me. In particular,
> if ubsan is still diagnosing these cases and they're still a
> problem in some constant expressions

Constant expressions are standardese for e.g.

static int x = 1 << 31;

It doesn't mean _all_ constants, and the warning only triggers with
-pedantic.

Regarding ubsan, give them some time to answer. :)

Paolo

> If the GCC folks don't want to go any further than that then
> I think we should prefer to avoid this UB. (And there's still
> the question of clang's position on this.)

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Laszlo Ersek <lersek@redhat.com> writes:

> On 11/17/15 16:47, Markus Armbruster wrote:
>> Laszlo Ersek <lersek@redhat.com> writes:
>> 
>>> I accept this is a defensible, maybe even reasonable choice to make in
>>> the QEMU project. On the other hand, I personally cannot stop hating
>>> shifting negative values (any direction) -- indeed, the *original* code
>>> from <https://github.com/madler/zlib/pull/112> makes me barf too.
>>>
>>> Therefore,
>>>
>>> Grudgingly-reviewed-by: Laszlo Ersek <lersek@redhat.com>
>>>
>>> (I realize the flag for the pointer wraparound has been separated; this
>>> is strictly about shifts.)
>> 
>> What's so abhorrent about shifting negative values?  I know machines
>> with signed integer representations other than twos complement exist, as
>> do machines that can't do both logical and arithmetic shifts.  Mostly
>> inside computer museums, though.
>> 
>> C was standardized at a time when keeping the language sufficiently
>> loose to permit efficient implementation on these oddball machines made
>> a lot more sense than it does now.  Making it undefined behavior went
>> too far, though.  Implementation-defined or unspecified behavior would
>> have sufficed.
>> 
>> Learn to stop worrying and love the signed shifts :)
>
> I'm not worried. I hate it for the mental load it represents.
>
> For me, the fact that the negative sign is encoded (with *any* kind of
> representation) within the bit pattern subject to shifting, makes the
> negative sign *inherently* incompatible with shifting.
>
> In real life, *you don't shift a sign*. It just makes no sense. The sign
> is not a digit. You can append or cut off zeroes from the right, but the
> sign is not subject to that. The sign doesn't care.
>
> When you shift nonzero bits out of an unsigned variable to the left, its
> value changes in an intuitive, modular way. When you shift nonzero bits
> out of a signed, negative value variable, to the left, it might easily
> turn positive, in a completely screwed up way.
>
> Imagine that you have five cells on paper, in real life, decimal:
>
> +---+---+---+---+---+
> | - | 3 | 0 | 9 | 0 |
> +---+---+---+---+---+
>
> you multiply it by ten ("just append a zero"), and you end up with
>
> +---+---+---+---+---+
> | 3 | 0 | 9 | 0 | 0 |
> +---+---+---+---+---+
>
> It changed sign because you ran out of cells. Now does that make any sense?
>
> In any such case, in real life you have sign and magnitude, and the
> shifting doesn't effect the sign at all!
>
>     +---+---+---+---+
>   - | 3 | 0 | 9 | 0 |
>     +---+---+---+---+
>
> You might run out of magnitude, but that's a *completely* different,
> controlled and intuitive phenomenon.
>
> ... Paolo wrote
>
>     -(a << b) works but does not express that the intention is to
>     compute -a * 2^N, especially if "a" is a constant
>
> So apparently that's where I disagree.
>
> To me, the << operator doesn't communicate "multiply by 2^N"; it
> massages the bit pattern instead. For unsigned values, said massaging
> implies the multiplication *intuitively*. ("Append a zero", remember?)
> It remains intuitive even if the result gets truncated.

Yes, operator << is an operation on bits.

Yes, when you use it to multiply a two's complement integer by a power
of two *and* this changes the sign, you suffer integer overflow.

But integer overflow isn't specific to bad, bad <<.  Pretty much all
operations on two's complement numbers can overflow.  When a << n
overflows (0 <= n < width of the shift - 1), then inhowfar would a * 2^n
fare any better?

If it wouldn't, then why is a << n worth a warning (but only when a is a
compile-time negative constant), but a * b isn't?

Perhaps we should all program in languages where integer overflow is a
hard error, or can't happen (bignums to the rescue).  However, we
aren't.

Instead, we're using an "improvement" over mere shifting of bits!
Instead of "signed left shift gives you the bits you asked for, but
probably not the integer you asked for (assuming you asked for one)",
we're using "may give you whatever bits it likes, or crash, or even put
milk in your tea".  I'm sure it sounded like a good idea at the time.

> For signed / negative values, the shifting only *happens* to imply the
> multiplication, and only because of two's complement. If you shift the
> negative value out of range, you're busto (the sign might change). And
> even if you stay within range, two's complement is a non-intuitive, ugly
> hack. It has useful properties, yes, but it's hard to reason about safely.

Well, with sign-magnitude / sign in the MSB, a left shift *also* is a
multiplication by a power of two.  It just overflows more easily.

> The problem with two's complement is not that "there could be other
> representations". (No, there aren't other representations; not today.)
> The problem with two's complement is that it is a mathematical construct
> that is hard to reason about, despite its intentionally useful properties.
>
> Nevermind, anyway

Yes, integer overflow is a pain.  No, it's not two's complement's fault,
it's using-a-finite-number-of-bits-to-represent-the-infinite-set-of-
integers' fault.

Learn to stop worrying and love the two's complement ;)

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Paolo Bonzini <pbonzini@redhat.com> writes:

> On 17/11/2015 18:39, Markus Armbruster wrote:
>> The kernel switched from -fwrapv to -fno-strict-overflow in '09, because
>> -fwrapv was buggy in gcc 4.1 (already old then, completely irrelevant
>> now), and because it "seems to be much less disturbing to gcc too: the
>> difference in the generated code by -fno-strict-overflow are smaller
>> (compared to using neither flag) than when using -fwrapv", which may or
>> may not be still the case with compilers that matter today.
>> 
>> Could you briefly explain why you picked -fwrapv and not
>> -fno-strict-overflow?
>
> Because -fno-strict-overflow doesn't silence ubsan, only -fwrapv does
> (it doesn't silence it for negative left shifts, but I've asked on
> gcc-patches whether they'd like to have that fixed as well).

Add something like that to the commit message, and you have my
Reviewed-by: Markus Armbruster <armbru@redhat.com>

> In the meanwhile I got some good news from the GCC folks:
>
>>> I think we should remove the ", but this is subject to change" in 
>>> implement-c.texi (while replacing it with noting that ubsan will still 
>>> diagnose such cases, and they will also be diagnosed where constant 
>>> expressions are required).

Makes only sense.

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Peter Maydell]

On 17 November 2015 at 18:21, Paolo Bonzini <pbonzini@redhat.com> wrote:
>
>
> On 17/11/2015 19:19, Peter Maydell wrote:
>> That doesn't seem like more than half-good news to me. In particular,
>> if ubsan is still diagnosing these cases and they're still a
>> problem in some constant expressions
>
> Constant expressions are standardese for e.g.
>
> static int x = 1 << 31;
>
> It doesn't mean _all_ constants, and the warning only triggers with
> -pedantic.

But if "-fwrapv" means "this dialect of C makes shifts of
negative numbers well defined and OK" then "-1 << 31"
should be fine and should not provoke a warning (whether in
a constant expression or not). If that's not what -fwrapv means,
then we shouldn't be using it as if it did.

thanks
-- PMM

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

On 17/11/2015 19:24, Peter Maydell wrote:
> On 17 November 2015 at 18:21, Paolo Bonzini <pbonzini@redhat.com> wrote:
>>
>>
>> On 17/11/2015 19:19, Peter Maydell wrote:
>>> That doesn't seem like more than half-good news to me. In particular,
>>> if ubsan is still diagnosing these cases and they're still a
>>> problem in some constant expressions
>>
>> Constant expressions are standardese for e.g.
>>
>> static int x = 1 << 31;
>>
>> It doesn't mean _all_ constants, and the warning only triggers with
>> -pedantic.
> 
> But if "-fwrapv" means "this dialect of C makes shifts of
> negative numbers well defined and OK" then "-1 << 31"
> should be fine and should not provoke a warning (whether in
> a constant expression or not). If that's not what -fwrapv means,
> then we shouldn't be using it as if it did.

Since we don't use -pedantic, we don't care.  But I agree that it could
be the subject of a separate fix.  For now I'll focus on ubsan since
that's the more important one.

Paolo

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Peter Maydell]

On 17 November 2015 at 18:36, Paolo Bonzini <pbonzini@redhat.com> wrote:
> On 17/11/2015 19:24, Peter Maydell wrote:
>> But if "-fwrapv" means "this dialect of C makes shifts of
>> negative numbers well defined and OK" then "-1 << 31"
>> should be fine and should not provoke a warning (whether in
>> a constant expression or not). If that's not what -fwrapv means,
>> then we shouldn't be using it as if it did.
>
> Since we don't use -pedantic, we don't care.

We need to care because the interesting question is "what is
GCC guaranteeing to us", not "how can we shut the compiler up".
If -fwrapv doesn't silence these warnings that means there's
a disconnect between what we think the guarantees are and what
the gcc devs think the guarantees are, which is liable to
cause trouble in the future.

thanks
-- PMM

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Markus Armbruster]

Peter Maydell <peter.maydell@linaro.org> writes:

> On 17 November 2015 at 18:21, Paolo Bonzini <pbonzini@redhat.com> wrote:
>>
>>
>> On 17/11/2015 19:19, Peter Maydell wrote:
>>> That doesn't seem like more than half-good news to me. In particular,
>>> if ubsan is still diagnosing these cases and they're still a
>>> problem in some constant expressions
>>
>> Constant expressions are standardese for e.g.
>>
>> static int x = 1 << 31;
>>
>> It doesn't mean _all_ constants, and the warning only triggers with
>> -pedantic.
>
> But if "-fwrapv" means "this dialect of C makes shifts of
> negative numbers well defined and OK" then "-1 << 31"
> should be fine and should not provoke a warning (whether in
> a constant expression or not). If that's not what -fwrapv means,
> then we shouldn't be using it as if it did.

A warning doesn't necessarily mean "this isn't well-defined".  It could
also mean "this might not be portable", or "we think your code is ugly".
Inferring semantics from warnings is shaky business.  Instead, let's ask
the maintainers of gcc to clarify the meaning of -fwrapv.

Re: [Qemu-devel] [PATCH v2 for 2.5] QEMU does not care about left shifts of signed negative values

[Paolo Bonzini]

On 17/11/2015 19:41, Markus Armbruster wrote:
> Peter Maydell <peter.maydell@linaro.org> writes:
> 
>> On 17 November 2015 at 18:21, Paolo Bonzini <pbonzini@redhat.com> wrote:
>>>
>>>
>>> On 17/11/2015 19:19, Peter Maydell wrote:
>>>> That doesn't seem like more than half-good news to me. In particular,
>>>> if ubsan is still diagnosing these cases and they're still a
>>>> problem in some constant expressions
>>>
>>> Constant expressions are standardese for e.g.
>>>
>>> static int x = 1 << 31;
>>>
>>> It doesn't mean _all_ constants, and the warning only triggers with
>>> -pedantic.
>>
>> But if "-fwrapv" means "this dialect of C makes shifts of
>> negative numbers well defined and OK" then "-1 << 31"
>> should be fine and should not provoke a warning (whether in
>> a constant expression or not). If that's not what -fwrapv means,
>> then we shouldn't be using it as if it did.
> 
> A warning doesn't necessarily mean "this isn't well-defined".  It could
> also mean "this might not be portable", or "we think your code is ugly".
> Inferring semantics from warnings is shaky business.  Instead, let's ask
> the maintainers of gcc to clarify the meaning of -fwrapv.

But again, we're not getting any warning in the first place.

Paolo