Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

I've been trying to get clarity on to what extent the position-independent data structure tricks in Gob (https://gist.github.com/pervognsen/c25a039fcf8c256141ef0778a1b32a88) are legal or illegal according to the C standard. I always had the impression it would run afoul of strict aliasing or pointer casting restrictions, but I've been digging into the standard, and now I'm no longer so sure. It might be perfectly legal after all?

Here's section 6.3.2.3 on pointer conversions from the C99 draft standard. I'll be referencing the C99 standard throughout this article, but I've verified that the C11 standard hasn't changed in the relevant areas.

"5 An integer may be converted to any pointer type. Except as previously specified, the result is implementation-defined, might not be correctly aligned, might not point to an entity of the referenced type, and might be a trap representation. [56]

6 Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type.

7 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 [57] 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.

[56] The mapping functions for converting a pointer to an integer or an integer to a pointer are intended to be consistent with the addressing structure of the execution environment.

[57] In general, the concept ‘‘correctly aligned’’ is transitive: if a pointer to type A is correctly aligned for a pointer to type B, which in turn is correctly aligned for a pointer to type C, then a pointer to type A is correctly aligned for a pointer to type C."

In my reading of these paragraphs, this grants an explicit license for most of the usual pointer arithmetic and type casting tricks as long as you stay within a single initial object, such as a char array that's been read from a file or returned by mmap. We have to be careful to avoid misalignment, but that cannot be a surprise to anyone. If you need to deal with misaligned objects, you have memcpy.

Aliasing shouldn't enter the picture with Gob because I'm not accessing the same object (e.g. a struct field) through different types. My fear was that casting positions within the char array to different types and accessing them would count as illegal aliases of the char array object, so let's see what the standard has to say about aliases.

Section 6.5 on expressions:

"6 The effective type of an object for an access to its stored value is the declared type of the object, if any. [73] If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. If a value is copied into an object having no declared type using memcpy or memmove, or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access.

7 An object shall have its stored value accessed only by an lvalue expression that has one of the following types: [74]

  • a type compatible with the effective type of the object,
  • a qualified version of a type compatible with the effective type of the object,
  • a type that is the signed or unsigned type corresponding to the effective type of the object,
  • a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object,
  • an aggregate or union type that includes one of the aforementioned types among its members (including, recursively, a member of a subaggregate or contained union), or
  • a character type.

[73] Allocated objects have no declared type.

[74] The intent of this list is to specify those circumstances in which an object may or may not be aliased."

This seems to allow Gob's use of pointer casts and indirections. The initial object is filled through the character type. We then access it subsequently via "a type compatible with the effective type of the object", indeed "For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access." It has no declared type because "allocated objects have no declared type" and paragraph 6 states that storing through a character type or with memcpy does not assign an effective type. If there is ever a store through another incompatible type, then "If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value," and so a subsequent read access through the original type would be an aliasing violation.

Some examples:

void *p = malloc(1024); // *p has no declared type
*(int *)p = 123;        // sets the effective type of *p to int
int i = *(int *)p;      // legal since the effective type of *p is now int
*(float *)p = 1.23f;    // sets the effective type of *p to float
float f = *(float *)p;  // legal since the effective type of *p is now float
int j = *(int *)p;      // illegal since the effective type of *p is float and int is not a compatible type

According to the first sentence of paragraph 6, this notion of a mutable "effective type" only comes into play for objects with no "declared type" since the effective type always equals the declared type, if there is one. So, this would be illegal:

int i = 123;
*(float *)&i = 1.23f; // illegal since i has an incompatible declared type (int)

And apparently only allocated objects have no declared type. So, as far as I can tell, a non-allocated char array could not legally be used in lieu of an object returned by malloc:

char buf[1024];
void *p = buf;
*(int *)p = 123; // illegal since *p has an incompatible declared type (char)

This last point is very surprising to me, if true. It would criminalize the universal idiom of suballocating out of char arrays that live on the stack or have static storage duration. Unlike other strict aliasing violations which have increasingly become real-world liabilities, I suspect violating this particular instance is going to remain safe in practice because of how widespread it is.

Micha Mettke points out that you can achieve the equivalent of the 123 assignment in the above snippet with a memcpy from an int i = 123 temporary according to section 6.2.6 on object representation. That is true (and you could do the same manually with a character type lvalue referencing object i, which is legal according to the last item of 6.5.7). But in an allocator, just like malloc itself, you want to be able to hand out a pointer that can be cast to any pointer type that can be written through and read back from, which requires working with arbitrarily typed lvalues. Doing everything character by character isn't possible since it would infect the whole program, not just the allocator code.

To summarize the relevance of all this to Gob: as long as the underlying Gob storage object has no declared type (e.g. returned by malloc or mmap) and is sufficiently aligned, the code should be legal as written, with no undefined or implementation defined behavior.

I'm trying to sort out my mental model for this part of the C standard once and for all, so if I made any conceptual mistakes or came to the wrong conclusions, please post a comment!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.