Re: [Qemu-devel] [PATCH 1/2] target-i386: Use 1UL for bit shift

[Laszlo Ersek]

On 10/02/15 10:34, Paolo Bonzini wrote:
> 
> 
> On 01/10/2015 21:17, Laszlo Ersek wrote:
>> - In the firmware, allocate an array of bytes, dynamically. This array
>>   will have no declared type.
>>
>> - Populate the array byte-wise, from fw_cfg. Because the stores happen
>>   through character-typed lvalues, they do not "imbue" the target
>>   object with any effective type, for further accesses that do not
>>   modify the value. (I.e., for further reads.)
>>
>> - Get a (uint8_t*) into the array somewhere, and cast it to
>>   (struct acpi_table_hdr *). Read fields through the cast pointer.
>>   Assuming no out-of-bounds situation (considering the entire
>>   pointed to acpi_table_hdr struct), and assuming no alignment
>>   violations for the fields (which is implementation-defined), these
>>   accesses will be fine.
>>
>> *However*. If in point 2 you populate the array with uint64_t accesses,
>> that *does* imbue the array elements with an effective type that is
>> binding for further read accesses.
> 
> Then don't do it.  Use memcpy from uint64_t to the array.

It won't work; memcpy() propagates the effective type. (So does a loop
that copies char-wise.) From 6.5p7:

    If a value is copied into an object having no declared type using
    /memcpy/ or /memmove/, or is copied as an array of character type,
    then the effective type of the modified object for that access and
    for subsequent accesses that do not modify the value is the
    effective type of the object from which the value is copied, if it
    has one.

> Type punning
> has other problems than aliasing---for example some architectures
> require pointers to be correctly aligned when accessing objects bigger
> than a byte.

I definitely agree that alignment is a question to be considered; in
fact the C standard speaks about pointer alignment with reference to
pointer *conversion*, not pointer dereferencing. (In other words, if you
cast a pointer-to-typeA to pointer-to-typeB, and the result is not
correctly aligned for typeB, then you get undefined behavior right at
the conversion, regardless of dereferencing the cast pointer later or
not.) 6.3.2.3p7:

    A pointer to an object or incomplete type may be converted to a
    pointer to a different object or incomplete type. If the resulting
    pointer is not correctly aligned (footnote 57) for the pointed-to
    type, the behavior is undefined. [...]

(
Footnote 57:

    In general, the concept ‘‘correctly aligned’’ is transitive: if a
    pointer to type A is correctly aligned for a pointer to type B,
    which in turn is correctly aligned for a pointer to type C, then a
    pointer to type A is correctly aligned for a pointer to type C.
)

However, alignment requirements are implementation-defined, and if you
know your platform (and in low level code you frequently do), you can
cover that base.

> 
>> ... I don't know who on earth has brain capacity for tracking this.
> 
> If you can't understand a rule (or understanding it burns too much of
> your brain cycles), just find a pattern that lets you respect it without
> much thought.

I understand the rule just fine. *Applying* the rule consistently is
very costly.

> For strict aliasing it's just "don't cast pointer types"
> with a single exception, namely casting a pointer to struct to a pointer
> to the first member's type and the other way round.  Everything else can
> either be expressed as container_of, or simply prohibited.

How about parsing network data? Assume that you have verified the size
of the uint8_t buffer, and that you have verified the message type with
direct *(uint8_t*) access. Assume further that you have a sequence of
such messages concatenated, each with a different type (implying a
different struct).

I don't see how unions would apply here with any flexibility. One thing
that would certainly work is to define one separate local variable for
each possible message type (ie. struct) -- or create one union variable
that can contain each one of those structs --, and then memcpy() data
from the buffer into the right variable (or union member) before
accessing the message fields in that variable / struct. The constant
copying is incredibly annoying, compared to advancing a uint8_t* pointer
in the buffer, checking remaining buffer size, and casting.

(I wonder if reinterpret_cast<>() would allow this in C++, BTW.)

> 
>> Effective type *does* propagate in a trackable manner, but it is one
>> order of magnitude harder to follow for humans than integer conversions
>> -- and resultant ranges -- are (and those are hard enough already!).
> 
> Integer conversions are already too much for me, in fact.
> 
> Here my pattern there is just: 1) use uint16_t as sparsely as possible
> (because the result of a multiplication can overflow, unlike uint8_t);

Okay, I think I can follow that...

> 2) never write unsigned int constants

Ah, so this is where it comes from! :)

So, I guess the idea is that you'd like to stay in "int" as much as
possible. (And, with respect to the above point, both uint8_t and
uint16_t are promoted to int (=== int32_t), on all platforms that matter.)

>---this doesn't apply to unsigned
> long long constants, which instead I use liberally; 3) rely heavily on
> Coverity to detect narrow types being used as {,u}int64_t after
> arithmetic has been done on int.

I see -- Coverity should help to identify expressions where the cast
should be done before doing the arithmetic.

> 
> Never writing unsigned int constants conflicts heavily with this ubsan
> rule.  And I can always use the excuse that I'm writing gnu89 code
> rather than c99. :)

I see.

In comparison, I'm a huge fan of unsigned-only, both in variables /
fields and in constants. :)

One random example: (a - b). If "a" and "b" are unsigned, then (1)
wrapping is well-defined, (2) if you don't want it, it is easy to detect
beforehand:

  if (a < b) { no can do }

However, if "a" and "b" are both signed ints, then (1) wrapping in the
subtraction is undefined behavior, (2) if you want to prevent it, the
failure condition *in math* (not in C) is:

  (a - b) < INT_MIN || (a - b) > INT_MAX

How can we evaluate that?

*** If (a >= b), then the first condition is false, and the second
condition decides. The second condition is equivalent to both of:

  a           > INT_MAX + b [i]
  a - INT_MAX > b           [ii]

[i] Since adding INT_MAX, a positive value, increases the sum, the
expression (INT_MAX + b) can be evaluated if

  (INT_MAX + b) <= INT_MAX

in other words, if

  b <= 0

[ii] Otherwise, (a - INT_MAX) can always be evaluated. This is because
the requirement is

  a - INT_MAX >= INT_MIN

(since subtracting a positive value decreases the sum), which is
equivalent to

  a  >= INT_MIN + INT_MAX

Now, we have (b > 0) here -- this is the "otherwise" branch of [i] --,
and our starting condition was (a >= b), therefore we have (a > 0),
which implies the above.

Thus, for the (a >= b) case, we have, as failure condition:

  (b <= 0) ? (a > INT_MAX + b) : (a - INT_MAX > b)

**** If (a < b), then the second condition is false, and the first
condition decides. The first condition is equivalent to both of:

  a           < INT_MIN + b [iii]
  a - INT_MIN < b           [iv]

[iii] Since adding INT_MIN, a negative value, decreases the sum, the
expression (INT_MIN + b) can be evaluated if:

  (INT_MIN + b) >= INT_MIN

in other words, if

  b >= 0

[iv] Otherwise, since subtracting INT_MIN, a negative value, increases
the sum, the expression (a - INT_MIN) can be evaluated if:

  (a - INT_MIN) <= INT_MAX

which is equivalent to

  a <= INT_MAX + INT_MIN

Now, we have (b < 0) here -- we're on the "otherwise" branch of [iii]
--, plus our starting condition was (a < b). Those together mean

  a < -1

which guarantees our requirement

 a <= INT_MAX + INT_MIN

Therefore (a - INT_MIN) can always be evaluated on this branch.

Leaving us with the following failure condition, for the (a < b) case:

  (b >= 0) ? (a < INT_MIN + b) : (a - INT_MIN < b)

**** The final condition is

(a >= b) ? ((b <= 0) ? (a > INT_MAX + b) : (a - INT_MAX > b))
         : ((b >= 0) ? (a < INT_MIN + b) : (a - INT_MIN < b))

If this evaluates to true, then (a - b) would be undefined behavior.

... Given that we almost never need negative integer values, I'd rather
stick with unsigned variables, unsigned constants, and write (a<b), in
order to check against wrapping, than use the above monstrosity. (If I
messed up the calculation, that only strengthens my point.)

Sure, we can always cast to int64_t first... and if we're subtracting
int64_t, we can always cast to Int128 first... :P

Laszlo