Custom memory allocation is not possible in standard C

I’ve recently been perusing the C’11 standard final draft, mostly hoping to find some resolutions to the various inconsistencies and problems I’ve noted previously with the C99 standard (with no real success). In particular I read section 7.22.3 (C11; 7.20.3 in C99), which discusses the malloc family of functions:

The pointer returned if the allocation succeeds is suitably aligned so that it may be assigned to a pointer to any type of object and then used to access such an object or an array of such objects in the space allocated …
This little snippet is interesting because it hints at the intended usage of the methods. We call malloc (for instance), which returns a “void *”, and then we assign it to some other type of pointer and use that pointer to access the object that we allocated. What I begin to wonder about is how well this conversion of pointers is defined.
malloc returns a “void *”. When we assign a “void *” value to a pointer of another type, C99’s 6.5.16.1p2s says the value of the “void *” is “… converted to the type of the assignment expression and replaces the value stored in the object designated by …” the assignee. Fine; so what happens during the conversion? First, 6.3.2.3p1:
A pointer to void may be converted to or from a pointer to any incomplete or object type. A pointer to any incomplete or object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.
Note with care “the result shall compare equal to the original pointer”; 6.5.9p6 tells us what this means:
Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function …
(Plus a couple of other cases, to do with arrays). What’s interesting here is the stipulation that the pointers must compare equal, not that they are the same in other regards – a bit more on this later. What’s also particularly interesting is the notion that the situations for which pointers, after conversion, must compare equal and therefore point at the same object are quite limited. Other than 6.3.2.3p1 (as quoted earlier) we have only 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 for the pointed-to type, the behavior is undefined. Otherwise, when converted back again, the result shall compare equal to the original pointer. When a pointer to an object is converted to a pointer to a character type, the result points to the lowest addressed byte of the object. Successive increments of the result, up to the size of the object, yield pointers to the remaining bytes of the object.
It’s not even made explicit that conversion from a “T *” (for some type T) to “char *” results in a pointer which must compare equal to the original, i.e. it’s not perfectly clear that the “lowest addressed byte” of 6.3.2.3p7 is the same thing as a “subobject at its beginning” as per 6.5.9p6 (though this case it seems a reasonable assumption). What’s particularly interesting is that conversion from a “void *” to some “T *” is not particularly well-defined. All that we have is 6.3.2.3p1, which says that the conversion is permissible, and that if inverted the result will compare equal with the original pointer (No no no! It’s the other way around – converting from T* to void* and back will compare equal; from void* to T* and back need not). Take the following code for example:
int a = 5;      // 1
void *va = &a;  // 2
float *fa = va; // 3
void *vb = fa;  // 4
float *fb = vb; // 5
int *pa = vb;   // 6

Now answer the following questions, assuming that the alignment requirements for all involved types are met (except when answering the first question). Write down your answers:

1. Is it possible for line (3) to produce undefined behavior, if the alignment requirements for ‘float’ are more stringent than that for ‘int’? (assume that line 3 does not produce undefined behavior for the following questions).

2. Would (fa == va) necessarily be true immediately after (3)?

3. Would (vb == va) necessarily be true immediately after (4)?

4. Would (fb == fa) necessarily be true immediately after (5)?

5. Would (pa == &a) necessarily be true immediately after (6)?

Here are my own answers, with discussion:

1. No, because 6.3.2.3p1 allows conversion from a void pointer to any type of pointer. The conversion is not necessarily allowed in both directions, however. 6.3.2.3p7 does not come into play because a pointer to void is not a pointer to an object type.

Yes, I think, because 6.3.2.3p7 comes into play. This does open the question of what the purpose of 6.3.2.3p1 is, however, since it appears to be completely encompassed by 6.3.2.3p7. (One could perhaps be forgiven for thinking that 6.3.2.3p1 is trying to remove the alignment requirements in the case of conversion from the “void *” type).

2. No. Nowhere does it state that these pointers must compare equal.

3. No.  As per costeau’s comment below, the transition from void-pointer-to-object-pointer-to-void-pointer is not guaranteed to yield a pointer equal to the original.

Yes. We converted a “void *” (va) to a “float *” and back again, so by 6.3.2.3p1 (and p7)  the result must compare equal with the original. This shouldn’t be surprising.

4. Yes, by 6.3.2.3.p7 p1. Again, this shouldn’t be surprising.

5. No.This is the really disturbing result.Although va and vb must compare equal (and therefore point at the same object), no further requirements are placed on the similarity of their behavior. (actually there is no requirement that va and vb compare equal! I have really goofed this up). Thus, converting them both to “int *” might yield different pointer values which do not compare equal (and which do not point at the same object!). Putting it another way, although va and vb must compare equal (wrong…), they need not be the same value!

Edit: A much better example, because I got that so wrong before:

int a = 5;
void *ap = &a;
void *bp = &a;

Note that it is not necessarily true that ap == bp, but it is true that (int *)ap == (int *)bp.

More generally, take this example:

char *a = malloc(sizeof(int));
void *r = a;
float *f = r;

Note that there is no guarantee now that f addresses the same object as does a (and indeed, there’s no guarantee that r holds a pointer equal to the one that was returned by the call to malloc!). So, if we were able to obtain a pointer to a chunk of memory (i.e. an object) there’s actually no way we could use it, unless it happened to be the right pointer type to begin with.

I really, really, do not like the answer for 5, but I can’t find a way to come to the opposite conclusion based on the standard as worded. Note that in general, conversion from “void *” to another type of pointer – in fact, conversion of any “T *” to another pointer type other than “char *” – is not very well defined. Interestingly, the only thing in the standard that lets us use the result of the malloc() function is the documentation for malloc() itself (as quoted earlier). But creating a custom, general-purpose memory allocation (malloc-like facility) is just not possible. You simply can’t return a usable “void *” value unless you derived it from a pointer to the desired type in the first place. Am I missing something?

Advertisements

What “restrict” really means

I recently stumbled across a web page claiming to be “Demystifying The Restrict Keyword“, a claim which I consider dubious at best. Of the semantics of C99’s restrict, the page (written by a Mike Acton) says:

[when declaring a restrict-qualified pointer] I promise that the pointer declared along with the restrict qualifier is not aliased. I certify that writes through this pointer will not effect the values read through any other pointer available in the same context which is also declared as restricted.

Err, wrong. Firstly, a pointer declared with restrict is allowed to have aliases, it’s just that restrictions are placed on how those aliases are used or created. The C99 standard as always makes use of completely inaccessible language to describe the semantics of “restrict” – see 6.7.3.1, “Formal definition of restrict” – but in this case we can wade through the cruft and extract some actual meaning. The key point is that if a value pointed at by a restrict-qualified pointer is accessed through that pointer in any way, and is also modified through some pointer expression, then the latter pointer expression must be “based on” the restrict-qualified pointer. “Based on” means what it sounds like it means – essentially, that the value of the expression depends on the value of the pointer on which it is based. Here’s a counter-example to the restriction on aliasing expressed by Mike Acton above:

int * restrict p = ...;
int a = *p;   // here we have used 'p' for access
int * q = p;  // q aliases p
*q = 4;       // q is "based on" p, so this is allowed

The second part – “I certify that writes through this pointer will not effect the values read through any other pointer available in the same context which is also declared as restricted” – is also wrong (and not just grammatically). What restrict means is (and I’m simplifying just a little) that – if the restrict-qualified pointer is used to access an object, and the object is modified through any pointer, then the latter pointer and all other pointers (regardless of whether they are qualified with restrict or not) which are used to access the object will be “based on” the restrict-qualified pointer. Because we are allowed (with some restrictions) to assign the value of one restrict-qualified pointer to another, we can easily devise another counter-example to Mike Acton’s contract:

int * restrict p = ...;
{
    int * restrict q = p;  // q aliases p, both are restricted
    // Note that both q and p are "available in [this] context"
    *q = 4;  // this writes through q and affects the value read through p,
             // and yet is perfectly legal! (because q is based on p).
}
(*p);  // note the read through p must occur outside the block above, because
       // p is not based on q.

“restrict” does have some tricky semantics and it’s a shame that someone would “demystify” them so misleadingly. It could be a grave mistake to think that a non-restrict-qualified pointer can always safely alias a restrict-qualified pointer for instance.

It doesn’t quite stop there; the page goes on with a length example of using restrict to improve optimisation of a small function. The solution presented goes too far, assigning the address of each member of three different objects of the same structure type to different restrict-qualified pointers before performing calculations on them. This shouldn’t really be necessary; qualifying the structure pointers themselves with restrict should suffice, since the compiler should already know that different members of the same struct cannot legally alias (however, I’ve done some testing with gcc 4.6.3 and I’m not sure that this is the case with this compiler). Also, I’m fairly certain the solution invokes undefined behaviour via the odd and unnecessary pointer arithmetic involving a ‘stride’; A better version follows:

void
move( vector3* restrict velocity, 
      vector3* restrict position, 
      vector3* restrict acceleration, 
      float             time_step,  
      size_t            count)
{

  for (size_t i=0;i<count;i++)
  {
    float* restrict acceleration_x = &acceleration[i].x;
    float* restrict velocity_x     = &velocity[i].x;
    float* restrict position_x     = &position[i].x;
    float* restrict acceleration_y = &acceleration[i].y;
    float* restrict velocity_y     = &velocity[i].y;
    float* restrict position_y     = &position[i].y;
    float* restrict acceleration_z = &acceleration[i].z;
    float* restrict velocity_z     = &velocity[i].z;
    float* restrict position_z     = &position[i].z;
    
    const float ax  = *acceleration_x;
    const float ay  = *acceleration_y;
    const float az  = *acceleration_z;
    const float vx  = *velocity_x;
    const float vy  = *velocity_y;
    const float vz  = *velocity_z;
    const float px  = *position_x;
    const float py  = *position_y;
    const float pz  = *position_z;

    const float nvx = vx + ( ax * time_step );
    const float nvy = vy + ( ay * time_step );
    const float nvz = vz + ( az * time_step );
    const float npx = px + ( vx * time_step );
    const float npy = py + ( vy * time_step );
    const float npz = pz + ( vz * time_step );

    *velocity_x   = nvx;
    *velocity_y   = nvy;
    *velocity_z   = nvz;
    *position_x   = npx;
    *position_y   = npy;
    *position_z   = npz;
  }
}

From my tests this was by far the most performant (on a core-i7 based machine) with gcc (compilation options: -std=c99 -O3 -march=core2). When using the clang compiler, there wasn’t much variation in results between any version, including the naive version which didn’t use restrict at all (a slight performance benefit can be noticed when simply introducing restrict qualification into the parameter declarations, but no further benefit comes from using the code above, and only a negligible benefit comes from Mike Acton’s code which I believe invokes undefined behaviour anyway).

 

C99 and type-punning – making sense of a broken language specification

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:

  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”

Also, there’s the question of which object or objects are accessed. Is it:

  1. The object representing the “b” member of the aggregate or
  2. The aggregate object “a” or
  3. Both the aggregate object and the member object or
  4. 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.

GCC, strict aliasing, C99

Big fat note 28/02/10: A deeper analysis of the standard forced me to change my opinion on this particular topic after writing this blog entry. In other words, I was wrong (about several things) in this blog post. If you want info on C99 aliasing, Don’t read this post; read the other one instead.

I recently wrote about how Mysql was breaking the C99 strict aliasing rules. In a related topic, there’s an interesting discussion thread which recently started on the GCC developers mailing list. It started with a post by Joshua Haberman where he questions the interpretation of C99’s so-called strict aliasing rules in GCC. It’s an interesting point that he raised.

Essentially, the strict aliasing rules say that you must access memory (“object”) only by references (“lvalue expressions”) to compatible types, or by references to certain other types (such as character types). Joshua points out that one of the other types allowed is an aggregate or union type containing a member of the original type. On first examination this seems quite natural; if you alter a whole structure (or union) object then any pointer to one of its members should not have its value cached in a register (for instance). However, it has the implication that accessing a variable by first casting it to a structure or union is allowed, even though it is probably a rare case.

The ongoing discussion, though, is hilarious:

Richard Guenther, in the first reply, complains that Joshua is “literally interpreting” the standard. This is ridiculous – surely the standard is meant to be literally interpreted; that’s why it is written in such precise (and mind-numbingly verbose) language (but – keep reading).

Andrew Haley, in the next reply, insists (contrary to Richard) that GCC complies with the standard as worded and doesn’t even attempt to explain how Joshua (and Richard) might have gotten it wrong. He then repeatedly attempts to claim that Joshua’s understanding of the standard is incorrect, using irrelevant sections of the standard to try and prove this. After Erik Trulsson steps in to support Andrew, Andrew then has the gall to call Joshua stubborn! (Incidentally, Erik’s argument is irrelevant – because the standard does define what happens when you dereference a valid pointer, and the rules for pointer conversion in 6.2.3.2 at least suggest that pointer would be valid in the example, as long as alignment requirements were met).

[Update: the defect report mentioned in the next paragraph isn’t really so relevant; I managed to conflate two separate issues when writing this entry; see clarification in the comments below. My main point still stands].

The discussion continues on and a relevant defect report (for the standard) is mentioned. The standard committee seem to have come to the wrong conclusion on this defect; that is, they say that example 1 in the defect report invokes undefined behavior when reading the standard makes it very clear that this is not the case (they do acknowledge the need for a wording change). This would seem to mean that the committee actually thinks the standard is wrong. That’s fine except that… it’s a standard. I mean, you’ve put it out there; that’s then set. You can revise it later, but to turn around and say “oh no, we didn’t mean that, no, ignore the wording, you’ve got to follow the spirit…” is just ridiculous. The whole point of having a standard is to be perfectly clear, and lay these things out without any ambiguity.

To put the issue in layman terms, the standard – as it is worded – allows re-using allocated memory to contain different types. That is, you can allocate some memory using malloc(), store something in it, use it, and then when you’re done with it you can store something else (even with an incompatible type) and re-use the memory. The argument on the GCC discussion list is that this should not be allowed (and in fact, GCC currently optimizes as if it is not allowed) because it interferes with optimization. [not correct; GCC allows this, though the C99 committee seem to think it needn’t].

It’s true that the standard as written disallows certain useful optimizations. Unless the compiler can prove for certain that two pointers don’t alias, it has to assume that a read from one pointer cannot be moved past a write to another, even if the types are incompatible. So, the reordering of R(p)/W(q) to W(q)/R(p) would not be allowed – though the reverse would be. Also, it doesn’t prevent the compiler from caching the result of pointer reads in registers if the only intermediate writes are through incompatible types – so, it cannot be said that the aliasing rules are pointless, even as they are presently written.

What really gets me is that the committee (in their conclusion on the defect report) seem to agree with the GCC interpretation. To turn around now and say that every one who wrote a program based on the wording of the standard got it wrong is crazy, particularly when there is a clear reason why you might want to rely on the original wording (so you could re-use allocated memory).

(I mean sure; the standard might not say or imply what it was intended to. If so, fix it in a later standard – C1X; and to be fair to the committee, maybe that’s what they’re intending. But don’t re-write history. As a programmer I need to be able to rely on what the standard says at the time that I read it).

As far as I’m concerned, this really is a bug in GCC. I mean, it does not follow the standard as written. Following the intention of the standard authors is irrelevant.

fork/exec is forked up

I don’t know why it’s taken me so long to realise this, but the whole fork/exec shebang is screwed. There doesn’t seem to be any simple standards-conformant way (or even a generally portable way) to execute another process in parallel and be certain that the exec() call was successful. The problem is, once you’ve fork()d and then successfully exec()d you can’t communicate with the parent process to inform that the exec() was successful. If the exec() fails then you can communicate with the parent (via a signal for instance) but you can’t inform of success – the only way the parent can be sure of exec() success is to wait() for the child process to finish (and check that there is no failure indication) and that of course is not a parallel execution.

If you have a working vfork() then you can communicate with the parent process using a shared memory location (any variable declared “volatile” should do the trick, bearing in mind that “volatile” is not particularly well defined) although doing so is not standards conformant (see http://opengroup.org/onlinepubs/007908775/xsh/vfork.html for instance). By “working” vfork() I mean a vfork() which 1. causes the address space to be shared between the child and parent process (rather than copying the address space as fork() does) and 2. causes execution of the parent process to be suspended until the child either successfully exec()s or _exit()s. The 2nd requirement is necessary to avoid the race condition whereby the parent process checks the status variable before the child process has actually tried to exec() or similar.

Even the vfork() solution, if it can be used, is reliant on the compiler doing the right thing both in terms of volatile access, and in terms of vfork() generally. (Note that “right thing” in terms of volatile access is the generally accepted definition, not that in the C standard. Also, the fact that vfork()s correct operation really requires compiler support is something that I’m not willing to go into right now, other than to say that the compiler is allowed to make the assumption that “if (vfork()) { } else { }” will always follow one branch and not the other which is not the case here as both branches will be executed with the same address space).

The only other solution I can think of is to use pipe() to create a pipe, set the output end to be close-on-exec, then fork() (or vfork()), exec(), and write something (perhaps errno) to the pipe if the exec() fails (before calling _exit()). The parent process can read from the pipe and will get an immediate end-of-input if the exec() succeeds, or some data if the exec() failed. This seems like it should be fairly portable, as long as FD_CLOEXEC is available, but I haven’t actually tried it out yet.


Update 8/1/2009: The latter solution really requires fork() instead of vfork(), because vfork() might suspend the parent and the write by the child might then block, causing a deadlock. (In practice a pipe is always going to have enough of a buffer for this not to happen). POSIX doesn’t even let a vfork()d child call write(), anyway.

13/11/2015 also worth mentioning is the possibility for priority inversion to occur if the child process is to be run at lower priority and a third process is running at some priority level between the other two. The parent, which is running at the highest priority, should receive notification of fork-exec status as soon as possible; however, the child (running at the lowest priority) will not send this notification while the third process is scheduled.

This can avoided only by not waiting for exec to succeed or fail, but instead to process the exec status (data coming over the pipe or pipe closure) asynchronously (17/11/2015 or by eg using ptrace() to stop the child after exec() so that its priority can be set at that point; this wouldn’t work however if the child was setuid [unless the parent was root] since you can’t change the priority of a process not owned by yourself).


Update 18/9/2012: There’s a reasonably portable solution to this whole mess in the form of posix_spawn. (Update again 11/11/2015 – no. posix_spawn allows various errors to result in the child process exiting with a status of 127, so implementations may exhibit the exact same issue as the fork/exec combination. I somehow missed this earlier).


TL;DR – it’s not easy to determine immediately and without blocking whether a fork/exec pair of calls succeeded. If the child process is to run at the same or higher priority as the parent, you can do it with a CLOEXEC pipe trick; if the child process is to run at lower priority, the pipe trick suffers from potential priority inversion problems.

HTTP specification

In the HTTP spec it says:

3.3 use of multipart/form-data

The definition of multipart/form-data is included in section 7. A
boundary is selected that does not occur in any of the data. (This
selection is sometimes done probabilisticly.)

Probabilisticly? Who wrote this shit? If you choose a boundary probabilisticly then given enough usage you will almost definitely, at some point in time, pick a boundary which will occur naturally in the data (though one alternative, choosing a boundary deterministically after scanning through the data, is not too appealing either). This sort of thing just shouldn’t be allowed to happen (even if the probability is low) because it can easily be prevented. There are two perfectly suited techniques to avoid the problem that this could cause:

  1. Mandate a Content-length header in each part (which obviates the need for a boundary tag anyway) OR
  2. Use content transfer encoding (escaping) so that the boundary cannot possibly occur in the encoded content

Neither of these techniques would be particularly difficult to implement or costly in terms of processing time or bandwidth (considering that Content-length for the entire body will generally need to be calculated anyway). The first one seems to be allowed by current standards, but not recommended anywhere and certainly not mandated (and arguably, doesn’t really solve the problem unless the standards are updated to say that it does – since the boundary tag should arguably be recognized wherever it occurs, even if it is partway through a body part according to that body part’s known content length). The second one has the problem that the only defined encoding which would be suitable is base64, and that incurs a 33% bandwidth overhead.

It’s really annoying that this sort of stupid blunder can make it into a standard which is so widely used. At least it seems it can’t lead to any security vulnerabilities (I think) but I pity the poor sucker whose file-upload-via-POST is failing due to a shoddy standard which says it’s ok that a boundary tag could possibly occur within the content.

ISO C99

I’m not sure when it happened but it looks like the C99 standard is now publicly available (for free download) in PDF form. Make sure to get the version which incorporates corrections TC1 and TC2. From the standard:

6.2.6.1 General – Representation of types

paragraph 3:

“Values stored in unsigned bit-fields and objects of type unsigned char shall be represented by a pure binary notation”.

A footnote tells us that a “pure binary notation” is:

“A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral powers of 2, except perhaps the bit with the highest position. … A byte contains CHAR_BIT bits, and the values of type unsigned char range from 0 to (2^CHAR_BIT) – 1.”

What the… ??

Let’s go through that footnote bit by bit, no pun intended:

A positional representation for integers that uses the binary digits 0 and 1 … ok, that’s fairly straightforward

… in which the values represented by successive bits are additive … I guess that means that to get the value as a whole, you add the values represented by the bits. Just like you do in any binary number. Although, this is a fairly retarded way of saying it.

… begin with 1… Does this mean that the first bit position has a value of 1? Or that the value for any bit position is one before it is multiplied by some power of 2? The latter is mathematically redundant so I guess it must be the former. Ok.

… and are multiplied by successive integral powers of 2 … Yes, ok, each bit is worth its face value (0 or 1) multiplied by “successive powers of two”, the begin with 1 beforehand means that 1 is the first power of 2 (it is 2^0), then next would be 2 (2^1) then 4, 8, 16 and so on. Again there must be a better way to say this.

… except perhaps the bit with the highest position. WTF!!?? So the highest bit position can be worth something completely different. This might make sense for representation of signed values in 2’s complement, but this was specifically referencing an unsigned type. Also:

A byte contains CHAR_BIT bits, and the values of type unsigned char range from 0 to (2^CHAR_BIT) – 1.

Do the math. If there are CHAR_BIT bits, the highest bit position is (CHAR_BIT – 1) if we number them starting from 0. Each bit except for that one is worth 2^position and the range we can represent using those bits as well as the highest bit is 2^CHAR_BIT – 1. What then must the highest bit position be worth? Why then specifically exclude it from this requirement?