Is the "struct hack" technically undefined behavior?

Question

What I am asking about is the well known "last member of a struct has variable length" trick. It goes something like this:

struct T {
    int len;
    char s[1];
};

struct T *p = malloc(sizeof(struct T) + 100);
p->len = 100;
strcpy(p->s, "hello world");

Because of the way that the struct is laid out in memory, we are able to overlay the struct over a larger than necessary block and treat the last member as if it were larger than the 1 char specified.

So the question is: Is this technique technically undefined behavior?. I would expect that it is, but was curious what the standard says about this.

PS: I am aware of the C99 approach to this, I would like the answers to stick specifically to the version of the trick as listed above.

Answer 1

As the C FAQ says:

It's not clear if it's legal or portable, but it is rather popular.

and:

... an official interpretation has deemed that it is not strictly conforming with the C Standard, although it does seem to work under all known implementations. (Compilers which check array bounds carefully might issue warnings.)

The rationale behind the 'strictly conforming' bit is in the spec, section J.2 Undefined behavior, which includes in the list of undefined behavior:

• An array subscript is out of range, even if an object is apparently accessible with the given subscript (as in the lvalue expression a[1][7] given the declaration int a[4][5]) (6.5.6).

Paragraph 8 of Section 6.5.6 Additive operators has another mention that access beyond defined array bounds is undefined:

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

Answer 2

I believe that technically it's undefined behavior. The standard (arguably) doesn't address it directly, so it falls under the "or by the omission of any explicit definition of behavior." clause (§4/2 of C99, §3.16/2 of C89) that says it's undefined behavior.

The "arguably" above depends on the definition of the array subscripting operator. Specifically, it says: "A postfix expression followed by an expression in square brackets [] is a subscripted designation of an array object." (C89, §6.3.2.1/2).

You can argue that the "of an array object" is being violated here (since you're subscripting outside the defined range of the array object), in which case the behavior is (a tiny bit more) explicitly undefined, instead of just undefined courtesy of nothing quite defining it.

In theory, I can imagine a compiler that does array bounds checking and (for example) would abort the program when/if you attempted to use an out of range subscript. In fact, I don't know of such a thing existing, and given the popularity of this style of code, even if a compiler tried to enforce subscripts under some circumstances, it's hard to imagine that anybody would put up with its doing so in this situation.

Answer 3

Yes, it is undefined behavior.

C Language Defect Report #051 gives a definitive answer to this question:

The idiom, while common, is not strictly conforming

http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_051.html

In the C99 Rationale document the C Committee adds:

The validity of this construct has always been questionable. In the response to one Defect Report, the Committee decided that it was undefined behavior because the array p->items contains only one item, irrespective of whether the space exists.

Answer 4

That particular way of doing it is not explicitly defined in any C standard, but C99 does include the "struct hack" as part of the language. In C99, the last member of a struct may be a "flexible array member", declared as char foo[] (with whatever type you desire in place of char).

Answer 5

It is not undefined behavior, regardless of what anyone, official or otherwise, says, because it is defined by the standard. p->s, except when used as an lvalue, evaluates to a pointer identical to (char *)p + offsetof(struct T, s). In particular, this is a valid char pointer inside the malloc'd object, and there are 100 (or more, dependign on alignment considerations) successive addresses immediately following it which are also valid as char objects inside the allocated object. The fact that the pointer was derived by using -> instead of explicitly adding the offset to the pointer returned by malloc, cast to char *, is irrelevant.

Technically, p->s[0] is the single element of the char array inside the struct, the next few elements (e.g. p->s[1] through p->s[3]) are likely padding bytes inside the struct, which could be corrupted if you perform assignment to the struct as a whole but not if you merely access individual members, and the rest of the elements are additional space in the allocated object which you are free to use however you like, as long as you obey alignment requirements (and char has no alignment requirements).

If you are worried that the possibility of overlapping with padding bytes in the struct might somehow invoke nasal demons, you could avoid this by replacing the 1 in [1] with a value which ensures that there is no padding at the end of the struct. A simple but wasteful way to do this would be to make a struct with identical members except no array at the end, and use s[sizeof struct that_other_struct]; for the array. Then, p->s[i] is clearly defined as an element of the array in the struct for i<sizeof struct that_other_struct and as a char object at an address following the end of the struct for i>=sizeof struct that_other_struct.

Edit: Actually, in the above trick for getting the right size, you might also need to put a union containing every simple type before the array, to ensure that the array itself begins with maximal alignment rather than in the middle of some other element's padding. Again, I don't believe any of this is necessary, but I'm offering it up for the most paranoid of the language-lawyers out there.

Edit 2: The overlap with padding bytes is definitely not an issue, due to another part of the standard. C requires that if two structs agree in an initial subsequence of their elements, the common initial elements can be accessed via a pointer to either type. As a consequence, if a struct identical to struct T but with a larger final array were declared, the element s[0] would have to coincide with the element s[0] in struct T, and the presence of these additional elements could not affect or be affected by accessing common elements of the larger struct using a pointer to struct T.

Answer 6

Yes, it is technically undefined behavior.

Note, that there are at least three ways to implement the "struct hack":

(1) Declaring the trailing array with size 0 (the most "popular" way in legacy code). This is obviously UB, since the zero size array declarations are always illegal in C. Even if it does compile, the language makes no guarantees about the behavior of any constraint-violating code.

(2) Declaring the array with minimal legal size - 1 (your case). In this case any attempts to take pointer to p->s[0] and use it for pointer arithmetic that goes beyond p->s[1] is undefined behavior. For example, a debugging implementation is allowed to produce a special pointer with embedded range information, which will trap every time you attempt to create a pointer beyond p->s[1].

(3) Declaring the array with "very large" size like 10000, for example. The idea is that the declared size is supposed to be larger than anything you might need in actual practice. This method is free of UB with regard to array access range. However, in practice, of course, we will always allocate smaller amount of memory (only as much as really needed). I'm not sure about the legality of this, i.e. I wonder how legal it is to allocate less memory for the object than the declared size of the object (assuming we never access the "non-allocated" members).

Answer 7

The standard is quite clear that you cannot access things beside the end of an array. (and going via pointers does not help, as you are not allowed to even increment pointers past one after array end).

And for "working in practise". I've seen gcc/g++ optimizer using this part of the standard thus generating wrong code when meeting this invalid C.

Answer 8

If a compiler accepts something like

typedef struct {
  int len;
  char dat[];
};

I think it's pretty clear that it must be ready to accept a subscript on 'dat' beyond its length. On the other hand, if someone codes something like:

typedef struct {
  int whatever;
  char dat[1];
} MY_STRUCT;

and then later accesses somestruct->dat[x]; I would not think the compiler is under any obligation to use address-computation code which will work with large values of x. I think if one wanted to be really safe, the proper paradigm would be more like:

#define LARGEST_DAT_SIZE 0xF000
typedef struct {
  int whatever;
  char dat[LARGEST_DAT_SIZE];
} MY_STRUCT;

and then do a malloc of (sizeof(MYSTRUCT)-LARGEST_DAT_SIZE + desired_array_length) bytes (bearing in mind that if desired_array_length is larger than LARGEST_DAT_SIZE, the results may be undefined).

Incidentally, I think the decision to forbid zero-length arrays was an unfortunate one (some older dialects like Turbo C support it) since a zero-length array could be regarded as a sign that the compiler must generate code that will work with larger indices.