Is copying 2D arrays with "memcpy" technically undefined behaviour?

Question

An interesting discussion has arisen in the comments to this recent question: Now, although the language there is C, the discussion has drifted to what the C++ Standard specifies, in terms of what constitutes undefined behaviour when accessing the elements of a multidimensional array using a function like std::memcpy.

First, here's the code from that question, converted to C++ and using const wherever possible:

#include <iostream>
#include <cstring>

void print(const int arr[][3], int n)
{
    for (int r = 0; r < 3; ++r) {
        for (int c = 0; c < n; ++c) {
            std::cout << arr[r][c] << " ";
        }
        std::cout << std::endl;
    }
}

int main()
{
    const int arr[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    int arr_copy[3][3];
    print(arr, 3);
    std::memcpy(arr_copy, arr, sizeof arr);
    print(arr_copy, 3);
    return 0;
}

The issue is in the call to std::memcpy: the arr argument will yield (by decay) a pointer to the first int[3] subarray so, according to one side of the discussion (led by Ted Lyngmo), when the memcpy function accesses data beyond the third element of that subarray, there is formally undefined behaviour (and the same would apply to the destination, arr_copy).

However, the other side of the debate (to which mediocrevegetable1 and I subscribe) uses the rationale that each of the 2D arrays will, by definition, occupy continuous memory and, as the arguments to memcpy are just void* pointers to those locations (and the third, size argument is valid), then there cannot be UB here.

Here's a summary of some of the comments most pertinent to the debate, in case any "clean-up" occurs on the original question (bolding for emphasis mine):

I don't think there's any out-of-bounds here. Just like memcpy works for an array of ints, it works for an array of int [3]s, and both should be contiguous (but I'm not 100% sure). – mediocrevegetable1

The out of bounds access happens when you copy the first byte from arr[0][3]. I've never seen it actually fail, but, in C++, it has UB. – Ted Lyngmo

But the memcpy function/call doesn't do any array indexing - it's just given two void* pointers and copies memory from one to the other. – Adrian Mole

I can't say for sure if that matters in C. In C++ it doesn't. You get a pointer to the first int[3] and any access out of its range has UB. I haven't found any exception to that in the C++ standard. – Ted Lyngmo

I don't think the arr[0][3] thing applies. By that logic, I think copying the second int of an int array through memcpy would be UB as well. int [3] is simply the type of arr's elements, and the bounds of arr as a whole in bytes should be sizeof (int [3]) * 3. I'm probably missing something though :/ – mediocrevegetable1

Are there any C++ Language-Lawyers who can settle the matter – preferably with (an) appropriate citation(s) from the C++ Standard?

Also, relevant citations from the C Standard may be helpful – especially if the two language Standards differ – so I've included the C tag in this question.

Answer 1

std::memcpy(arr_copy, arr, sizeof arr); (your example) is well-defined.

std::memcpy(arr_copy, arr[0], sizeof arr);, on the other hand, causes undefined behavior (at least in C++; not entirely sure about C).

---

Multidimensional arrays are 1D arrays of arrays. As far as I know, they don't get much (if any) special treatment compared to true 1D arrays (i.e. arrays with elements of non-array type).

Consider an example with a 1D array:

int a[3] = {1,2,3}, b[3];
std::memcpy(b, a, sizeof(int) * 3);

This is obviously legal.¹

Notice that memcpy receives a pointer to the first element of the array, and can access other elements.

The element type doesn't affect the validity of this example. If you use a 2D array, the element type becomes int[N] rather than int, but the validity is not affected.

Now, consider a different example:

int a[2][2] = {{1,2},{3,4}}, b[4];
std::memcpy(b, a[0], sizeof(int) * 4);
//             ^~~~

This one causes UB², because since memcpy is given a pointer to the first element of a[0], it can only access the elements of a[0] (a[0][i]), and not a[j][i].

But, if you want my opinion, this is a "tame" kind of UB, likely to not cause problems in practice (but, as always, UB should be avoided if possible).

---

---

¹ The C++ standard doesn't explain memcpy, and instead refers to the C standard. The C standard uses somewhat sloppy wording:

C11 (N1570) [7.24.2.1]/2

The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1.

A pointer to the first (or any) element of an array points only to that element, not to the entire array, even though the entire array is reachable through said pointer. Thus, if interpreted literally, it appears that @LanguageLawyer is right: if you give memcpy a pointer to an array element, you're only allowed to copy that single element, and not the successive elements.

This interpretation contradicts the common sense, and most probably wasn't intended.

E.g. consider the example in [basic.types.general]/2, which applies memcpy to an array using a pointer to the first element: (even though examples are non-normative)

constexpr std::size_t N = sizeof(T);
char buf[N];
T obj;
std::memcpy(buf, &obj, N);
std::memcpy(&obj, buf, N);

---

² This is moot, because of the problematic wording for memcpy described above.

I'm not entirely sure about C, but for C++, there are strong hints that this is UB.

Firstly, consider a similar example that uses std::copy_n, attempting to perform an element-wise copy rather than a byte-wise one:

#include <algorithm>

consteval void foo()
{
    int a[2][2] = {{1,2},{3,4}}, b[2][2] = {{1,2},{3,4}};
    std::copy_n(a[0], 4, b[0]);
}

int main() {foo();} 

Running functions at compile-time catches most form of UB (it makes the code ill-formed), and indeed compiling this snippet gives:

error: call to consteval function 'foo' is not a constant expression
note: cannot refer to element 4 of array of 2 elements in a constant expression

The situation with memcpy is less certain, because it performs a byte-wise copy. This whole topic seems appears to be vague and underspecified.

Consider the wording for std::launder:

[ptr.launder]/4

A byte of storage b is reachable through a pointer value that points to an object Y if there is an object Z, pointer-interconvertible with Y, such that b is within the storage occupied by Z, or the immediately-enclosing array object if Z is an array element.

In other words, given a pointer to an array element, all elements of the said array are reachable through that pointer (non-recursively, i.e. through &a[0][0] only a[0][i] are reachable).

Formally, this definition is only used to describe std::launder (the fact that it can't expand the reachable region of the pointer given to it). But the implication seems to be that this definition summarizes reachability rules described by other parts of the standard ([static.cast]/13, notice that reinterpret_cast is defined through the same wording; also [basic.compound]/4).

It's not entirely clear if said rules apply to memcpy, but they should. Because otherwise, the programmer would be able to disregard reachability using library functions, which would make the concept of reachability mostly useless.

Answer 2

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

Answer 3

With all due respect, HolyBlackCat is utterly wrong, for very first principles. My C17 standard draft says in 7.24.1: "For all functions in this subclause [containing memcpy], each character shall be interpreted as if it had the type unsigned char." The C standard doesn't really make any type considerations for these trivial functions: memcpy copies memory. As far as semantics are at all considered, it is treated as a sequence of unsigned characters. Therefore, the following first C principle applies:

As long as there is an initialized object at an address you can access it through a char pointer.

Let's repeat it for emphasis and clarity:

Any initialized object can be accessed by a char pointer.

If you know that an object is at a specific address 0x42, for example because the hardware of your computer maps the x coordinate of your mouse there, you can convert that into a char pointer and read it. If the coordinate is a 16 bit value you can read the next byte too.

Nobody cares how you know that there is an integer: If there is one, you can read it. (Peter Cordes noted that there is no guarantee that you can arrive at a valid address (or at least, at the expected address) through pointer arithmetic from an unrelated object because of possible segmented memory architectures. But this is not the example case: The entire array is one object and must reside in a single segment.)

Now that we have 3 arrays of 3 ints we know that 9 ints are placed consecutively in memory; that is a language requirement. The entire memory there is full of ints belonging to a single object, and we can iterate manually over it through char pointers, or we can turf it to memcpy. Whether we use arr or arr[0] or obtain the address through a stack offset from some other variable [<- not guaranteed correct as Peter Cordes reminded me] or some other magic or simply make an educated guess is entirely irrelevant as long as the address is correct, and of that there is no doubt here.

Answer 4

The question is about C++; I can only answer for C. In C, this is well-defined behavior. I'll be quoting from a December 11, 2020 draft of the C2x standard, found at http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2596.pdf; all emphasis will be as in the original.

The question is whether we can apply a memcpy to an int[3][3]. An int[3][3] is an array of arrays, while memcpy works on bytes. So we will need to know what the standard says about the representation of arrays as bytes.

We start with arrays. Section 6.2.5, "Types", paragraph 22, defines array types:

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

An int[3][3] is therefore a contiguously allocated nonempty set of three int[3] objects. Each of those is a contiguously allocated nonempty set of three int objects.

Let's first ask about int objects. Everyone expects a memcpy of a single int to work. To see that the standard requires this, we look in section 6.2.6.1, "General", paragraph 2:

Except for bit-fields, objects are composed of contiguous sequences of one or more bytes, the number, order, and encoding of which are either explicitly specified or implementation-defined.

So an int is a contiguous sequence of one or more bytes. Therefore our int[3][3] is a contiguous sequence of three contiguous sequences of three contiguous sequences of sizeof(int) bytes; the standard requires that it is 9 × sizeof(int) contiguous bytes.

The standard also puts requirements on how these bytes relate to the array indices. Section 6.5.2.1, "Array subscripting," paragraph 2, says:

A postfix expression followed by an expression in square brackets [] is a subscripted designation of an element of an array object. The definition of the subscript operator [] is that E1[E2] is identical to (*((E1)+(E2))).

So arr[1] == *((arr)+(1)) is the second int[3], arr[1][2] == *((*((arr)+(1)))+(2)) is its third element, and this must be the sixth int past the start of arr. Paragraph 3 is explicit about this:

Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n ≥ 2) with dimensions i × j × ··· × k, then E (used as other than an lvalue) is converted to a pointer to an (n − 1)-dimensional array with dimensions j × ··· × k. If the unary * operator is applied to this pointer explicitly, or implicitly as a result of subscripting, the result is the referenced (n − 1)-dimensional array, which itself is converted into a pointer if used as other than an lvalue. It follows from this that arrays are stored in row-major order (last subscript varies fastest).

Despite this, you're still not allowed to access arr[0][4]. As Ted Lyngmo's answer notes, Appendix J.2 specifically says:

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

But since memcpy is really about bytes, it's okay. Its source and destination aren't multidimensional arrays but void *. 7.24.2.1, "The memcpy function," explains:

The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1.

A "character" can have three meanings according to section 3.7. The relevant one seems to be "single-byte character" (3.7.1), and therefore memcpy copies n bytes. Hence memcpy(arr_copy, arr, sizeof(arr)) must copy arr to arr_copy correctly.

Though come to think of it, memcpy doesn't say that it copies n contiguous bytes. I suppose it could copy the same byte n times. Or pick n random bytes. That would make debugging ... interesting.

Answer 5

Is copying 2D arrays with "memcpy" technically undefined behaviour?

(n.b., this only covers C, per the draft C11 standard at https://port70.net/~nsz/c/c11/n1570.html)

No, it is not.

TLDR Summary:

6.7.6.3 Function declarators (including prototypes), paragraph 7 defines decay of arrays to pointers in function calls. BUT that decay is done under the auspices of 6.9.1 Function definitions, paragraph 7, which states "... in either case, the type of each parameter is adjusted as described in 6.7.6.3 for a parameter type list; the resulting type shall be a complete object type."

That directly refutes the concept that the pointer that results from array decay when an array is passed as a function parameter does not refer to the entire array.

Detailed Answer

First arrays are "complete objects".

Why arrays must be "complete objects"

(If someone can find a statement in the standard[s] defining arrays as "complete objects" this entire section of this answer is redundant.)

While not explicitly defined as such in the (draft) C11 standard (at least not anywhere that I have been able to find), arrays are implicitly "complete objects" in multiple statements, such as statements where arrays are explicitly removed from the "complete object" category:

6.5.2.2 Function calls, paragraph 1:

The expression that denotes the called function shall have type pointer to function returning void or returning a complete object type other than an array type.

6.7.2.1 Structure and union specifiers does not explicitly allow array members of structures and unions other than "flexible array members" in paragraph 18:

As a special case, the last element of a structure with more than one named member may have an incomplete array type; this is called a flexible array member. ...

The only paragraph of 6.7.2.1 Structure and union specifiers is paragraph 9:

A member of a structure or union may have any complete object type other than a variably modified type.

That is the only statement in the (draft) C11 standard that allows for the inclusion of arrays in structures and unions.

Array initialization is covered by 6.7.9 Initialization, paragraph 3:

The type of the entity to be initialized shall be an array of unknown size or a complete object type that is not a variable length array type.

That only covers arrays of fixed, known size via the category "complete object".

Function return values have arrays explicitly removed from the "complete object" category by 6.9.1 Function definitions, paragraph 3:

The return type of a function shall be void or a complete object type other than array type.

So, we have established that arrays are "complete objects".

Parameters to functions are "complete object types"

Per 6.9.1 Function definitions, Semantics, paragraph 7:

the type of each parameter is adjusted as described in 6.7.6.3 for a parameter type list; the resulting type shall be a complete object type.

Why "complete object" is important

6.5.2.1 Array subscripting, paragraph 1 states:

One of the expressions shall have type ''pointer to complete object type'', the other expression shall have integer type, and the result has type ''type''.

And per 6.9.1p7, the array was passed as a "complete object type", which means the pointer can be dereferenced to access the entire array.

Q.E.D.

Answer 6

The indicated use of memcpy will be processed meaningfully by any compiler whose authors don't abuse the Standard as an excuse to regard useful constructs as "broken". The only people who should care about whether the Standard actually defines it without contradiction would be compiler writers who abuse the Standard, or those seeking to protect themselves against compiler writers that abuse the Standard. If the C or C++ Standards were intended to be immune to abuse, it might be worth worrying about whether it 100% unambiguously specifies all of the cases were memcpy should work. Both are written, however, to be reliant upon compiler writers to recognize that if a Standard would simultaneously specifies how some constructs work, but characterizes an overlapping set of constructs as invoking Undefined Behavior, compilers should make a good faith effort to process code as usefully as practical.

Consider the two functions:

char arr[4][4][4];

int test1(int i, unsigned mode)
{
  arr[1][0][0] = 1;
  memcpy(arr[0][i], arr[2][0], mode & 4);
  return arr[1][0][0];
}

int test2(int i, unsigned mode)
{
  arr[1][0][0] = 1;
  memcpy(arr[0]+i, arr[2], mode & 4);
  return arr[1][0][0];
}

Depending upon what the programmer is trying to do, any of the following interpretations might be most useful:

1. Process both functions in a way that reloads the value of arr[1][0][0] after the memcpy.

2. Process both functions in a way that returns 1 unconditionally without regard for whether memcpy overwrote it.

3. Process the first function in a manner that unconditionally returns 1, but process the second in a manner that reloads arr[1][0][0], on the basis that while the Standards define the use of index operators on array lvalues/glvalues in terms of array decay followed by pointer indexing, programmers' choice of syntax is often based upon whether an array-type lvalue/glvalue is actually being used as an array, or is being used as a means of getting a pointer to the first element, which then be used as the base for further address calculations.

If a compiler were to attempt to process the code meaningfully in the case where i and mode are 4, there would be no bona fide ambiguity about how the code should behave. Only one behavior would make sense. The only ambiguity is whether the benefits of accommodating that case would be worth the execution cost of doing so; accommodating the behavior is always a "safe" choice. It would be awkward to write the Standard to say that test1 should have defined behavior for i==0..3 when n is 4, and i==0..4 when n is zero, but test2 should have defined behavior for i==0..15 regardless of n, but for most purposes the best blend of semantics, compatibility, and optimization would be achieved by processing code in that fashion.

Answer 7

My current standpoint is that when an int[3][3] is passed as an argument to a function, it decays into a pointer to the first element in that array. The first element is an int[3] and the other two int[3]s are in range - just like when you pass a 1D int[3] to a function, you get a pointer to the first int and the other two ints are in range, hence the memcpy is safe.

---

Original answer:

_{This answer is based on some wrong assumptions I made by reading something a long time ago. I'll leave the answer and the comments up to perhaps prevent other people from walking into the same mind-trap.}

What is passed to the function decays into a pointers to the first elements, that is in this case, two int(*)[3]s.

C draft Annex J (informative) Portability issues J.2 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).

memcpy(arr_copy, arr, sizeof arr); get's two int(*)[3] and will access both out of range, hence, UB.

Answer 8

C++ standard says ([cstring.syn]/1):

The contents and meaning of the header <cstring> are the same as the C standard library header <string.h>.

C11 7.24.2.1 The memcpy function says:

Synopsis

1

         #include <string.h>
         void *memcpy(void * restrict s1,
              const void * restrict s2,
              size_t n);

Description

2 The memcpy function copies n characters from the object pointed to by s2 into the object pointed to by s1…

Given this description, one may wonder what if n is greater than the size of the object pointed to by s1/s2. «Common sense» suggests that copying more than, say, sizeof(int) bytes from an int object should be meaningless.

And indeed, there is 7.24.1 String function conventions p.1 saying:

The header <string.h> declares one type and several functions, and defines one macro useful for manipulating arrays of character type and other objects treated as arrays of character type. … Various methods are used for determining the lengths of the arrays, but in all cases a char * or void * argument points to the initial (lowest addressed) character of the array. If an array is accessed beyond the end of an object, the behavior is undefined.

Thus, when passing a pointer to the first element of an array, it is «the object» from memcpy p.2 and trying to copy more bytes than this object has is UB.