C/C++: Is This Undefined Behavior? (2D Arrays)

C/C++: Is this undefined behavior? (2D arrays)

Accessing elements of a multidimensional array from a pointer to the first element is Undefined Behavior (UB) for the elements that are not part of the first array.

Given T array[n], array[i] is a straight trip to UB-land for all i >= n. Even when T is U[m]. Even if it's through a pointer. It's true there are strong requirements on arrays (e.g. sizeof(int[N]) == N*sizeof(int)), as mentioned by others, but no exception is explicitly made so nothing can be done about it.

I don't have an official reference because as far as I can tell the C++ standard leaves the details to the C89 standard and I'm not familiar with either the C89 or C99 standard. Instead I have a reference to the comp.lang.c FAQ:

[...] according to an official interpretation, the behavior of accessing (&array[0][0])[x] is not defined for x >= NCOLUMNS.

2D Array indexing - undefined behavior?

It's undefined behavior, and here's why.

Multidimensional array access can be broken down into a series of single-dimensional array accesses. In other words, the expression a[i][j] can be thought of as (a[i])[j]. Quoting C11 §6.5.2.1/2:

The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

This means the above is identical to *(*(a + i) + j). Following C11 §6.5.6/8 regarding addition of an integer and pointer (emphasis mine):

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.

In other words, if a[i] is not a valid index, the behavior is immediately undefined, even if "intuitively" a[i][j] seems in-bounds.

So, in the first case, a[0] is valid, but the following [20] is not, because the type of a[0] is int[5]. Therefore, index 20 is out of bounds.

In the second case, a[-1] is already out-of-bounds, thus already UB.

In the last case, however, the expression a[5] points to one past the last element of the array, which is valid as per §6.5.6/8:

... if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object ...

However, later in that same paragraph:

If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.

So, while a[5] is a valid pointer, dereferencing it will cause undefined behavior, which is caused by the final [-3] indexing (which, is also out-of-bounds, therefore UB).

Is accessing an element of a multidimensional array out of bounds undefined behavior?

According to the standard, it is clearly undefined behaviour as such a case is explicitly listed in the section J.2 undefined behaviour (found in an online C99 standard draft):

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

It can still be the case that your example will work, and actually I have seen a lot of such cases in C code; However, to be accurate, it is UB.

Realloc produces undefined behavior in C when used with a 2d array

There is definitely a sizing problem in your initial allocation:

field_pointer = (field *)malloc(sizeof(field *)) should allocate the size of a structure, not that of a pointer. Use field_pointer = malloc(sizeof(field)) or better:

    field_pointer = malloc(sizeof(*field_pointer));

Note that you could simplify the code by using a real 2D array instead of a pointer to an array of pointers to arrays of 2 int.

Also note that there is no need to manipulate the global object until it is fully loaded. Using local variables is recommended. Returning the structure pointer allows for the caller to detect failure to load the maze. It should be the caller responsibility to store the pointer to the global variable is needed.

Here is a modified version:

#include <stdio.h>
#include <stdlib.h>

typedef struct field {
    int x, y, free_spaces;
    int (*empty_coords)[2];
    int S[2];
    int E[2];
} field;

field *field_pointer;

/* Enumerates the whole field by saving the coordinates of the free pieces and the dimensions */
field *enum_field(const char *filename) {
    FILE *maze = fopen(filename, "r");
    if (maze == NULL)
        return NULL;
    field *fp = calloc(sizeof(*fp), 1);
    if (fp == NULL) {
        fclose(maze);
        return NULL;
    }
    fp->free_spaces = 0;
    fp->empty_coords = NULL;
    int i = 0, j = 0, chr;

    while ((chr = fgetc(maze)) != EOF) {
        if (chr == '\n') {
            if (fp->x < i)
                fp->x = i;
            i = 0;
            j++;
        } else {
            if (chr != '#') {
                // allocate space for one extra set of coordinates
                int (*new_coords)[2] = realloc(fp->empty_coords,
                                               (fp->free_spaces + 1) * sizeof(*fp->empty_coords));
                if (!new_coords) {
                    free(fp->empty_coords);
                    free(fp);
                    fclose(maze);
                    return NULL;
                }
                fp = new_coords;
                fp->empty_coords[fp->free_spaces][0] = i;
                fp->empty_coords[fp->free_spaces][1] = j;
                fp->free_spaces++;

                if (chr == 'E') {
                    fp->E[0] = i;
                    fp->E[1] = j;
                } else
                if (chr == 'S') {
                    fp->S[0] = i;
                    fp->S[1] = j;
                }
            }
            i++;
        }
    }
    fp->y = j;
    fclose(maze);
    // return structure pointer for the caller to store to into field_pointer
    return fp;
}

Undefined behavior with 2d array of struct C

This is what it looks like you're trying to do. You will need to scan your csv file and compute the number of rows required, then populate the values however you want.

#include <stdio.h>
#include <stdlib.h>

struct node {
  char* value;
};

int main() {
  const int rows = 3; // you will need to compute this beforehand
  const int columns = 35;

  struct node** arrayofnodes = malloc(rows * sizeof(struct node*));

  for (int i = 0; i < rows; ++i) {
    arrayofnodes[i] = malloc(columns * sizeof(struct node));
  }

  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      arrayofnodes[i][j].value = malloc(...);
      strcpy(arrayofnodes[i][j].value, ...); // etc..
    }
  }

  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      free(arrayofnodes[i][j].value);
    }
  }

  for (int i = 0; i < rows; ++i) {
    free(arrayofnodes[i]);
  }

  free(arrayofnodes);
}

Is it undefined behavior to access the inner array out of bounds on a 2d array in c

In C, what you're doing is undefined behavior.

The expression arr[0] has type int [5]. So the expression arr[0][5] dereferences one element past the end of the array arr[0], and dereferencing past the end of an array is undefined behavior.

Section 6.5.2.1p2 of the C standard regarding Array Subscripting states:

The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

And section 6.5.6p8 of the C standard regarding Additive Operators states:

When an expression that has integer type is added to or
subtracted from a pointer, the result has the type of the pointer
operand. If the pointer operand points to an element of an array
object, and the array is large enough, the result points to an element
offset from the original element such that the difference of the
subscripts of the resulting and original array elements equals the
integer expression. In other words, if the expression P points to
the i-th element of an array object, the expressions (P)+N
(equivalently,N+(P)) and (P)-N (where N has the value n)
point to, respectively, the i+n-th and i−n -th elements of the
array object, provided they exist. Moreover, if the
expression P points to the last element of an array object, the
expression (P)+1 points one past the last element of the array
object, and if the expression Q points one past the last
element of an array object,the expression (Q)-1 points to the
last element of the array object. 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.
If the result points one past the last element of the array object, it
shall not be used as the operand of a unary * operator that is
evaluated.

The part in bold specifies that the addition implicit in an array subscript may not result in a pointer more that one element past the end of an array, and that a pointer to one element past the end of an array may not be defererenced.

The fact that the array in question is itself a member of an array, meaning the elements of each subarray are continuous in memory, doesn't change this. Aggressive optimization settings in the compiler may note that it is undefined behavior to access past the end of the array and make optimizations based on this fact.

Is copying 2D arrays with memcpy technically undefined behaviour?

It's well-defined, even if you use memcpy(arr_cpy, arr, size) rather than

memcpy(&arr_cpy, &arr, size) (which @LanguageLawyer has finally explained is what they've been arguing for the whole time), for reasons explained by @HolyBlackCat and others.

The intended meaning of the standard is clear, and any language to the contrary is a defect in the standard, not something compiler devs are going to use to pull the rug out from under countless normal uses of memcpy (including 1D arrays) that don't cast int* to int (*)[N], especially since ISO C++ doesn't allow variable-length arrays.

Experimental evidence for how compiler-developers chose to interpret the standard as letting memcpy read from the whole outer object (array-of-array-of-int) which is pointed-to by the void* arg, even if that void* was obtained as a pointer to the first element (i.e. to the first array-of-int):

If you pass a size that's too large, you do get a warning, and for GCC the warning even spells out exactly what object and what size it sees being memcpyed:

#include <cstring>

int dst[2][2];
void foo(){
    int arr[2][2] = {{1,1},{1,1}};
    std::memcpy(dst, arr, sizeof(arr));  // compiles cleanly
}

void size_too_large(){
    int arr[2][2] = {{1,1},{1,1}};
    std::memcpy(dst, arr, sizeof(arr)+4);
}

Using &dst, &src makes no difference here to warnings or lack thereof.

Godbolt compiler explorer for GCC and clang -O2 -Wall -Wextra -pedantic -fsanitize=undefined, and MSVC -Wall.

GCC's warning for size_too_large() is:

warning: 'void* memcpy(void*, const void*, size_t)' forming offset [16, 19] is  \
  out of the bounds [0, 16] of object 'dst' with type 'int [2][2]' [-Warray-bounds]
   11 |     std::memcpy(dst, arr, sizeof(arr)+4);
      |     ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
<source>:3:5: note: 'dst' declared here
    3 | int dst[2][2];

clang's doesn't spell out the object type, but does still show sizes:

<source>:11:5: warning: 'memcpy' will always overflow; destination buffer has size 16, but size argument is 20 [-Wfortify-source]
    std::memcpy(dst, arr, sizeof(arr)+4);
    ^

So it's clearly safe in practice with real compilers, a fact which we already knew. Both see the destination arg as being the whole 16-byte int [2][2] object.

However, GCC and clang are possibly less strict than the ISO C++ standard. Even with dst[0] as the destination (decaying to an int* rather than int (*)[2]), they both still report the destination size as 16 bytes with type int [2][2].

HolyBlackCat's answer points out that calling memcpy this way really only gives it the 2-element sub-array, not the whole 2D array, but compilers don't try to stop you from or warn about using a pointer to the first element to access any part of a larger object.

As I said, testing real compilers can only show us that this is well-defined on them currently; arguments about what they might do in future requires other reasoning (based on nobody wanting to break normal uses of memcpy, and the standard's intended meaning.)

ISO standard's exact wording: arguably a defect

The only question is whether there's any merit to the argument that there's a defect in the standard's wording for the way it explains which object is relevant for the language beyond the end of an object, whether that's limited to the single pointed-to object after array to pointer "decay" for passing an arg to memcpy. (And yes, that would be a defect in the standard; it's widely assumed that you don't need and shouldn't use &arr with an array type for memcpy, or basically ever AFAIK.)

To me, that sounds like a misinterpretation of the standard, but I may be biased because I of course want to read it as saying what we all know is true in practice. I still think that having it be well-defined is a valid interpretation of the wording in the standard, but the other interpretation may also be valid. (i.e. it could be ambiguous whether it's UB or not, which would be a defect.)

A void* pointing to the first element of an array can be cast back to an int (*)[2] to access the whole array object. That isn't how memcpy uses it, but it shows that the pointer hasn't lost its status as a pointer to the whole N-dimensional array. I think the authors of the standard are assuming this reasoning, that this void* can be considered a pointer to the whole object, not just the first element.

However, it's true that there's special language for how memcpy works, and a formal reading could argue that this doesn't let you rely on normal C assumptions about how memory works.

But the UB interpretation allowed by the standard is not how anyone wants it to work or thinks it should. And it would apply to 1D arrays, so this interpretation conflicts with standard examples of using memcpy that are well-known / universally assumed to work. So any argument that the wording in the standard doesn't quite match this is an argument that there's a defect in the wording, not that we need to change our code and avoid this.

There's also no motivation for compiler devs to try to declare this UB because there's very little optimization to be had here (unlike with signed overflow, type-based aliasing, or assumption of no NULL deref).

A compiler assuming that runtime-variable size must only affect at most the whole first element for the pointer type that got cast to void* wouldn't allow much optimization in real code. It's rare for later code to only access elements strictly after the first, which would let the compiler do constant-propagation or similar things past a memcpy that was intended to write it.

(As I said, everyone knows this isn't what the standard intended, unlike with clear statements about signed overflow being UB.)

Is this write to an array truly undefined behavior in C?

There's nothing invalid about your code, the compiler is wrong. If you remove the unnecessary ADDR_AFTER check in test(), the code runs as expected with no UBSan error. If you run it with optimization enabled and without UBSan, you get the wrong output (test=1, should be 2).

Something about the ADDR_AFTER(first) == (uintptr_t)an_int code inside test() makes Clang do the wrong thing when compiling with -O2.

I tested with Apple clang version 11.0.3 (clang-1103.0.32.62) but it looks like Clang 13 and current trunk also have the bug: https://godbolt.org/z/s83ncTsbf - if you change the compiler to any version of GCC you'll see it can return 1 or 2 from main(), while Clang always returns 1 (mov eax, 1).

You should probably file a Clang bug for this.

C/C++: Is This Undefined Behavior? (2D Arrays)