Hacker News Reader

Comment by drdexebtjl | Hacker News Reader

> It is awkward in C, where the implementation has to be macro-generated.

You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example.

The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separate metadata allocation.

The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.

View on HN

Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];).

But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.

There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.

> Accessing an array out of bounds is UB.

There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct.

I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.

> There is no OoB access of an array

Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds.

Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though.

> if the payload type has an alignment that's greater than the size of a pointer

The amount of padding is implementation-defined. The only portable guarantee is that 'payload' is aligned for its element type, char. To over-align, use _Alignas, as in:

    struct node {
        struct node *next;
        _Alignas(max_align_t) char payload[]; // Satisfies all fundamental alignment requirements
    };

> It does not matter that storage happens to be allocated beyond the end of said array.

It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.

> Strict aliasing

...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsigned chars.

> It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.

You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.

> memcpy takes a void pointer as its destination, sets the effective type of the storage behind it

And, in doing so, may very well overwrite the unspecified padding following 'payload' in the structure, thus instantly destroying the effective type of the structure object itself. Subsequent accesses to the structure or its members will be UB.

It seems to me that your argument hinges on two assumptions:

    - there is no padding following 'payload' (this would have to be statically asserted),
    - the pointer to 'payload' is indistinguishable from the pointer past the structure; in particular, provenance is not an issue.

That is a very interesting discussion.

If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic.

AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory.

If ISO C treats this as UB, shouldn’t ISO C be fixed?

No, you should fix your code to be compliant with ISO C. The optimizer isn’t going to wait for you to convince WG14.

I’m not chasing theoretical portability and checking off a box saying my code is 100% pure ISO C. If that’s important to you, don’t do this (and also don’t use pretty much any allocator!)

Every sufficiently useful C codebase assumes specific implementations.

> but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.

When you do "void *x = malloc(sizeof(struct node))", the returned storage doesn't have struct node object in it, it has an object of no effective type in it, with size "sizeof(struct node)". Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" — it takes a char pointer into the object storage, adds a number (less than the object's size) and so produces another char pointer that points somewhere inside into the object storage — and no, since there has been no actual referencing of the object's value, constructing such a pointer does not set the effective type of that object; and a char pointer is explicitly allowed to alias whatever storage. Then the memcpy sets the effective type, done. No UB anywhere.

> Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)"

It may differ, depending on the precise notion of provenance being applicable. If provenance only has allocation granularity, I suppose that there is no difference. I know that there were some discussions about provenance and subobjects. I do not know whether the question is resolved.

Where this gets complicated is that zero-sized arrays are non-standard. So even if we could build a convincing argument from standard notions of provenance, how would it transfer to a subobject that is excluded from the standard?

Last but not least, this is not only about creating the effective type through memcpy. The question is also whether this destroys the effective type of the structure. See my previous point about possible padding after 'payload'.

Please also consider that flexible array members are here for a reason. If I follow your argument, then they bring nothing that arrays of length 0 or 1 do not already cover.

In practice you wouldn’t have the payload in the struct at all, just a fixed offset aligned with the maximum alignment, but this is more illustrative of what’s happening for an example.

IIRC GCC and Clang lets character types alias to any type. Otherwise glibc’s malloc also doesn’t abide to strict aliasing.

> IIRC GCC and Clang lets character types alias to any type.

It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it does not have effective type T) is not.

> Otherwise glibc’s malloc also doesn’t abide to strict aliasing.

It may not have to. From the point of view of C, malloc is special because it is part of the implementation. The compiler is free to handle UB as it sees fit. In particular, it can decide that aliasing has different semantics in malloc.c than outside it.

I'm curious, what would be the point of having a zero-sized array if you can't access it?

Reply on news.ycombinator.com