[Qemu-devel] [PATCH 0/3] More fixes for undefined behaviour

[Qemu-devel] [PATCH 0/3] More fixes for undefined behaviour

[Peter Maydell]

These three patches provide more fixes for undefined behaviour
spotted by the clang sanitizer when doing "make check" runs.
I don't think these need to go into 2.0; I'm just sending them
out now so I don't forget about them...

Peter Maydell (3):
  hw/ide/ahci.c: Avoid shift left into sign bit
  int128.h: Avoid undefined behaviours involving signed arithmetic
  xbzrle.c: Avoid undefined behaviour with signed arithmetic

 hw/ide/ahci.c         | 4 ++--
 include/qemu/int128.h | 4 ++--
 xbzrle.c              | 8 +++++---
 3 files changed, 9 insertions(+), 7 deletions(-)

-- 
1.9.0

[Qemu-devel] [PATCH 1/3] hw/ide/ahci.c: Avoid shift left into sign bit

[Peter Maydell]

Add U suffix to avoid shifting left into the sign bit, which
is undefined behaviour.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 hw/ide/ahci.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/hw/ide/ahci.c b/hw/ide/ahci.c
index bfe633f..50327ff 100644
--- a/hw/ide/ahci.c
+++ b/hw/ide/ahci.c
@@ -438,9 +438,9 @@ static void check_cmd(AHCIState *s, int port)
 
     if ((pr->cmd & PORT_CMD_START) && pr->cmd_issue) {
         for (slot = 0; (slot < 32) && pr->cmd_issue; slot++) {
-            if ((pr->cmd_issue & (1 << slot)) &&
+            if ((pr->cmd_issue & (1U << slot)) &&
                 !handle_cmd(s, port, slot)) {
-                pr->cmd_issue &= ~(1 << slot);
+                pr->cmd_issue &= ~(1U << slot);
             }
         }
     }
-- 
1.9.0

Re: [Qemu-devel] [Qemu-trivial] [PATCH 1/3] hw/ide/ahci.c: Avoid shift left into sign bit

[Michael Tokarev]

28.03.2014 19:12, Peter Maydell wrote:
> Add U suffix to avoid shifting left into the sign bit, which
> is undefined behaviour.

Applied to -trivial, thanks!

/mjt

[Qemu-devel] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

Add casts when we're performing arithmetic on the .hi parts of an
Int128, to avoid undefined behaviour.

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 include/qemu/int128.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/qemu/int128.h b/include/qemu/int128.h
index 9ed47aa..f597031 100644
--- a/include/qemu/int128.h
+++ b/include/qemu/int128.h
@@ -53,7 +53,7 @@ static inline Int128 int128_rshift(Int128 a, int n)
     if (n >= 64) {
         return (Int128) { h, h >> 63 };
     } else {
-        return (Int128) { (a.lo >> n) | (a.hi << (64 - n)), h };
+        return (Int128) { (a.lo >> n) | ((uint64_t)a.hi << (64 - n)), h };
     }
 }
 
@@ -78,7 +78,7 @@ static inline Int128 int128_neg(Int128 a)
 
 static inline Int128 int128_sub(Int128 a, Int128 b)
 {
-    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
+    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };
 }
 
 static inline bool int128_nonneg(Int128 a)
-- 
1.9.0

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Michael Tokarev]

28.03.2014 19:12, Peter Maydell wrote:
> Add casts when we're performing arithmetic on the .hi parts of an
> Int128, to avoid undefined behaviour.
[]
>  static inline Int128 int128_sub(Int128 a, Int128 b)
>  {
> -    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
> +    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };

What was wrong with this one?  I don't think casting to unsigned here is
a good idea.

Thanks,

/mjt

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

On 6 April 2014 08:09, Michael Tokarev <mjt@tls.msk.ru> wrote:
> 28.03.2014 19:12, Peter Maydell wrote:
>> Add casts when we're performing arithmetic on the .hi parts of an
>> Int128, to avoid undefined behaviour.
> []
>>  static inline Int128 int128_sub(Int128 a, Int128 b)
>>  {
>> -    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
>> +    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };
>
> What was wrong with this one?  I don't think casting to unsigned here is
> a good idea.

This patch is fixing these three clang sanitizer warnings:
/home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:40:
runtime error: signed integer overflow: 0 - -9223372036854775808
cannot be represented in type 'long'
/home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:47:
runtime error: signed integer overflow: -9223372036854775808 - 1
cannot be represented in type 'long'
/home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:56:47:
runtime error: left shift of negative value -9223372036854775807

of which the first two are in this function.

Note that int128_add() already has a cast.

The alternative would be to say that Int128 should have
undefined behaviour on underflow/overflow and the test
code is wrong, but that doesn't seem very useful to me.

thanks
-- PMM

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Michael Tokarev]

06.04.2014 14:18, Peter Maydell wrote:
> On 6 April 2014 08:09, Michael Tokarev <mjt@tls.msk.ru> wrote:
>> 28.03.2014 19:12, Peter Maydell wrote:
>>> Add casts when we're performing arithmetic on the .hi parts of an
>>> Int128, to avoid undefined behaviour.
>> []
>>>  static inline Int128 int128_sub(Int128 a, Int128 b)
>>>  {
>>> -    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
>>> +    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };
>>
>> What was wrong with this one?  I don't think casting to unsigned here is
>> a good idea.
> 
> This patch is fixing these three clang sanitizer warnings:
> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:40:
> runtime error: signed integer overflow: 0 - -9223372036854775808
> cannot be represented in type 'long'

Int128 is defined as { uint64_t lo, int64_t hi }, so the second half is
signed (because Int128 should be able to represent negative numbers too).

-9223372036854775808 is 0x8000000000000000 -- which is only sign bit = 1.

uint64_t - int64_t is already somewhat undefined - should the second
int be treated as unsigned too? (I'm sorry I don't really remember the
C specs in there).

But more to the point - the new behavour, while "defined", is just as
arbitrary as the old "undefined" behavour.  On overflow we can get either
truncated or negative result, neither of which is right.

> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:47:
> runtime error: signed integer overflow: -9223372036854775808 - 1
> cannot be represented in type 'long'
> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:56:47:
> runtime error: left shift of negative value -9223372036854775807
> 
> of which the first two are in this function.
> 
> Note that int128_add() already has a cast.
> 
> The alternative would be to say that Int128 should have
> undefined behaviour on underflow/overflow and the test
> code is wrong, but that doesn't seem very useful to me.

It is still arbitrary.

But whole thing looks more like an attempt to shut up a bogus compiler warning
really.  It is not correct either way because there's just no correct way,
because the end behavour is undefined in hardware, and we _are_ emulating
hardware here.

Yes, int128_add() has a cast already, and it is just as arbitrary as this one.

So.. maybe for consistency with _add(), maybe to shut up useless warning, maybe
to have something to base units-tests on (arbitrary but defined), this can be
applied... I think :)

So, applied to -trivial ;)

Thanks,

/mjt

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

On 6 April 2014 15:13, Michael Tokarev <mjt@tls.msk.ru> wrote:
> 06.04.2014 14:18, Peter Maydell wrote:
>> On 6 April 2014 08:09, Michael Tokarev <mjt@tls.msk.ru> wrote:
>>> 28.03.2014 19:12, Peter Maydell wrote:
>>>> Add casts when we're performing arithmetic on the .hi parts of an
>>>> Int128, to avoid undefined behaviour.
>>> []
>>>>  static inline Int128 int128_sub(Int128 a, Int128 b)
>>>>  {
>>>> -    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
>>>> +    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };
>>>
>>> What was wrong with this one?  I don't think casting to unsigned here is
>>> a good idea.
>>
>> This patch is fixing these three clang sanitizer warnings:
>> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:40:
>> runtime error: signed integer overflow: 0 - -9223372036854775808
>> cannot be represented in type 'long'
>
> Int128 is defined as { uint64_t lo, int64_t hi }, so the second half is
> signed (because Int128 should be able to represent negative numbers too).
>
> -9223372036854775808 is 0x8000000000000000 -- which is only sign bit = 1.

Yes, and 0 - this in signed arithmetic is undefined behaviour, which
is why clang is complaining.

> uint64_t - int64_t is already somewhat undefined - should the second
> int be treated as unsigned too? (I'm sorry I don't really remember the
> C specs in there).

This is well defined -- see C99 6.3.1.8 "Usual arithmetic conversions":
the int64_t value is converted to uint64_t and the operation is performed
using unsigned arithmetic (and the result of converting any int64_t to
a uint64_t is a well defined value).

> But more to the point - the new behavour, while "defined", is just as
> arbitrary as the old "undefined" behavour.  On overflow we can get either
> truncated or negative result, neither of which is right.

Currently on overflow we are giving undefined behavour -- that
means the compiler is allowed to return 42, make QEMU segfault,
delete all the user's files, or anything else it feels like. It does not
simply mean "result is unknown" or "result is what you might expect
on a 2s complement arithmetic CPU".

The obvious semantics here are to treat Int128 as a 2s complement
value. This is particularly useful since there is no UInt128, since it
means you can actually treat it as an unsigned 128 bit integer if
you want to (though you wouldn't be able to use the comparison ops,
obviously).

>> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:47:
>> runtime error: signed integer overflow: -9223372036854775808 - 1
>> cannot be represented in type 'long'
>> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:56:47:
>> runtime error: left shift of negative value -9223372036854775807
>>
>> of which the first two are in this function.
>>
>> Note that int128_add() already has a cast.
>>
>> The alternative would be to say that Int128 should have
>> undefined behaviour on underflow/overflow and the test
>> code is wrong, but that doesn't seem very useful to me.
>
> It is still arbitrary.
>
> But whole thing looks more like an attempt to shut up a bogus compiler warning
> really.  It is not correct either way because there's just no correct way,
> because the end behavour is undefined in hardware, and we _are_ emulating
> hardware here.

This seems to be where we differ. This is not a bogus warning:
we're doing undefined behaviour, so either:
 (a) the test code is wrong
 (b) our implementation is wrong

"Leave it alone" is about the only thing that's definitely wrong.

> Yes, int128_add() has a cast already, and it is just as arbitrary as this one.

No, it also is avoiding undefined behaviour.

thanks
-- PMM

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

On 6 April 2014 15:13, Michael Tokarev <mjt@tls.msk.ru> wrote:
> It is not correct either way because there's just no correct way,
> because the end behavour is undefined in hardware, and we _are_ emulating
> hardware here.

Incidentally, I'd disagree with that statement on two grounds:
 * in hardware, integer overflow is well defined (at least for all
   the things we emulate) -- the 99% case is "it's 2s complement"
    and we might have a few cases of "exception on overflow",
    as with x86 MININT/-1 and IIRC SPARC or MIPS have
   some "exception on overflow" add/subtract insns. I don't
   know of any h/w daft enough to make signed integer arithmetic
   actually undefined-behaviour.
 * in QEMU we're not actually using Int128 in QEMU for h/w
   emulation -- we just use it for doing address arithmetic in the
   memory subsystem so we don't run into problems with
   overflow and insufficient range in 64 bit integer types.

In any case we can freely define the semantics of this type
in any way we find convenient for ourselves. I think it's much
easier to reason about things if you don't have to deal with
undefined-behaviour cases (if C compilers had a "behave
like a sane 2s complement system for signed arithmetic"
option I'd be advocating for us using it...)

thanks
-- PMM

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Richard Henderson]

On 04/06/2014 08:27 AM, Peter Maydell wrote:
> (if C compilers had a "behave
> like a sane 2s complement system for signed arithmetic"
> option I'd be advocating for us using it...)

-fwrapv.


r~

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

On 7 April 2014 15:25, Richard Henderson <rth@twiddle.net> wrote:
> On 04/06/2014 08:27 AM, Peter Maydell wrote:
>> (if C compilers had a "behave
>> like a sane 2s complement system for signed arithmetic"
>> option I'd be advocating for us using it...)
>
> -fwrapv.

Well, we should use that then :-)

thanks
-- PMM

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Markus Armbruster]

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

> On 7 April 2014 15:25, Richard Henderson <rth@twiddle.net> wrote:
>> On 04/06/2014 08:27 AM, Peter Maydell wrote:
>>> (if C compilers had a "behave
>>> like a sane 2s complement system for signed arithmetic"
>>> option I'd be advocating for us using it...)
>>
>> -fwrapv.
>
> Well, we should use that then :-)

I share your distaste for compilers being perfectly capable to recognize
undefined behavior so they can "optimize" working programs into slightly
faster broken programs, yet unable to warn me about the very same
undefined behavior they so eagerly exploit.

-fwrapv is known to be buggy in gcc 4.1.  Do we care?

It bit the kernel a couple of years ago, and they replaced -fwrapv by
-fno-strict-overflow.

Commit introducing -fwrapv:
https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=68df3755e383e6fecf2354a67b08f92f18536594

Commit moving to -fno-strict-overflow:
https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=a137802ee839ace40079bebde24cfb416f73208a

Blog post comparing the two options:
http://www.airs.com/blog/archives/120

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Avi Kivity]

On 04/06/2014 01:18 PM, Peter Maydell wrote:
> On 6 April 2014 08:09, Michael Tokarev <mjt@tls.msk.ru> wrote:
>> 28.03.2014 19:12, Peter Maydell wrote:
>>> Add casts when we're performing arithmetic on the .hi parts of an
>>> Int128, to avoid undefined behaviour.
>> []
>>>   static inline Int128 int128_sub(Int128 a, Int128 b)
>>>   {
>>> -    return (Int128){ a.lo - b.lo, a.hi - b.hi - (a.lo < b.lo) };
>>> +    return (Int128){ a.lo - b.lo, (uint64_t)a.hi - b.hi - (a.lo < b.lo) };
>> What was wrong with this one?  I don't think casting to unsigned here is
>> a good idea.
> This patch is fixing these three clang sanitizer warnings:
> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:40:
> runtime error: signed integer overflow: 0 - -9223372036854775808
> cannot be represented in type 'long'
> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:81:47:
> runtime error: signed integer overflow: -9223372036854775808 - 1
> cannot be represented in type 'long'
> /home/petmay01/linaro/qemu-from-laptop/qemu/include/qemu/int128.h:56:47:
> runtime error: left shift of negative value -9223372036854775807
>
> of which the first two are in this function.
>
> Note that int128_add() already has a cast.
>
> The alternative would be to say that Int128 should have
> undefined behaviour on underflow/overflow and the test
> code is wrong, but that doesn't seem very useful to me.
>
>

Isn't the test broken here?  It is trying to add (or shift) -2^127 and 
something else, and the result truly overflows.

A better behaviour would be to abort when this happens.  Int128 was 
designed to avoid silent overflows, not to silently cause breakage.

Not that I think it is necessary, there is no way for the guest to 
trigger an overflow.

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Peter Maydell]

On 7 April 2014 15:56, Avi Kivity <avi@cloudius-systems.com> wrote:
> On 04/06/2014 01:18 PM, Peter Maydell wrote:
>> The alternative would be to say that Int128 should have
>> undefined behaviour on underflow/overflow and the test
>> code is wrong, but that doesn't seem very useful to me.

> Isn't the test broken here?  It is trying to add (or shift) -2^127 and
> something else, and the result truly overflows.

Well, the test code is assuming "semantics as per 2s
complement arithmetic" and checking various corner cases.
As I say, we could define that this is invalid and
rewrite the test cases.

thanks
-- PMM

Re: [Qemu-devel] [Qemu-trivial] [PATCH 2/3] int128.h: Avoid undefined behaviours involving signed arithmetic

[Avi Kivity]

On 04/07/2014 06:17 PM, Peter Maydell wrote:
> On 7 April 2014 15:56, Avi Kivity <avi@cloudius-systems.com> wrote:
>> On 04/06/2014 01:18 PM, Peter Maydell wrote:
>>> The alternative would be to say that Int128 should have
>>> undefined behaviour on underflow/overflow and the test
>>> code is wrong, but that doesn't seem very useful to me.
>> Isn't the test broken here?  It is trying to add (or shift) -2^127 and
>> something else, and the result truly overflows.
> Well, the test code is assuming "semantics as per 2s
> complement arithmetic" and checking various corner cases.
> As I say, we could define that this is invalid and
> rewrite the test cases.

It is invalid.  The test thinks that -2^127 * 2 == 0, but if a guest 
could trigger it, it would probably be a security issue.

[Qemu-devel] [PATCH 3/3] xbzrle.c: Avoid undefined behaviour with signed arithmetic

[Peter Maydell]

Use unsigned types for doing bitwise arithmetic in the xzbrle
calculations, to avoid undefined behaviour:

 xbzrle.c:99:49: runtime error: left shift of 72340172838076673
 by 7 places cannot be represented in type 'long'

Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
---
 xbzrle.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/xbzrle.c b/xbzrle.c
index fbcb35d..8e220bf 100644
--- a/xbzrle.c
+++ b/xbzrle.c
@@ -28,7 +28,7 @@ int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
 {
     uint32_t zrun_len = 0, nzrun_len = 0;
     int d = 0, i = 0;
-    long res, xor;
+    long res;
     uint8_t *nzrun_start = NULL;
 
     g_assert(!(((uintptr_t)old_buf | (uintptr_t)new_buf | slen) %
@@ -93,9 +93,11 @@ int xbzrle_encode_buffer(uint8_t *old_buf, uint8_t *new_buf, int slen,
         /* word at a time for speed, use of 32-bit long okay */
         if (!res) {
             /* truncation to 32-bit long okay */
-            long mask = (long)0x0101010101010101ULL;
+            unsigned long mask = (unsigned long)0x0101010101010101ULL;
             while (i < slen) {
-                xor = *(long *)(old_buf + i) ^ *(long *)(new_buf + i);
+                unsigned long xor;
+                xor = *(unsigned long *)(old_buf + i)
+                    ^ *(unsigned long *)(new_buf + i);
                 if ((xor - mask) & ~xor & (mask << 7)) {
                     /* found the end of an nzrun within the current long */
                     while (old_buf[i] != new_buf[i]) {
-- 
1.9.0

Re: [Qemu-devel] [Qemu-trivial] [PATCH 3/3] xbzrle.c: Avoid undefined behaviour with signed arithmetic

[Michael Tokarev]

28.03.2014 19:12, Peter Maydell wrote:
> Use unsigned types for doing bitwise arithmetic in the xzbrle
> calculations, to avoid undefined behaviour:
> 
>  xbzrle.c:99:49: runtime error: left shift of 72340172838076673
>  by 7 places cannot be represented in type 'long'

Aplied to -trivial, thanks!

/mjt