[Edited again, 2012-02-17. Simplified argument].
My previous posts (here and elsewhere) about C99′s so-called aliasing rules made statements about what those rules really mean that some people don’t agree with. It’s worth delving into the issue again, with critical reference to the actual standard. The rules are complex. Having examined the standard thoroughly, I now believe my original take was wrong (although the arguments made by others against it were mostly incorrect).
Status Quo
There are a few attempts to explain C99 aliasing in various places on the web. If you’re new to the issue, here’s a brief summary: C99 essentially requires that memory (an “object” in C99 parlance) is accessed via a consistent pointer type, so for instance if you access something via an “int *” (i.e. an lvalue of type “int”) then you shouldn’t then attempt to read it via a “float *”. The relevant section of the standard is 6.5 paragraph 7. There are some exceptions listed there to the general rule; importantly, you are always allowed to accesss memory via a character type (eg char *) and via memcpy() and memmove(). The contentious part is that you can access an object via an lvalue whose type is an aggregate type (structure or union) with a member whose type is that of the object being accessed. This was discussed in my previous blog entry; it essentially allows access to an int value (for example) via a pointer to a union with an int member, the contentious issue being whether or not the value must actually be a member of the union in question (more discussion will follow).
GCC relaxes the aliasing rules in one sense, that is, access to the same object is allowed via two incompatible types so long as the types are members of a union and that access is, in both cases, done through the union. This extension is widely used in open-source code, however I must stress this technique is not strictly conformant with C99 and is not necessarily portable to other, fully C99 compliant compilers; I will discuss it further below. Another way to access an object as another type is to copy its value to a variable of the other type via a “char *” or memcpy() (if the value is to be modified, the modification can then be copied back in the same manner). Certainly this might seem less efficient, but a clever compiler should be able to recognize what is being attempted and optimize it accordingly (at the time of writing, GCC doesn’t do this very well).
Analysing the standard
6.5p7 states that “objects can have their stored value accessed only by an lvalue expression” that has one of various types. Note that the word “expression” in this paragraph is redundant seeing as an lvalue is defined (in 6.3.2.1p1) as being a kind of expression.
Aside: One problem with the statement in 6.5p7 is that expressions can be compound, that is, an expression can be made up of other expressions (as in “expression1 + expression2″) and in this case the subexpression might be an lvalue of an appropriate type, but the compound expression might not be (and indeed might not even be an lvalue). Arguably, the compound expression still accesses the object and thus breaks the aliasing rules; however, it is doubtful that there exists any non-trivial program which abides by this interpretation, seeing as it seems to make writing meaningful programs very difficult. We have to assume then that if an object is “accessed by an expression” it does not mean the object is accessed also by a compound expression containing that expression, which seems unintuitive but which is not (as far as I can tell) directly contradicted anywhere in the standard.
Clearly 6.5p7 regulates acess to objects; so what is an object? The definition in the standard is that an object is a region of data storage, the contents of which can represent one or more values; it also notes that objects may have an associated type. Also, 6.2.5p20 states that a structure type describes a set of member objects. Although it is never explicated, there is certainly an implication here that objects can overlap, that is, a structure object overlaps its various member objects.
The fact that access is allowed through an aggregate type (containing a member with a compatible type) is really interesting, as it appears to give us a clue as to how “access” is to be interpreted in the case of overlapping objects. Section 3.1 defines access as reading or modifying the value of an object, however it is not clear if accessing a member object of an aggregate type also should be considered an access of the aggregate object, and vice-versa.
For example: in an expression such as “a.b”, what is the type of the lvalue through which access occurs? Is it:
- The type of “a” (let’s call it “struct A”) or
- The type of “b” (let’s call it “B”) or
- There are two accesses, one via the type of “a” and one via the type of “b”
For guidance we look elsewhere in the standard. In 6.5.2.3, member access is defined (as a postfix operator). The type of such an expression is certainly the type of the member, so this seems like it is an access of the member object via its type – which is clearly allowed.
What about if we copy a structure directly however? For example, in the expression “s1 = s2″, where s1 and s2 are of the same union type, there is no explicit member access. It could however easily be argued that a struct object access also constitutes access to each of the struct members, and that is presumably why 6.5p7 allows access to an object via an expression which as “an aggregate type … containing one of the aforementioned types”. (it is also arguable that an expression such as “a.b”, where “a” is a struct type, access both the container object and the member object).
Interestingly enough, though, there seems to be an assumption that access to a member object by itself does not access a containing object. For instance, consider the following:
struct A {
int a;
int b;
} s_a;
s_a.a = 1;
s_a.b = 2;
int *p = &s.a;
*p = 3;
I have a lot of trouble believing that the code sample above could have undefined behaviour, however the only way that this code’s behaviour could be defined according to 6.5p7 is if accessing a member object does not also constitute access to a containing aggregate object. It is unfortunate that the definition of access seems to preclude this – since an access is to “modify the value of an object”, and surely modifying an aggregate member value also modifies the value of the aggregate object?
It’s worth noting that for the case of indirect member access (e.g. “(&a)->b”) the standard is a little more clear as to what is being accessed: In this case the value is that of “the named member of the object to which the first expression points” (i.e. it is the “b” member of the “a” object).
Anyway, we have reached what seems to be a reasonable understanding. Accessing an object does not constitute access to the containing object; however accessing a container object also accesses all contained members (bearing in mind that a union only ever “contains” one member at a time, as will be elaborated on below). With this interpretation of “access” in mind, 6.5p7 seems quite reasonable.
There’s just one problem.
6.2.6.1 discusses trap representations. Essentially a “trap representation” is an invalid value which causes undefined behavior when it is accessed or generated. Paragraph 6 contains this interesting snippet:
The value of a structure or union object is never a trap representation, even though the value of a member of the structure or union object may be a trap representation.
The purpose of this seems to be to allow access to structures (and unions) which may have, for instance, uninitialized fields. Unfortunately, this doesn’t work if we assume, as we did before in order to reconcile with 6.5p7, that access to an object also constitutes access to all contained objects. Thus, even if the structure value itself is not a trap representation, accessing a structure object with a field whose value was a trap representation would still cause undefined behavior (according to p5).
It is unfortunate that the C99 standard is not clearer on the relationship between overlapping (aggregate and union) objects. I can see no good way to reconcile the text of the standard with the current consensus understanding of the language. About the best we can do is say that accessing a member object does not constitute access to the containing object, nor vice versa; this however makes part of 6.5p7 redundant.
What about unions?
Union types presumably exist as a convenient way to allocate storage suitable for one of various object types, but they are also commonly used (as discussed above) for accessing the contents of an object (with an effective type) via a different type (“type punning”). For instance I can store a value into a float member of the union and then access the int member of the union to interpret the representation as an int. Or… can I? Although GCC allows this (so long as all accesses occur through the union type) and many open-source programs make use of it, the standard states that the value of a union member other than the last one stored is unspecified (Annex J.1).
For instance, 6.2.6.1p5 states that accessing a value that is a trap representation results in undefined behaviour. However, if we apply the same rules that we inferred for struct types, then accessing a union access all its members… now, if any one them has a trap representation, then the behaviour is undefined! Presumably, this is not intended, and in fact the standard does imply that only one member is accessed when accessing the union (as will be discussed).
What specifically does the standard have to say about unions?
- 6.2.5p20, which tells us that a union has “an overlapping set of member objects”
- Footnote 37 from 6.2.5p22, which says that “an object with union type can contain only one member at a time”
- 6.2.6.1p6, which says that a union object may not be a trap representation, although its member objects may be
- 6.7.2.1p14, which says that “the value of at most one of the members can be stored in a union object at any time”
- Annex J.1 says that “the value of a union member other than the last one stored into” is unspecified.
- In TC3, a footnote is added which specifies that accessing a member of a union other than the last one stored causes “the object representation” to be re-interpreted in the new type and specifically refers to this as “type-punning”. This seems to contradict Annex J.1.
The note in Annex J.1 seems to indicate that type punning via a union is not portable, but this is directly contradicted in Technical Corregendum 3.
Defect Report 236
It’s worth referring to C99 defect report 236 at this point. The report includes two examples of code with aliasing concerns and asks whether they are conforming. I agree with the response for example 2 (it is impossible to store to the member of a union when that member isn’t active, and the union is the declared and therefore the effective type; therefore the store must be via either the active type [i.e. a pointer to the active member] or the union type). Example 1 on the other hand is clearly conforming; yet, the committee response is that both programs “invoke undefined behaviour”. It is acknowledged that the wording of the standard requires changing and yet I see no changes to 6.5p7 in any later drafts.
Note that the ability to change the effective type of an object (which has no declared type) by storing a value, as implied by 6.5p7, is useful for re-using allocated storage; that is, it becomes possible to store a value of one type and later use the same storage for a value of another type. This is a potentially worthwhile usage. I have been informed by a GCC developer that GCC supports this usage.
It is certainly odd that the DR236 is closed, and yet the response clearly contradicts the standard, yet there is no resolution. Without such a resolution it can only be assumed that the response was drafted and was neglected to be amended when the report was closed. To take any other standpoint is to stand in contradiction of the wording of the standard.
Note also that the wording doesn’t disallow all type-based alias analysis, and arguably doesn’t prevent most useful type-based alias analysis. For instance, it is still possible to re-order read operations.
Can an object be accessed by first casting to an aggregate or union type?
The question brought up by Joshua Haberman on the GCC developers’ mailing list (which I discussed previously) was whether a variable value can be accessed by first casting its address to a union pointer where the union contained the original type as a member. 6.5p7 would seem to allow this; the only two legitimate arguments against this were that alignment requirements need to be met (it was pointed out that this could be ensured by other means) and that it might not be valid to dereference a pointer obtained by performing such a cast. This latter argument was brought up by Andrew Haley. Initially I was skeptical, but to be fair we must consult the standard document and see what it says in regards to pointer conversion and dereferencing.
6.5.3.2p4 states that if an invalid value has been assigned to a pointer which is dereferenced, the behaviour is undefined. Given that this seems almost tautological, it is strange that it explicitly requires that the invalid value has been assigned rather than just that the value is invalid. For instance, if I obtain a pointer via a cast (or some other operation) then surely the pointer can be invalid without an assignment of that invalid value ever having taken place, and surely its dereference should still result in undefined behaviour. (Really, in this case the behaviour is still undefined by virtue of it… well, not being defined).
6.3.2.3 states all the ways in which pointers can be converted to different types. Amongst other things, it ensures that we can convert a “T *” (for any type T) to a “void *” and back and guarentee that the “result will compare equal” to the original pointer. 6.5.9p5 adds that pointers which compare equal will point to the same object (including an object and a subobject at its beginning). 6.3.2.3p7 allows us to convert to any pointer type (not just “void *”) and back, yielding an equal pointer, so long as alignment requirements are met. It does not however say what the resulting pointer actually points at, except in the case of the converted-to type being “a pointer to character type” where the result points at the first byte of the object. 6.7.2.1p13 suggests that converting between a pointer to a struct type and a pointer to the type of its first member yields a pointer to the first member (i.e. the ‘expected’ semantics) and vice versa.
That is enough information to think that we should be able to take a pointer to a structure’s first member (named “m”, of type “M”) and convert it to a pointer to the structure itself, safely, and dereference that pointer.
Aside: why does 6.5.9p6 assert that two pointers can compare equal if one points “one past the end of an array object” and the other points to “the start address of a different array object” [which happens to immediately follow the first in the address space]? Why isn’t it enough to assert that it point at the start address of any other object at that location? As worded, this would force compilers not to allocate non-array objects just beyond the end of an array, except that it could probably be argued that two pointers in this situation “point to the same object” anyway). (ah – there is already a defect report #215 about this, though Technical Corregendum 3 doesn’t fix it).
Having determined that we can correctly convert a pointer-to-member into a pointer-to-structure, the next question is: what happens if we do so, and dereference the result, when there isn’t actually a structure object there? (replace “structure” with “union” as you please). This is essentially what Joshua Haberman was asking about. Considering all the above, I find I must reconsider my original position: that is, you cannot dereference a “T *” if there is no “T” at the pointed-to location, even if the members of T are there. This is essentially due to definition: dereferencing a pointer accesses the value of an object, which is clearly not possible if there is no object.
Conclusion
I have analysed the C99 standard in regards to aliasing reasonably thoroughly, more so than any other web resource that I’m aware of. The standard is unfortunately very unclear and we are forced to make various assumptions if we want to interpret it in anything like the common understanding (as implemented by compilers). Hopefully, the next revision of the standard will improve. Come on guys – get it right!
Posted by davmac 
