Detecting array flattening trick with gcc

Question

Some code flattens multidimensional arrays like this:

int array[10][10];
int* flattened_array = (int*)array;
for (int i = 0; i < 10*10; ++i)
   flattened_array[i] = 42;

This is, as far as I know, undefined behaviour.

I am trying to detect cases like this with gcc sanitizers, however, neither -fsanitize=address nor -fsanitize=undefined work.

Is there a sanitizer option that I'm missing, or perhaps a different way to detect this at run time? Or maybe I am mistaken and the code is legal?

Edit: the sanitizers detect this access as an error:

array[0][11] = 42;

but do not detect this:

int* first_element = array[0];
first_element[11] = 42;

Furthermore, clang detects the first access statically, and gives out a warning

warning: array index 11 is past the end of the array (which contains 10 elements) [-Warray-bounds]

Edit: the above does not change if int in the declaration is replaced with char.

Edit: There are two potential sources of UB.

1. Accessing an object (of type int[10]) through an lvalue of an incompatible type (int).
2. Out-of-bounds access with a pointer of type int* and an index >=10 where the size of the underlying array is 10 (rather than 100).

Sanitizers don't seem to detect the first kind of violation. There's a debate whether this is a violation at all. After all, there's also an object of type int at the same address.

As for the second potential UB, the UB sanitizer does detect such access, but only if it is done directly via the 2D array itself and not via another variable that points to its first element, as shown above. I don't think the two accesses should differ in legality. They should be either both legal (and then ubsan has a false positive) or both illegal (and then ubsan has a false negative).

Edit: Appendix J2 says array[0][11] should be UB, even though it is only informative.

Answer 1

From a language lawyer point of view, this is generally seen as invalid code because the integers arrays are only of size 10 and the code does access past the declared array size. Yet it used to be a common idiom, and I know no compiler that would not accept it. Still with all real world compilers I know, the resulting program will have the expected behaviour.

After a second (in reality much more) reading of the C11 standard draft (n1570) the intent of the standard is still not clear. 6.2.5 Types § 20 says:

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type.

It makes clear that an array contains contiguously allocated objects. But IMHO is unclear about whether a contiguously allocated set of objects is an array.

If you answer no, then the shown code does invoke UB by accessing an array past it last element

But if you answer yes, then a set of 10 contiguous sets of 10 contiguous integers gives 100 contiguous integers and can be seen as an array of 100 integers. Then the shown code would be legal.

That latter acception seems to be common in the real word because it is consistent with dynamic array allocation: you allocate enough memory for a number of objects, and you can access that as if it had been declared as an array - and the allocation function ensures no alignment problem.

My conclusion so far is:

• is it nice and clean code: certainly not and I would avoid it in production code
• does it invokes UB: I really do not know and my personal opinion is probably no

---

Let us look at the code added in the edit:

array[0][11] = 42;

The compiler knows that array is declared as int[10][10]. So it knows that both indexes must be less than 10, and it can raise a warning.

int* first_element = array[0];
first_element[11] = 42;

first_element is declared as a mere pointer. Statically, the compiler has to assume that it can point inside an array of unknown size, so outside of a specific context, it is much harder to raise a warning. Of course for a human programmer it is evident that both way should be seen the same, but as a compiler is not required to emit any diagnostic for out of bounds array, efforts to detect them are left to the minimum and only trivial cases are detected.

In addition, when a compiler internally codes pointer arithmetics on common platforms, it just computes a memory address which is the original address and a byte offset. So it could emit the same code as:

char *addr = (char *) first_element;  // (1)
addr += 11 * sizeof(int);             // (2)
*((int *) addr) = 42;                 // (3)

(1) is legal because a pointer to any objet (here an int) can be converter to a pointer to char, which is required to point to the first byte of the representation of the object

(2) the trick here is that (char *) first_element is the same as (char *) array because the first byte of the 10*10 array is the first byte of the first int of the first row, and an single byte can only have one single address. As the size of array is 10 * 10 * sizeof(int), 11 * sizeof(int) is a valid offset in it.

(3) for the very same reason, (char *) &array[1][1] is addr because elements in an array are contiguous so their byte representation are also contiguous. And as a forth and back conversion between 2 types is legal and required to give back the original pointer, (int *) addr is (int*) ((char*) &array[1][1]). That means that dereferencing (int *) addr is legal and shall have the same effect as array[1][1] = 42.

This does not mean that first_element[11] does not involve UB. array[0] has a declared size which is 10. It just explains why all known compilers accepts it (in addition to not wanting to break legacy code).

Answer 2

The sanitizers are not especially good at catching out-of-bounds access unless the array in question is a complete object.

For example, they do not catch out-of-bounds access in this case:

struct {
   int inner[10];
   char tail[sizeof(int)];
} outer;

int* p = outer.inner;
p[10] = 42;

which is clearly illegal. But they do catch access to p[11].

Array flattening is not really different in spirit from this kind of access. Code generated by the compiler, and the way it is instrumented by sanitizers, should be pretty similar. So there's little hope that array flattening can be detected by these tools.

Answer 3

Multidimensional arrays are required to be contiguously allocated (C uses row-major). And there can't be any padding between elements of an array - though not stated explicitly in the standard, this can be inferred with array definition that says "contiguously allocated nonempty set of objects" and the definition of sizeof operator.

So the "flattening" should be legal.

---

Re. accessing array[0][11]: although, Annex J2 directly gives an example, what exactly is the violation in the normative isn't obvious. Nevertheless, it's still possible to make it legal an intermediate cast to char*:

*((int*)((char*)array + 11 * sizeof(int))) = 42;

(writing such code is obviously not advised ;)

Answer 4

The problem here is that there Standard describes as equivalent two operations, one of which clearly should be defined and one of which the Standard expressly says is not defined.

The cleanest way to resolve this, which seems to coincide with what clang and gcc already do, which is to say that applying [] operator to an array lvalue or non-l value does not cause it to decay, but instead looks up an element directly, yielding an lvalue if the array operand was an lvalue, and a non-l value otherwise.

Recognizing the use of [] with an array as being a distinct operator would clean up a number of corner cases in the semantics, including accessing an array within a structure returned by a function, register-qualified arrays, arrays of bitfields, etc. It would also make clear what the inner-array-subscript limitations are supposed to mean. Given foo[x][y], a compiler would be entitled to assume that y would be within the bounds of the inner array, but given *(foo[x]+y) it would not be entitled to make such an assumption.