llvm dev - Jan 2016 - [cfe-dev] RFC: Enforcing pointer type alignment in Clang

Hi John,

On 15 Jan 2016, at 08:14, John McCall via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> 
> The question at hand is whether we should require the user to write this:
>   misaligned_A_B *p = &a.b;
> instead of, say:
>   A::B *p = &a.b;
>   int x = *(misaligned_int*) &p->n;
> because we want to reserve the right to invoke undefined behavior and
propagate our “knowledge" that p is 4-byte-aligned to “improve” the
1-byte-aligned access on the next line.
> 
> My contention is that this is a clean and elegantly simple formal model
that is disastrously bad for actual users because it is no longer possible to
locally work around a mis-alignment bug without tracking the entire history of
the pointer.  It is the sort of compiler policy that gets people to roll their
eyes and ask for new options called things like -fno-strict-type-alignment which
gradually get adopted by 90% of projects.
I’ve had the misfortune to look at a lot of code that does unaligned access over
the last few years.  By far the most common reason for it that I’ve seen is
networking code that uses packed structures to represent packets.  For example:

__attribute__((packed))
struct somePacket
{
	uint8_t a;
	uint32_t b;
	// ...
};

In your model, what happens when:

- I use field b directly?
- I take the address of field b and store it in an int* variable?

David

> On Jan 18, 2016, at 3:18 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
> Hi John,
> 
> On 15 Jan 2016, at 08:14, John McCall via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>> 
>> The question at hand is whether we should require the user to write
this:
>>  misaligned_A_B *p = &a.b;
>> instead of, say:
>>  A::B *p = &a.b;
>>  int x = *(misaligned_int*) &p->n;
>> because we want to reserve the right to invoke undefined behavior and
propagate our “knowledge" that p is 4-byte-aligned to “improve” the
1-byte-aligned access on the next line.
>> 
>> My contention is that this is a clean and elegantly simple formal model
that is disastrously bad for actual users because it is no longer possible to
locally work around a mis-alignment bug without tracking the entire history of
the pointer.  It is the sort of compiler policy that gets people to roll their
eyes and ask for new options called things like -fno-strict-type-alignment which
gradually get adopted by 90% of projects.
> 
> I’ve had the misfortune to look at a lot of code that does unaligned access
over the last few years.  By far the most common reason for it that I’ve seen is
networking code that uses packed structures to represent packets.  For example:
> 
> __attribute__((packed))
> struct somePacket
> {
> 	uint8_t a;
> 	uint32_t b;
> 	// ...
> };
> 
> In your model, what happens when:
> 
> - I use field b directly?
The compiler recognizes that this access is to a valid but underaligned uint32_t
object and generates code assuming a lower alignment.  This doesn’t change,
except inasmuch as we gain a formal model that accepts the existence of
valid-but-underaligned objects.
> - I take the address of field b and store it in an int* variable?
It’s not undefined behavior to form that pointer.  It is, however, still
undefined behavior to access the object through that int*, because that type
assumes a higher alignment.  (The undefined behavior buys us a lot here:
otherwise, LLVM would have to assume that all pointers are unaligned unless it
could prove that they point to aligned memory.  That’s prohibitive.)  However,
if you don’t access the object as an int*, and instead access it in a
less-aligned way, there’s no undefined behavior and the code is guaranteed to
work.

For example, given this:
  uint32_t *pb = &packet->b;

Under my model, this code would still have undefined behavior and might trap on
an alignment-enforcing system:
  uint32_t b = *pb;

This code would still have undefined behavior, because the formal type of the
access is still uint32_t here:
  uint32_t b;
  memcpy(&b, pb, sizeof(b));

This code is fine:
  uint32_t b;
  memcpy(&b, (const char*) pb, sizeof(b));

As is this code:
  __attribute__((aligned(1))) typedef uint32_t unaligned_uint32_t;
  uint32_t b = *(unaligned_uint32_t*) pb;

Note that, under the language standards, both of the last two examples have
undefined behavior: there’s no concept of a valid unaligned object at all, and
if you shoe-horned one in, it would be probably be undefined behavior to take
its address.  Clang would be allowed to say “okay, you took the address of this,
and we can assume it was actually properly aligned despite being the address of
a less-aligned object” and then propagate that alignment assumption to the later
accesses to promote the alignment assumption.  The goal of my model — and
perhaps I’ve mis-formalized it, but I think the goal is quite clear — is just to
forswear this capability in the compiler.

John.

> On Jan 19, 2016, at 12:51 PM, John McCall <rjmccall at apple.com>
wrote:
> 
>> On Jan 18, 2016, at 3:18 AM, David Chisnall <David.Chisnall at
cl.cam.ac.uk> wrote:
>> Hi John,
>> 
>> On 15 Jan 2016, at 08:14, John McCall via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
>>> 
>>> The question at hand is whether we should require the user to write
this:
>>> misaligned_A_B *p = &a.b;
>>> instead of, say:
>>> A::B *p = &a.b;
>>> int x = *(misaligned_int*) &p->n;
>>> because we want to reserve the right to invoke undefined behavior
and propagate our “knowledge" that p is 4-byte-aligned to “improve” the
1-byte-aligned access on the next line.
>>> 
>>> My contention is that this is a clean and elegantly simple formal
model that is disastrously bad for actual users because it is no longer possible
to locally work around a mis-alignment bug without tracking the entire history
of the pointer.  It is the sort of compiler policy that gets people to roll
their eyes and ask for new options called things like -fno-strict-type-alignment
which gradually get adopted by 90% of projects.
>> 
>> I’ve had the misfortune to look at a lot of code that does unaligned
access over the last few years.  By far the most common reason for it that I’ve
seen is networking code that uses packed structures to represent packets.  For
example:
>> 
>> __attribute__((packed))
>> struct somePacket
>> {
>> 	uint8_t a;
>> 	uint32_t b;
>> 	// ...
>> };
>> 
>> In your model, what happens when:
>> 
>> - I use field b directly?
> 
> The compiler recognizes that this access is to a valid but underaligned
uint32_t object and generates code assuming a lower alignment.  This doesn’t
change, except inasmuch as we gain a formal model that accepts the existence of
valid-but-underaligned objects.
> 
>> - I take the address of field b and store it in an int* variable?
> 
> It’s not undefined behavior to form that pointer.  It is, however, still
undefined behavior to access the object through that int*, because that type
assumes a higher alignment. (The undefined behavior buys us a lot here:
otherwise, LLVM would have to assume that all pointers are unaligned unless it
could prove that they point to aligned memory. That’s prohibitive.)  However, if
you don’t access the object as an int*, and instead access it in a less-aligned
way, there’s no undefined behavior and the code is guaranteed to work.
> 
> For example, given this:
>  uint32_t *pb = &packet->b;
> 
> Under my model, this code would still have undefined behavior and might
trap on an alignment-enforcing system:
>  uint32_t b = *pb;
> 
> This code would still have undefined behavior, because the formal type of
the access is still uint32_t here:
>  uint32_t b;
>  memcpy(&b, pb, sizeof(b));
> 
> This code is fine:
>  uint32_t b;
>  memcpy(&b, (const char*) pb, sizeof(b));
> 
> As is this code:
>  __attribute__((aligned(1))) typedef uint32_t unaligned_uint32_t;
>  uint32_t b = *(unaligned_uint32_t*) pb;
> 
> Note that, under the language standards, both of the last two examples have
undefined behavior: there’s no concept of a valid unaligned object at all, and
if you shoe-horned one in, it would be probably be undefined behavior to take
its address.  Clang would be allowed to say “okay, you took the address of this,
and we can assume it was actually properly aligned despite being the address of
a less-aligned object” and then propagate that alignment assumption to the later
accesses to promote the alignment assumption. The goal of my model — and perhaps
I’ve mis-formalized it, but I think the goal is quite clear — is just to
forswear this capability in the compiler.

I think everything you said above is uncontroversial. I believe everyone here is
in agreement that reinterpret_casts back and forth to arbitrary pointer types
are currently allowed, and must continue to be, allowed by clang. Richard
suggested a spec-diff to formalize that. As an implication of that being valid,
the cast itself does not and must not in the future impart any knowledge of
alignment (even though doing so would be theoretically okay per the current
language spec).

That is, for clarity, clang does now and should always continue to allow the
following, despite the spec saying it doesn't need to:

  char *x = malloc(10);
  int *y = (int*)&x[1]; // assign a misaligned int*.
  char c = *(char*)y; // but accessed only as char*, so no problem.

However, one part of your suggested rules that both I and Richard questioned was
the requirement that the expression "&p->n" be valid, even if
"p" is misaligned for its type. I still don't think that it's
necessary or even particularly useful to start allowing that. And, note, that
would be an actual change in behavior, not a clarification/formalization of
existing behavior.

That is:
1) Is it valid to do "p->n", when p is not a valid object which is
properly aligned for its type?
2) Assuming that's not valid, does adding a & cause it to then be valid,
via some special case? E.g. the rule in C that states that "&a[n]"
translates to "(a + n)", and "&*a" translates to
"a", regardless of the value or validity of "a". (Without
that rule, &*a would be invalid, too, if "a" was null or
misaligned.)

Just to reiterate, I think the issue here is **not** about whether clang can
make alignment assumptions in later code, it's about whether the member
access expression *itself* is valid. (If it's not valid, then what happens
in later code is irrelevant.)

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160120/df563fa5/attachment.html>

On 19 Jan 2016, at 17:51, John McCall <rjmccall at apple.com>
wrote:
> 
>  uint32_t *pb = &packet->b;
> 
> Under my model, this code would still have undefined behavior and might
trap on an alignment-enforcing system:
>  uint32_t b = *pb;
We already have a warning for almost this cast, but it’s flawed in two respects:

- It’s noisy, so people normally turn it off.
- It’s silenced by an explicit cast.

The latter is problematic again in your model, because programmers now get no
warning when they do the dangerous thing.
> This code would still have undefined behavior, because the formal type of
the access is still uint32_t here:
>  uint32_t b;
>  memcpy(&b, pb, sizeof(b));
> 
> This code is fine:
>  uint32_t b;
>  memcpy(&b, (const char*) pb, sizeof(b));
This makes me nervous, because presumably void* has an alignment of 1 and now we
have different behaviour depending on whether we perform an implicit or explicit
cast.

I’m also somewhat uncomfortable with the idea that assigning a uint32_t*
temporary to a uint32_t* variable increases its alignment.  I’d be tempted to
propose modelling the alignment more explicitly in the C type system, so that
&pb is not a uint32_t*, it’s a __alignment__(1) uint32_t* and can’t be
implicitly cast to a uint32_t*.  That would mean that we could explicitly warn
on casts that increased the alignment and provide a type for b that would both
preserve the (lack of) alignment.  For example:

typedef __attribute__((aligned(1))) uint32_t unaligned_uint32_t;

struct foo
{
    char a;
    uint32_t b;
}
__attribute__((packed));

struct foo packet;
...
uint32_t *pb = &packet.b;
unaligned_uint32_t *upb = &packet.b;

Currently, this code is accepted by clang.  I would propose that:

// This should not be allowed (or, if it is, with a warning that can be turned
into an error)
uint32_t *pb = &packet.b;
// This should be permitted, but the static analyser should complain
uint32_t *pb = (uint32_t*)&packet.b;
// This should be permitted to silently work
unaligned_uint32_t *upb = &packet.b;

I believe that you would get most of this from clang by implicitly providing the
alignment information to members of packed structs.  This would mean that the
type of packet.b would implicitly be unaligned_uint32_t, not uint32_t.
> As is this code:
>  __attribute__((aligned(1))) typedef uint32_t unaligned_uint32_t;
>  uint32_t b = *(unaligned_uint32_t*) pb;
> 
> Note that, under the language standards, both of the last two examples have
undefined behavior: there’s no concept of a valid unaligned object at all, and
if you shoe-horned one in, it would be probably be undefined behavior to take
its address.  Clang would be allowed to say “okay, you took the address of this,
and we can assume it was actually properly aligned despite being the address of
a less-aligned object” and then propagate that alignment assumption to the later
accesses to promote the alignment assumption.  The goal of my model — and
perhaps I’ve mis-formalized it, but I think the goal is quite clear — is just to
forswear this capability in the compiler.
This is, as you say, a language extension, but it’s one that’s been supported by
GCC since at least the 2.x days and existing code relies on it.

David