4

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?

Daniel Näslund
  • 2,300
  • 3
  • 22
  • 27
  • 1
    You need to look up effective type rules in §6.5 p6-7 (here's probably existing answer about this already). Objects created with dynamic memory allocation are treated slightly differently as they don't have declared type. – user694733 Mar 15 '18 at 12:12
  • An allocated object has no declared type, so the effective type is the type of the first access to the allocated memory. Since `buf` is never accessed, but is only used to calculate addresses, there's no object of type `char` there. Still it would be somewhat cleaner to not ever declare `buf` as a member, but simply use `new_hdr+1` as the starting address. (This is about C rules, C++ ones may be different). – n. m. could be an AI Mar 15 '18 at 12:17
  • @n.m. Which is why, OP should specify the language that he is really using or interested in. Either C or C++. – machine_1 Mar 15 '18 at 12:20
  • 1
    @machine_1 I've removed the C++ tag. C is complicated enough :) – Daniel Näslund Mar 15 '18 at 12:23
  • 1
    It turned out that the main issue here was not strict aliasing, but incorrect pointer arithmetic. So this is not a duplicate of whatever questions regarding effective type we already have on SO. Don't be so hasty to down vote questions without reading them carefully. – Lundin Mar 15 '18 at 12:48
  • An insufficient alignment for `buf` might be a problem. `malloc()` like functions are expected to return a max-aligned object and `buf` should be a such one. – ensc Mar 15 '18 at 13:18
  • @ensc What do you mean "insufficient alignment"? The compiler will ensure that all struct members are aligned. A struct may have trailing padding between the flexible array member and the member before it. This isn't the "struct hack" from C90. – Lundin Mar 15 '18 at 13:57
  • @Lundin I think ensc is referring to the fact that `buf` is declared `char[]`, but `ip` where it is assigned, is `int*`. – user694733 Mar 15 '18 at 13:59
  • @user694733 Again, the type of `ip` is completely irrelevant, as there is no lvalue access with type `int*` anywhere. You can declare `ip` as `bananas_t` and it wouldn't matter. – Lundin Mar 15 '18 at 14:04
  • @Lundin Don't mix this with our discussion in topic on your answer. If we'd have `struct X {char a; char b[]}`, then `struct X* x = malloc(sizeof(struxt X) + sizeof(int)); int * ip = (int*)x->b`, might not generate correctly aligned pointer to `int`, because there might not be necessary padding between `x->a` and `x->b`. – user694733 Mar 15 '18 at 14:16
  • @user694733 Ok I see what you mean. Though regardless of alignment, that code would also give a strict aliasing violation, if the contents were accessed as `int`. – Lundin Mar 15 '18 at 14:37
  • @Lundin assuming `bananas_t` requires a 128 bit alignment; `malloc()` like functions are expected to return memory with at least such an alignment. But `buf[]` within the object might be only 64 bit aligned (when e.g. `size_t` is 32 bit) and because the object itself is at least 128 bit aligned (allocated by `malloc()`), `buf[]` is misaligned. – ensc Mar 15 '18 at 15:43

2 Answers2

1

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.

Lundin
  • 195,001
  • 40
  • 254
  • 396
  • You write "And here the memory of `buf` is accessed for the first time, getting the effective type `char[]`. But in there I don't see any stores to buf. So the `buf`effective type should remain undecided I guess. Until we store an int into it as is done in https://github.com/pervognsen/bitwise/blob/master/ion/ion.c#L56. Given that, I'd say the first access to the memory pointed to by buf will be an `int` write. Under those circumstances are we still obeying the srict-aliasing rules? – Daniel Näslund Mar 15 '18 at 13:06
  • 1
    There is not subtracted from `buf`, but from `buf` casted to `(char *)`. This should is a "pointer to a complete type" and operation is valid, isn't it? – ensc Mar 15 '18 at 13:22
  • @DanielNäslund It isn't clear how the macro is used, but I assume there will be a read access which returns a `BufHdr*` to the code invoking the macro. You are correct that this isn't a store access, so what applies is the last part of the _effective type_ definition: `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.` In this case `BufHdr`. – Lundin Mar 15 '18 at 13:50
  • @ensc It's a question about if an object with no type is to be regarded as having incomplete type or not. But that part really doesn't matter, since you simply can't do pointer arithmetic out of bounds of the array. Whoever wrote the code might have confused the rule in 6.3.2.3, which does not apply here: "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." – Lundin Mar 15 '18 at 13:51
  • 1
    Notably, `(uintptr_t)(b) - offsetof(BufHdr, buf)` would have been well-defined. After which an implementation-defined conversion back to pointer type can happen. But it wouldn't be UB. – Lundin Mar 15 '18 at 13:53
  • *"b is not a pointer pointing to the same array as whatever is stored before b"* I don't think this is true. `b` is value of `ip`, which in turn is calculated from original object which is created with `xmalloc`. Assuming there are no implementation defined issues at pointer conversion, rule 6.5.6/9 is not violated. There is no out of array bounds access, because we are accessing the complete object with `char*` pointer. – user694733 Mar 15 '18 at 13:57
  • @user694733 The variable `ip` is completely irrelevant here. What matters is only the effective type of the objects involved. What's stored before `b` is not an array, but a `size_t` member, and there may be any padding present too. As I said in a previous comment, the exception from 6.3.2.3 does not apply to subtraction. We are not doing "successive increments", but an absolute address decrement, out of bounds where no arrays are allocated. This part is very clear, really. – Lundin Mar 15 '18 at 14:01
  • I agree. `ip` doesn't affect it. But rules from 6.5.6 affect here too. We can traverse *back* and forth within array created with `xmalloc(new_size);`. It doesn't matter whether pointer we use to do this is derived from `(char*)new_hdr->buf` or `(char*)new_hdr + offsetof(BufHdr, buf)` as they both must result in identical pointer. – user694733 Mar 15 '18 at 14:29
  • @user694733 `(char*)new_hdr->buf` gives the lowest address of the array. In the answer I assume that the macro is called as `buf__hdr(ip)` because otherwise the macro doesn't make any sense. And if you take `(char *)(b) - whatever`, it is the very same thing as writing `&array[0] - whatever`. – Lundin Mar 15 '18 at 14:40
  • 1
    @user694733: When the language was designed, it didn't matter whether a pointer identified a byte within an inner array or a byte within an outer object, since address computations would work identically on both. I don't think anything in the Standard makes clear what, if anything, must be done to convert a `char*` that identifies an element of an inner array into a `char*` that can be indexed throughout the enclosing object. – supercat Apr 23 '18 at 21:28
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!].

supercat
  • 77,689
  • 9
  • 166
  • 211
  • Is this really so? That you can't write a your own allocator and have it free of strict-aliasing problems? That just sounds hard to believe. I saw that you had the same conclusion in https://stackoverflow.com/questions/31534716/malloc-free-malloc-and-strict-aliasing#comment65446143_31535153. Aren't there any ways around that? Surely compiler folks knows that custom allocators exists a'plenty? – Daniel Näslund Apr 24 '18 at 10:34
  • @DanielNäslund: The rules in N1570 6.5p7 don't even require that compilers support the use of `aggregate.member` or `aggregatePtr->member` to access non-character members, but the authors presumably expected that compilers would support obvious cases anyway. As I note above, it's possible to write one's own allocator without aliasing problems if a compiler declines to enforce the rule except as indicated above. If code frees a pointer to a `thing1`, an allocator will likely convert it into a pointer to an allocator's internal data structure and never use it as a... – supercat Apr 24 '18 at 14:42
  • ...`thing1` again unless it is re-converted. Then if something asks for that block and converts it to a `thing2*`, no storage that will be accessed with that type will be re-used as the allocator's storage type unless or until that pointer gets passed back to the allocator and converted yet again. Unfortunately, both gcc and clang pay ignore the timing of pointer conversions in deciding whether an access to a `thing1` can be re-ordered relative to an access to a `thing2`. Using `-fno-strict-aliasing` to block re-ordering will make the compilers usable, but negates optimization benefits. – supercat Apr 24 '18 at 14:46
  • @DanielNäslund: BTW, even on a "nice" compiler, one might still have to ensure that the pointer that's returned from an allocation request is either derived from one which was previously freed, or else that a pointer which is freed gets stored someplace "volatile" and a pointer that gets returned by an allocation request gets read from someplace "volatile". The Standard wouldn't require that the latter approach would work (but as noted it fails to allow things that obviously should work), but a decent compiler should recognize that if it sees a pointer to an object stored somewhere volatile... – supercat Apr 24 '18 at 15:30
  • ...any pointer which is subsequently read from a volatile location should be regarded as potentially derived from it. – supercat Apr 24 '18 at 15:34