Re: [Qemu-devel] [PATCH for-2.5] hw/timer/hpet.c: Avoid signed integer overflow which results in bugs on OSX

[Laszlo Ersek <lersek@redhat.com>]

On 11/09/15 23:25, Laszlo Ersek wrote:
> On 11/09/15 15:56, Peter Maydell wrote:
>> Signed integer overflow in C is undefined behaviour, and the compiler
>> is at liberty to assume it can never happen and optimize accordingly.
>> In particular, the subtractions in hpet_time_after() and hpet_time_after64()
>> were causing OSX clang to optimize the code such that it was prone to
>> hangs and complaints about the main loop stalling (presumably because
>> we were spending all our time trying to service very high frequency
>> HPET timer callbacks). The clang sanitizer confirms the UB:
>>
>> hw/timer/hpet.c:119:26: runtime error: signed integer overflow: -2146967296 - 2147003978 cannot be represented in type 'int'
>>
>> Fix this by doing the subtraction as an unsigned operation and then
>> converting to signed for the comparison.
>>
>> Reported-by: Aaron Elkins <threcius@yahoo.com>
>> Signed-off-by: Peter Maydell <peter.maydell@linaro.org>
>> ---
>>  hw/timer/hpet.c | 4 ++--
>>  1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/hw/timer/hpet.c b/hw/timer/hpet.c
>> index 3037bef..7f0391c 100644
>> --- a/hw/timer/hpet.c
>> +++ b/hw/timer/hpet.c
>> @@ -116,12 +116,12 @@ static uint32_t timer_enabled(HPETTimer *t)
>>  
>>  static uint32_t hpet_time_after(uint64_t a, uint64_t b)
>>  {
>> -    return ((int32_t)(b) - (int32_t)(a) < 0);
>> +    return ((int32_t)(b - a) < 0);
>>  }
>>  
>>  static uint32_t hpet_time_after64(uint64_t a, uint64_t b)
>>  {
>> -    return ((int64_t)(b) - (int64_t)(a) < 0);
>> +    return ((int64_t)(b - a) < 0);
>>  }
>>  
>>  static uint64_t ticks_to_ns(uint64_t value)
>>
> 
> I'm late to the discussion, but I cannot imagine what would speak against:
> 
>     return (b < a);
> 
> The post-patch code still converts a uint64_t difference to int32_t.
> According to the C standard(s), such a conversion (i.e., when the
> integer value being converted doesn't fit in the target signed integer)
> results in an implementation-defined value, or an implementation-defined
> signal is raised.
> 
> On our platforms, the impl-def value is determined by "truncate to 32
> bits, then reinterpret the bit pattern as two's complement signed
> int32_t". Meaning, if:
> 
>     (b > a) && ((b - a) & (1u << 31))
> 
> (that is, "b" is so much larger than "a" that bit#31 is set in the (b-a)
> difference), then hpet_time_after() will now incorrectly return 1.
> (Because bit#31 will be interpreted as the sign bit, turned on.)
> 
> Again, what speaks against
> 
>     return (b < a);
> 
> ?
> 
> (The pre-patch code dates back to commit 16b29ae1 (year 2008), which
> offers precious little justification for the formula.)

An hour or so after sending this email, I think I got an idea about the
code's intent. (Knowing practically nothing about HPET.) I guess the
HPET provides counters that can wrap around, so if you don't look
frequently enough, you won't know if the value is actually smaller or
greater (because you can't use raw magnitude to tell that).

So I *guess* this code implemented the following idea: assume you have a
"last value", and a reading (?) from "just a bit later". You take the
neighborhood (with radius 2^31, or 2^63) of the "last value", and if the
new reading falls into the upper half of that neighborhood, you say "the
value has grown".

This idea is actually very well suited for uintN_t modular arithmetic,
because the (x - y) difference expresses the number of times you have to
increment y to make it fall into the same remainder class as x, modulo 2^N.

Hence, ((x - y) < 2^(N-1)) expresses "x is later than or equal to y"
(with both x and y being uintN_t variables). Equivalently, we have ((x -
y) >= 2^(N-1)) meaning "x is strictly earlier than y", which can also be
said as "y is strictly after x".

And I think that's exactly what these functions implement:

- Their names say "time after".

- The condition

  (x - y) >= 2^(N-1)

  tests exactly whether the most significant bit is set in the
  difference.

  When the bit pattern of the difference is reinterpreted as intN_t,
  that in turn means

  (intN_t)(x - y) < 0

So the functions seem to check if "a is strictly after b".

... The call sites seem to confirm this:

        if (t->config & HPET_TN_32BIT) {
            while (hpet_time_after(cur_tick, t->cmp)) {
                t->cmp = (uint32_t)(t->cmp + t->period);
            }
        } else {
            while (hpet_time_after64(cur_tick, t->cmp)) {
                t->cmp += period;
            }
        }

The loops increment "t->cmp" as long as "cur_tick is strictly after
t->cmp"; in other words, the loops make "t->cmp" catch up with "cur_tick".

... I think the functions are right after all, it's just that the
following would have matched my personal taste more:

  b - a >= 1u << 31

and

  b - a >= 1ull << 63

(Because they don't have any impl-def parts in them, plus to me they
make the intent, with the modular arithmetic and the "neighborhoods",
clearer.)

I guess for others it's the opposite... :)

Cheers
Laszlo