How reason about strict-aliasing for malloc-like functions

Question

AFAIK, there are three situations where aliasing is ok

1. Types that only differ by qualifier or sign can alias each other.
2. struct or union types can alias types contained inside them.
3. casting T* to char* is ok. (the opposite is not allowed)

These makes sense when reading simple examples from John Regehrs blog posts but I'm not sure how to reason about aliasing-correctness for larger examples, such as malloc-like memory arrangements.

I'm reading Per Vognsens re-implementation of Sean Barrets stretchy buffers. It uses a malloc-like schema where a buffer has associated metadata just before it.

typedef struct BufHdr {
    size_t len;
    size_t cap;
    char buf[];
} BufHdr;

The metadata is accessed by subtracting an offset from a pointer b:

#define buf__hdr(b) ((BufHdr *)((char *)(b) - offsetof(BufHdr, buf)))

Here's a somewhat simplified version of the original buf__grow function that extends the buffer and returns the buf as a void*.

void *buf__grow(const void *buf, size_t new_size) { 
     // ...  
     BufHdr *new_hdr;  // (1)
     if (buf) {
         new_hdr = xrealloc(buf__hdr(buf), new_size);
     } else {
         new_hdr = xmalloc(new_size);
         new_hdr->len = 0;
     }
     new_hdr->cap = new_cap;
     return new_hdr->buf;
}

Usage example (the buf__grow is hidden behind macros but here it's in the open for clarity):

int *ip = NULL;
ip = buf__grow(ip, 16);
ip = buf__grow(ip, 32);

After these calls, we have 32 + sizeof(BufHdr) bytes large memory area on the heap. We have ip pointing into that area and we have new_hdr and buf__hdr pointing into it at various points in the execution.

Questions

Is there a strict-aliasing violation here? AFAICT, ip and some variable of type BufHdr shouldn't be allowed to point to the same memory.

Or is it so that the fact that buf__hdr not creating an lvalue means it's not aliasing the same memory as ip? And the fact that new_hdr is contained within buf__grow where ip isn't "live" means that those aren't aliasing either?

If new_hdr were in global scope, would that change things?

Do the C compiler track the type of storage or only the types of variables? If there is storage, such as the memory area allocated in buf__grow that doesn't have any variable pointing to it, then what is the type of that storage? Are we free to reinterpret that storage as long as there is no variable associated with that memory?

Answer 1

The Standard does not define any means by which an lvalue of one type can be used to derive an lvalue of a second type that can be used to access the storage, unless the latter has a character type. Even something as basic as:

union foo { int x; float y;} u = {0};
u.x = 1;

invokes UB because it uses an lvalue of type int to access the storage associated with an object of type union foo and float. On the other hand, the authors of the Standard probably figured that since no compiler writer would be so obtuse as to use the lvalue-type rules as justification for not processing the above in useful fashion, there was no need to try to craft explicit rules mandating that they do so.

If a compiler guarantees not to "enforce" the rule except in cases where:

1. an object is modified during a particular execution of a function or loop;
2. lvalues of two or more different types are used to access storage during such execution; and
3. neither lvalue has been visibly and actively derived from the other within such execution

such a guarantee would be sufficient to allow a malloc() implementation that would be free of "aliasing"-related problems. While I suspect the authors of the Standard probably expected compiler writers to naturally uphold such a guarantee whether or not it was mandated, neither gcc nor clang will do so unless the -fno-strict-aliasing flag is used.

Unfortunately, when asked in Defect Report #028 to clarify what the C89 rules meant, the Committee responded by suggesting that an lvalue formed by dereferencing a pointer to a unions member will mostly behave like an lvalue formed directly with the member-access operator, except that actions which would invoke Implementation-Defined Behavior if done directly on a union member should invoke UB if done on a pointer. When writing C99, the Committee decided to "clarify" things by codifying that principle into C99's "Effective Type" rules, rather than recognizing any cases where an lvalue of a derived type may be used to access the parent object [an omission which the Effective Type rules do nothing to correct!].

Answer 2

Is there a strict-aliasing violation here? AFAICT, ip and some variable of type BufHdr shouldn't be allowed to point to the same memory.

What's important to remember is that a strict aliasing violation only occurs when you do a value access of a memory location, and the compiler believes that what's stored at that memory location is of a different type. So it is not so important to speak of the types of the pointers, as to speak of the effective type of whatever they point at.

An allocated chunk of memory has no declared type. What applies is C11 6.5/6:

The effective type of an object for an access to its stored value is the declared type of the object, if any. 87)

Where note 87 clarifies that allocated objects have no declared type. That is the case here, so we continue to read the definition of effective type:

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.

This means that as soon as we do an access to the chunk of allocated memory, the effective type of whatever is stored there, becomes the type of whatever we stored there.

The first time access happens in your case, is the lines new_hdr->len = 0; and new_hdr->cap = new_cap;, making the effective type of the data at those addresses size_t.

buf remains inaccessed, so that part of the memory does not yet have an effective type. You return new_hdr->buf and set an int* to point there.

---

The next thing that will happen, I assume is buf__hdr(ip). In that macro, the pointer is cast to (char *), then some pointer subtraction occurs:

(b) - offsetof(BufHdr, buf) // undefined behavior

Here we formally get undefined behavior, but for entirely different reasons than strict aliasing. b is not a pointer pointing to the same array as whatever is stored before b. The relevant part is the specification of the additive operators 6.5.6:

For subtraction, one of the following shall hold:
— both operands have arithmetic type;
— both operands are pointers to qualified or unqualified versions of compatible complete object types; or
— the left operand is a pointer to a complete object type and the right operand has integer type.

The first two clearly don't apply. In the third case, we don't point to a complete object type, as buf has not yet gotten an effective type. As I understand it, this means we have a constraint violation, I'm not entirely sure here. I am however very sure that the following is violated, 6.5.6/9:

When two pointers are subtracted, both shall point to elements of the same array object, or one past the last element of the array object; the result is the difference of the subscripts of the two array elements. The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined

So that's definitely a bug.

---

If we ignore that part, the actual access (BufHdr *) is fine, since BufHdr is a struct ("aggregate") containing the effective type of the object accessed (2x size_t). And here the memory of buf is accessed for the first time, getting the effective type char[] (flexible array member).

There is no strict aliasing violation unless you would after invoking the above macro go and access ip as an int.

---

If new_hdr were in global scope, would that change things?

No, the pointer type does not matter, only the effective type of the pointed-at object.

Do the C compiler track the type of storage or only the types of variables?

It needs to track the effective type of the object if it wishes to do optimizations like gcc, assuming strict aliasing violations never occur.

Are we free to reinterpret that storage as long as there is no variable associated with that memory?

Yes you can point at it with any kind of pointer - since it is allocated memory, it doesn't get an effective type until you do a value access.