Does C strict aliasing make untyped static memory pools impossible?

The rules on aliasing are specified in section 6.5p7 of the C standard:

An object shall have its stored value accessed only by an lvalue expression that has one of the following types: ⁸⁸⁾

• 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.

---

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

Note that this list allows any object to be accessed via a char *, but not the reverse, i.e. an object declared as an array of one or more characters can't be accessed as an lvalue of some other type.

This also means that malloc can't be implemented in a standard compliant way, since there's no way to create memory with no effective type without it. However malloc is considered part of the implementation and therefore can take of advantage of its knowledge of implementation internals to return a pointer to a block of memory that a compliant program can use.

The wording “Character arrays must not be reinterpreted as objects of other types” is imprecise. A correct statement is that if you reinterpret a character array as an object of another type (except as allowed by C 2018 6.5 7), the C standard does not define the behavior.

As always, if we want to accomplish a task, and the C standard does not define the behavior we want, we can look to other things to define the behavior we want.

If so, does it mean that an allocator that parcels out memory from a statically declared memory region is unimplementable in standard C?

Such an allocator is unimplementable in strictly conforming C, which is C code that does not rely on an unspecified, undefined, or implementation-defined behavior (and does not exceed any minimum implementation limit). It is entirely possible to write such an allocator in conforming C, which is C with extensions. Quite simply, one could put the memory allocation routines in one source file and compile them with a switch that supports aliasing memory as different types. (This is an extension, such as GCC’s -fno-strict-aliasing switch.) Then, when compiling other source files with common compilers, the compiler is blind to the effective type of the memory in the memory allocation source file, so it cannot be affected by the fact that the memory allocation routines use character arrays. (This is another extension, albeit the behavior arises implicitly from our understanding of how compilers and linkers are designed.)

WG14 member Jens Gustedt says in a blog post on strict aliasing rules:

Character arrays must not be reinterpreted as objects of other types.

Is that, in fact, true?

Sort of. The language specifications do not actually forbid such reinterpretation via pointer manipulation, but they do specify that accessing a character array or part of one as if it were an object of non-character type produces undefined behavior. If we take avoiding undefined behavior to be of paramount importance then Jens' "must not" follows.

However, "undefined behavior" means that the language specifications do not define the behavior, neither that of the access itself nor that of the entire program that exercises such an access. A program that performs such an access does not conform strictly to the language specifications, but its behavior might nevertheless be perfectly well defined when used with some particular C implementation, perhaps in combination with some other measure, such as specific compilation options. That same program might fail spectacularly -- or very subtly -- with a different C implementation, but that might not be a relevant consideration in some cases.

(I guess the corresponding language in the standard is the part saying that if an object has a declared type, than that type is its effective type.)

Yes.

If so, does it mean that an allocator that parcels out memory from a statically declared memory region is unimplementable in standard C?

As I take you to mean the question, yes. If you declare a large array of some type and hand out pointers (in)to that array, then undefined behavior arises from using those pointers to access regions of the array as if they had types inconsistent with the array's declared type, or where the pointer used for access is not correctly aligned for accessing members of the array as their declared type.

On the other hand, you can write such an allocator to manage access to a pool of a specific type of objects, such that the behavior of accessing allocated objects according to compatible types is well defined.

I hoped that if I ever found myself in a similar situation in (malloc-less) C, I could just declare a maximally aligned char array and keep using structs the usual way.

You might be able to do. That's a question of what your specific C implementation affords, above and beyond the language specifications.

I also fail to see what the point of _Alignas could possibly be in such a world, except as a standardized device for expressing non-standard requirements (similar to volatile).

I take you to be supposing that the role of _Alignas is to ensure correct alignment for pointer-based aliasing. Since such aliased access produces undefined behavior, why should one care about such alignment considerations?

Maybe one shouldn't. Certainly I find _Alignas rarely, if ever, to be of any genuine use in my own programming, and I generally write for hosted environments that, therefore, do provide malloc() and afford objects without declared types. But if you are relying on characteristics of your particular C implementation then you may find that _Alignas serves a useful purpose for you.

The Standard clearly allows implementations which are intended to be suitable for tasks requiring static memory pools to extend the semantics of the language to support them, and allows "conforming" (but not strictly conforming) programs to exploit such extensions. In fact, the vast majority of C implementations can be configured to support such tasks in mutually-compatible fashion. The Standard does not require that implementations or configurations which are not intended to be usable for such purposes support such constructs. Implementations which don't support the constructs necessary to accommodate static memory pools would, almost by definition, be unsuitable for tasks requiring static memory pools, but the Standard makes no attempt to require that all implementations be suitable for all purposes.

Consequently, when writing rules about type-based aliasing, the authors of the Standard did not exercise anything near the level of care that would have been appropriate if they intended such rules to serve as a boundary between programs that should be expected to work and programs that shouldn't. It may seem odd that C99 rules which have never been even remotely satisfactory, as evidenced by the confusion and controversy surrounding them for the last 20 years, have remained unchanged, but there's a simple reason for that: changing the rules would require reaching a consensus as to what they're supposed to say, and it would be impossible to write a single set of rules, suitable for all purposes, to distinguish between operations that should or should not be regarded as meaningful, since the question of whether an implementation should be expected to process a construct meaningfully depends upon the purposes for which it is designed and configured.

When the Standard characterizes an action as "undefined behavior", or as violating a constraint, it means nothing more nor less than that the Standard itself imposes no requirements about how implementations process code in the relevant situation. The Standard makes no attempt to distinguish actions which are clearly erroneous from those which may not be portable to every conceivable implementation but should be expected to behave identically on 99% of them. Nor does the Standard make much effort to consider all of the corner cases where an action which would generally invoke UB might (and perhaps should) be processed in the same meaningful way by all implementations.

Code which expects to do "weird" things with memory should be processed using configurations that make allowance for that, even if the code is strictly conforming. Handling all of the tricky corner cases in the rules as written would require foregoing optimizations that would often be useful, and both clang nor gcc will ignore such corner cases rather than forego the optimizations. The question of whether a piece of code will be processed meaningfully thus depends much more strongly on compiler configuration than upon whether the code jumps through all the hoops given in the Standard.

The Standard, at least as interpreted by clang and gcc in -fstrict-aliasing mode, does not allow for storage which has been used as one type to be reliably reused as a different type within its lifetime, regardless of where the storage came from, and even if such storage was originally obtained via malloc. The inability to reliably form untyped memory pools of static duration flows generally from the inability to have reliable memory pools of any duration.

According to paragraph 6 of N1570 6.5:

The effective type of an object for an access to its stored value is the declared type of the object, if any.87) 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.

Footnote 87 reads:

Footnote 87) Allocated objects have no declared type.

but it doesn't specify where or not there might be other cases where objects would have or not be regarded as having a declared type. Given something like:

extern int x;
extern int *alloc = malloc(sizeof (int));
extern int *unknownExternalFunction(int*p1, int *p2);
extern short s;

int *p = unknownExternalFunction(&x, alloc);
memcpy(p, &s, sizeof (short));

it would seem like *p should have a declared type in cases where unknownExternalFunction happens to return the first argument, but not in cases where it returns the second. Thus, the effective type of the storage at p should be int in the first scenario, but short in the second. From what I can tell, with the rules as written, a compiler would clearly be entitled to generate code that checks whether the returned address is coincidentally equal to x or p, and selects among versions of the downstream code optimized for scenarios where the memcpy does or doesn't alter the value. It turns out, though, that there's an even more interesting subtlety.

Although the notion of "modify" used elsewhere in the Standard indicates that even an action which writes an object with the value it already holds "modifies" it, the meaning here is different, and an object need not be regarded as modified by a sequence of actions that leave it holding the same bit pattern as it held before.

struct s { int x; };
struct t { int x; };
int test(void*p, void *q)
{
    struct s *ps = p;
    ps->x = 1;

    struct t *qt = q;
    qt->x = 2;

    struct t *pt = p;
    int temp = pt->x;
    // Start of sequence that writes to *p
    // but leaves bit pattern unchanged
    ps->x = 49;
    ps->x = temp;
    // End of sequence that writes to *p
    // but leaves bit pattern unchanged
    return ps->x;
}

If p and q identify the same storage with no declared type, the way clang and gcc interpret the -> operator, this code will set the effective type of the storage to struct s and then to struct t. It will then use type struct t to read the storage (perfectly legitimate). Although it will then use type s to write the storage twice, both clang and gcc will recognize that the two writes, taken together, leave the storage holding the same bit pattern as it held before the first write. Because the two writes, taken together, do not modify the storage, they do not alter the Effective Type of the storage, and behavior of the code would be undefined in the scenario where p and q are equal.