C99 revisited

[This is, essentially, a living document. I make continuous edits as I discover relevant snippets from the standard documents].

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 wrong, 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(). 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, and though it is not strictly conformant with C99 according to the current wording it is most likely intended to be part 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). 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 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 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:

  1. The type of “a” (let’s call it “struct A”) or
  2. The type of “b” (let’s call it “B”) or
  3. There are two accesses, one via the type of “a” and one via the type of “b”

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). 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”. (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?

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) – 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.

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.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 conflicts to some degree with Annex J.1.

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 smoking crack:

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.

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 pointer conversion is not defined.

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, I find I must reconsider my original position: that is, 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 to the pointer conversion not being defined if we attempt to produce a “T *” for a location where there is none.

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 has no effective type
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.

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; whether or not access to an object implies access to subobjects; and if so, what happens when the subobjects are trap representations.

About these ads

5 Responses to C99 revisited

  1. Hi! I’m the person who started the original thread on gcc@. I just found this blog entry when I googled for the thread to reference it.

    The thread you saw on gcc@ was continued in a private thread that included Clark Nelson from Intel, who is on the standards committee and is heavily involved in these particular portions of the standard. That conversation helped me better understand the intentions of these sections that had been so confounding to me.

    My best understanding about 6.5p7 is that it is not normative, in the sense of defining otherwise-undefined behavior. It does not change the meaning of any programs. Rather it describes the aliasing implications of the rest of the standard (in particular 6.3.2.3).

    So when it says “An object shall have its stored value accessed only by an lvalue expression that has one of
    the following types” (6.5p7), it does not mean “an object *may* have its stored valued accessed by *any* lvalue expression that has one of the following types.” It doesn’t allow you to create and use any aliases that follow these rules.

    Rather it is documenting that, as a matter of course, an object will only have its stored value accessed by an expression of one of the following types. In other words, it is a promise to the optimizer that only aliases that follow one of these rules can exist.

    • davmac says:

      Rather it is documenting that, as a matter of course, an object will only have its stored value accessed by an expression of one of the following types. In other words, it is a promise to the optimizer that only aliases that follow one of these rules can exist.

      Absolutely – I hadn’t interpreted it any other way.

    • davmac says:

      After some more thought and returning to this issue several times, I’ve now updated to the text to explain why 6.5p7 must in fact be normative.

  2. […] I still believe my example is well defined. If being a language lawyer is something you enjoy: C99 revisited | Software is Crap […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: