Formerly: C99 revisited
[None of the issues discussed here have, to my knowledge, been addressed in the much newer C11 standard. I have edited this document from time to time, when I discovered relevant parts of the standard or made new revelations].
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 now examined the standard thoroughly, I think my original take was not 100% correct, but I’m also left with the strong impression that the standard document has serious issues.
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() (although even this can be problematic, as per later discussion). It is also allowed to 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 would seem to 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 a union object (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, and though it is not strictly conformant with C99 [nor C11] according to the current wording it is most likely intended to be supported of the standard (see the note on TC3, to follow). 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, with significant caveats). Certainly this might seem less efficient, but a clever compiler should be able to recognize what is being attempted and optimize it accordingly (although at the time of writing, GCC doesn’t always 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. It’s also not completely certain how an expression can access a stored value; it seems likely that what is meant here is that evaluation of an lvalue can cause access to a stored value.
Clearly 6.5p7 regulates access 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. There is 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”
Also, there’s the question of which object or objects are accessed. Is it:
- The object representing the “b” member of the aggregate or
- The aggregate object “a” or
- Both the aggregate object and the member object or
- The aggregate object and all its member objects, recursively.
Unfortunately the definition of “access” provided is very weak. For guidance we look elsewhere in the standard. In 6.5.2.3, member access is defined (as a postfix operator), and specifies that the value is that of the member and that the lvalue type is that of the member; but it is not clear if the access is actually to the aggregate/union object (and the member value is then extracted from this), or is directly to the member, or whether there are two distinct accesses (one to the containing object and one to the member object). None of these would be ruled out by 6.5p7.
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”. (In fact it seems justifiable to assume than an expression such as “a.b”, where “a” is a struct type, accesses both the container object and the member object, where the lvalue for access to the container object is “a”, and that it actually causes access to all member objects when evaluated).
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?
Anyway, we have reached what seems to be a consistent 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). This both allows access to a structure member via a pointer to the member type, and justifies the allowance for accessing a member object via the containing aggregate type. With this interpretation of “access” in mind, 6.5p7 seems quite reasonable.
Trap representations.
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 immediately preceding paragraph (6.2.6.1p5):
If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined.
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. (We could try to work around this by instead saying that only reading an aggregate object does not access its members, but that writing to one does; however, there doesn’t seem to be any text that would justify such a differentiation).
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) – specifically:
The following are unspecified:
- The value of a union member other than the last one stored into
This is underneath the heading “J.1 Unspecified Behavior”. Since “unspecified behavior” and “unspecified values” are different things, it’s not really clear which is intended here, however an “an unspecified value cannot be a trap representation” (3.17.3). The TC3 amendments add a footnote which allows type-punning via a union, but notes that “This might be a trap representation.” [apparently Annex J was forgotten. It was, however, amended in the later C11 standard, removing the above point from the list].
(Note that the Annexes are not considered normative, that is, they supplement the main text, but they should not impose additional requirements. In this case the annex claims that there is no requirement on the value of inactive union members. The footnote added in the amendment would appear to change that, however, footnotes aren’t normative either. This implies that either that the footnote is incorrect, or that the statement in Annex J was incorrect even before the addition of the footnote.)
Now, 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… and, 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.5.2.3, which says that the value of an expression using the union member access operators (“.” or “->”) is “The value is that of the named member” (and the footnote added in TC3, mentioned below).
- 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 [removed in C11].
- 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 conflicts to some degree with Annex J.1.
Note that footnote 82, added in C99’s Technical Corrigendum #3, seems to allow type punning through a union. However, being a footnote, it is non-normative, meaning that it should only clarify the regular text; unfortunately, in this case, it seems to actually contradict the normative text. Specifically, (6.7.2.1) “the value of at most one of the members can be stored in a union object at any time” together with (6.5.2.3) “The value is that of the named member” strongly implies that reading the value of a “non-active” union member should be impossible.
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 and my testing indicates that it does (version 4.8.3). The suggested change in DR236 disallows such usage.
It seems odd that the DR236 is closed, with a resolution that appears to conflict with the present wording of the standard, yet no amendment was ever made.
Note that the current 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.
Update 30-May-2014: More recently, I’ve stumbled on the N1520 proposal, titled “Fixing the rules for type-based aliasing“, which is interesting as it gives some insight into what at least one ISO committee member believes is the intended effect of the standard. However, it’s dated 2010, it has not (as far as I know) been implemented, and it fails to address several shortcomings in the current wording (the “one problem” mentioned above, and exactly how/when objects come into existence; the document itself acknowledges this second issue, but does not address it). At one point the author appears to be highly confused:
Basically, if it is kept in mind that an lvalue expression (as mentioned in the introductory clause of 6.5p7) with aggregate or union type implies access of all of its member subobjects (recursively), and that accessing a subobject of an aggregate or union constitutes an access to the containing aggregate or union, it seems to me that the fifth bullet is not necessary, and could just be deleted.
As best as I can tell, the purpose of the fifth bullet is specifically to allow this access (i.e. it allows aggregate object access to access all member objects). If you removed the fifth bullet, then such access would no longer be allowed, and if you assume – as N1520 suggests – that accessing an aggregate object also implies access to the subobjects, then you would no longer be allowed to access any aggregate object because 6.5p7 would now prevent the implied access to the subobjects.
So, 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, if one is liberal in interpretation, 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’d need to look at relevant portions of the standard.
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 guarantee 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 (the precise wording is “suitable converted”, an operation which is not actually defined).
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. However, we can only do this if an object of the structure type actually exists, since otherwise the result of the pointer conversion is not specified.
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).
So, with a strict interpretation of the standard, you cannot in general dereference a “T *” if there is no “T” at the pointed-to location, even if the members of T are there. This is due primarily to the pointer conversion not being defined if we attempt to produce a “T *” for a location where there is no “T” object, which is likely a surprising result to many who assume that this is instead a result of the strict-aliasing rules in §6.5.
I believe that this is what led Josh Haberman eventually (see his comment on this post, below) to decide that 6.5p7 is not normative. However, this is erroneous, since it is still in fact possible to create a pointer to an object which is of the wrong type:
void * m = malloc(sizeof(int) + sizeof(float));
// object '*m' has no effective type at this point
int * i = m;
*i = 5; // effective type is now int (6.5p6)
float * f = m;
*f = 5.0; // effective type is now float (6.5p6)
// i still points to the object (which is now of type float)
int a = *i; // this access is not allowed due to 6.5p7
6.5p7 prevents this kind of aliasing.
On the other hand, although the result of a pointer conversion between a pointer to a member type and a pointer to the containing structure type is only specified if a structure object actually exists, in practice (for most common architectures and compilers) we know exactly what the result of such a conversion will be – it will be a pointer that points to the same location but having a different type. This can even be proved by asserting that the two pointers are equal after the conversion (such a comparison isn’t actually allowed in C99, because it limits the types of pointers that can be compared with each other; however, compilers generally lift this restriction and allow comparison of pointers of arbitrary type).
With this in mind, we could cast a pointer-to-first-member to a pointer-to-containing-structure and then 6.5p7 would not appear to prevent accessing the first member via the structure pointer. If the member were then accessed via the ‘->’ operator we could consult 6.5.2.3p4:
A postfix expression followed by the -> operator and an identifier designates a member of a structure or union object. The value is that of the named member of the object to which the first expression points, and is an lvalue. […]
Now, this could (and I suggest should) be interpreted as requiring that the pointer does point to an existing object of the structure type, since otherwise the named member cannot exist. (Possibly, it also causes access to this structure object). I think this is the strongest argument for why you cannot ‘cast into existence’ a structure or union object, even though the result of the pointer conversion is known (if implementation-defined).
Consensus Interpretation on unions (GCC and LLVM)
In general problems arise can arise when compiling with GCC and where an access to a struct member occurs where the there is no struct object. That is to say, if we do:
a = p->m;
… then this is seen as constituting an access to the object pointed to by ‘p’ rather than just the member object ‘m’, and the access to this object is bound by the strict aliasing rules.
Making sense of the union rules is difficult. The intent of footnote 82 is clearly to allow type-punning through a union, but if the compiler must assume that two arbitrary pointers may alias due to pointing at different members of the same union, then pretty much all type-based alias analysis (TBAA) goes out the window and the strict-aliasing rules (C99 6.5p7) are pointless. The GCC documentation for the -fstrict-aliasing switch clearly states that:
type-punning is allowed, provided the memory is accessed through the union type
I.e. you can use a union for type punning but access via both types must be “through the union type”, i.e. they must be performed as member accesses. LLVM seems to follow the same restriction (shown by testing behavior with some simple test cases; LLVM 3.6.1).
6.5.2.3 contains a paragraph seemingly legitimising a certain limited form of type punning, where structure types having a “common initial sequence” are punned via a union. C99 requires that the union declaration be visible, implying that (unlike the GCC requirement) access need not be through the union type (since if access were required to be through the union type, then the union type would necessarily be visible and it would not be necessary to require this explicitly). However, GCC does not appear to support even this limited form of type punning unless accesses are via the union type. (It’s worth noting that it’s not clear whether de-referencing a pointer to an inactive union member is legal anyway – does the member object actually exist? Would attempting such result instead in accessing the active member, thereby potentially violating the aliasing rules?).
Type punning via ‘char *’ and ‘memcpy’
6.5p7 does allow access to any object via a “char *” pointer and via the “memcpy” and “memmove” standard library functions. Naively, you might think this was sufficient to allow type punning (and it does allow a limited form). For instance, suppose we have a pointer (“fp”) to a “float” value which we want to reinterpret as an “int”:
int r;
memcpy(&r, fp, sizeof(int));
There is little doubt that the above code does not invoke undefined behavior, assuming that sizeof(float) >= sizeof(int), though the value of r is not specified and presumably may be a trap value. If we modify the value of “r” we should in theory then be able to copy the representation back to the original location:
r = ...;
memcpy(fp, &r, sizeof(int));
Again this should be fine. The problem is that we then attempt to read the floating point value (assume we can guarantee somehow that it is not a trap representation):
float f = *fp;
Surprisingly, this last line could fall foul of the strict aliasing rules (6.5). Whether this is the case depends on whether the “*fp” object has a declared type or not. According to the standard, copying an “int” actually alters the effective type of the destination object if it has no declared type. In the case that “fp” points to a dynamically allocated object (i.e. allocated via malloc()) then it doesn’t have a declared type. This makes it very difficult to perform type punning on any object with no declared type. We could copy via a temporary with the correct declared type:
r = ...;
float ftemp;
memcpy(&ftemp, &r, sizeof(int));
memcpy(fp, &ftemp, sizeof(int));
float f = *fp;
Seeing as we now copy from an object with a declared type of “float”, the effective type of “*fp” remains (or becomes) “float”. However, this is extremely clunky, and it requires us to know what the expected type of the object (if we have a “float *”, it seems reasonable to expect that the object it points to is a “float”, but what about if the original pointer is a “void *” or cannot otherwise reliably be assumed to point at a particular type?)
The whole “declared type” issue is also clouded by the existence aggregate types. If the destination object is a member object (i.e. has declared type) inside a dynamically allocated aggregate object (no declared type), what happens? (Consider especially the case of unions, or structures having a single member). Again the definition of “access” becomes important, and the text in the standard is insufficient.
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). Unresolved issues include:
- the proper definition of, and lifetime of, objects; In particular:
- Does a union member object exist when it is not the active member (i.e. not the last assigned-to member?) If it does, what is the effect of accessing it; does it have a specified value? Is behaviour defined if the object is modified?
- what is meant (in 6.5p7) when it refers to accessing the “stored value” of an object, in terms of how this contrasts with accessing the object itself.
- whether or not access to an object implies access to subobjects; and if so, what happens when the subobjects hold trap representations (i.e. what in this case is the significance of the requirement that structure/union objects have no trap representation)
- whether or not access to an object implies access to any containing objects; and if so, why such access is forbidden by 6.5p7
- If a value is copied (as per 6.5p7) using memcpy/memmove/character array, then what determines “the object from which the value is copied” if the region copied matches more than one object (such as a struct or union with a single member occupying the entire aggregate).
- Is it really intended that copying a value (as per 6.5p7) into an object with no declared type always changes the effective type of the object to that of the source object? (If so, this effectively precludes type punning in a dynamically allocated object).
I’d like to see these issues addressed in a future version of the standard.
