Безопасная работа с массивами? Нет, не слышали28.03.2025 11:46
Рано или поздно любому разработчику на С-подобном языке приходит в голову идея использовать двумерный массив как одномерный. Причины для этого всегда разные, а вот результат чаще всего один. В этой небольшой заметке разберём эту сомнительную технику и какие проблемы она может привнести в вашу программу.
О чём речь?
Тема индексации массивов не раз обсуждалась в разных статьях, но мы решили рассмотреть её более детально. При анализе некоторых Open Source проектов с помощью PVS-Studio нам попадались фрагменты кода, которые открыто используют многомерный массив как одномерный. И когда мы разбирались в этой теме, у многих возникал вопрос: «Всё же работает, в чём они не правы?».
А можно пример?
Чтобы разобраться в ситуации, посмотрим на небольшой фрагмент кода:
#define ROWS (2)
#define COLS (4)
int main()
{
int a[ROWS][COLS] = { 0, 1, 2, 3, 4, 5, 6, 7 };
for (int i = 0; i < ROWS * COLS; ++i)
{
printf(" %d", a[0][i]);
}
return 0;
}
Здесь двумерный массив a используется как одномерный: в цикле мы обращаемся к элементам через a[0][i], где i пробегает от 0 до ROWS * COLS. А что тут неправильного? Ведь согласно стандарту, все элементы массива располагаются в памяти последовательно:
An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified.
В примере происходит последовательный доступ к элементам с помощью адресной арифметики относительно начала двумерного массива. Давайте обратимся к стандартам языков C и C++, чтобы понять, что нас ожидает при написании такого кода:
C23
6.5.3.2/2:
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))). Because of the conversion rules that apply to the binary + operator, if E1 is an array object (equivalently, a pointer to the initial element of an array object) and E2 is an integer,
E1[E2] designates the E2-th element of E1 (counting from zero).
6.5.7/9:
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 the pointer operand and the result do not point to elements of the same array object or one past the last element of the array object, the behavior is undefined. If the addition or subtraction produces an overflow, 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.
C++23
7.6.1.2/1:
A subscript expression is a postfix expression followed by square brackets containing a possibly empty, comma-separated list of initializer-clauses that constitute the arguments to the subscript operator. The postfix-expression and the initialization of the object parameter of any applicable subscript operator function is sequenced before each expression in the expression-list and also before any default argument. The initialization of a non-object parameter of a subscript operator function S, including every associated value computation and side effect, is indeterminately sequenced with respect to that of any other non-object parameter of S.
7.6.1.2/2:
With the built-in subscript operator, an expression-list shall be present, consisting of a single assignment-expression. One of the expressions shall be a glvalue of type «array of T» or a prvalue of type «pointer to T» and the other shall be a prvalue of unscoped enumeration or integral type. The result is of type «T». The type «T» shall be a completely-defined object type. The expression E1[E2] is identical (by definition) to *((E1)+(E2)), except that in the case of an array operand, the result is an lvalue if that operand is an lvalue and an xvalue otherwise.
7.6.6/4:
When an expression J that has integral type is added to or subtracted from an expression P of pointer type, the result has the type of P.
If P evaluates to a null pointer value and J evaluates to 0, the result is a null pointer value.
Otherwise, if P points to an array element i of an array object x with n elements, the expressions P + J and J + P (where J has the value j) point to the (possibly-hypothetical) array element i + j of x if 0 ≤ i + j ≤ n and the expression P - J points to the (possibly-hypothetical) array element i - j of x if 0 ≤ i − j ≤ n.
Otherwise, the behavior is undefined.
Если кратко, то оба стандарта говорят нам о том, что арифметика указателей позволяет смещаться по элементам массива, но выход за его границы приводит к неопределённому поведению.
Вернёмся к примеру с двумерным массивом a[2][4]. Результатом первого оператора индексирования a[0] будет указатель на int[4], а значит доступ может осуществляться только в интервале [0...3]. Иначе произойдёт выход за границу массива, при котором поведение не определено. Проблема найдена.
Да что такого может произойти?
Просто прочтите эту статью, и ответ станет очевиден.
Но кто мы такие, чтобы просто поверить «какой-то» статье? Лучше вооружимся Compiler Explorer, возьмём в качестве примера компилятор GCC 14.2 и изучим поглубже, что же может произойти.
Сначала посмотрим на ассемблерный код при корректной индексации (исходный код также доступен по ссылке).
Ассемблерный код (x86–64, GCC 14.2)
.LC2:
.string " %d"
main:
; Пролог функции
push r12
push rbp
push rbx
; Резервирование памяти на стеке под массив int[2][4]
sub rsp, 32
; Подготовка к инициализации a[0] четырьмя элементами через xmm0
movdqa xmm0, XMMWORD PTR .LC0[rip]
; Сохранение верхушки стека в rbx
mov rbx, rsp
; Сохранение в r12 one-past-the-end от массива a[0]
lea r12, [rsp+16]
; Инициализация a[0] четырьмя элементами через xmm0
movaps XMMWORD PTR [rsp], xmm0
; Подготовка к инициализации arr[1] четырьмя элементами через xmm0
movdqa xmm0, XMMWORD PTR .LC1[rip]
; Сохранение верхушки стека в rbp
mov rbp, rbx
; Инициализация a[1] четырьмя элементами через xmm0
movaps XMMWORD PTR [rsp+16], xmm0
.L2:
; Печать очередного элемента массива a[0], начиная с верхушки стека
mov esi, DWORD PTR [rbp+0]
mov edi, OFFSET FLAT:.LC2
xor eax, eax
add rbp, 4
call printf
; Цикл до конца a[0] (r12)
cmp r12, rbp
jne .L2
.L3:
; Печать очередного элемента массива a[1]
mov esi, DWORD PTR [rbx+16]
mov edi, OFFSET FLAT:.LC2
xor eax, eax
add rbx, 4
call printf
; Цикл до конца a[0] (r12)
cmp r12, rbx
jne .L3
; Эпилог функции
add rsp, 32
xor eax, eax
pop rbx
pop rbp
pop r12
ret
; Инициализаторы двумерного массива
.LC0:
.long 0
.long 1
.long 2
.long 3
.LC1:
.long 4
.long 5
.long 6
.long 7
Если вы убеждены, что в памяти массив будет располагаться линейно, то для архитектуры x86–64 это действительно так: резервируется непрерывный участок памяти на стеке под весь двумерный массив. И мы можем заметить, что компилятор дальше этим активно пользуется.
Он оптимизировал наш вложенный цикл до двух линейных, идущих друг за другом. Первый проходит по массиву a[0] и отправляет в печать каждый элемент до конца этого массива. Второй цикл также проходит по массиву a[0], но отправляет в печать каждый элемент из массива a[1] при помощи сдвига на 16 байт, т.е. на размер массива a[0] в 4 элемента.
Результат выполнения этой программы совпадает с нашими ожиданиями:
Ну раз компилятор генерирует код, в котором многомерный массив весь лежит последовательно, то у читателя может возникнуть следующий вопрос:
Переписываем код на один цикл и проверяем это утверждение.
Ассемблерный код с индексацией, поведение которой не определено (x86–64, GCC 14.2)
.LC1:
.string " %d"
main:
push rbx
; Резервирование памяти на стеке под массив int[2][4]
sub rsp, 32
; Подготовка к инициализации a[0] четырьмя элементами через xmm0
movdqa xmm0, XMMWORD PTR .LC0[rip]
; Сохранение верхушки стека в rbx
mov rbx, rsp
; Инициализация a[0] четырьмя элементами через xmm0
movaps XMMWORD PTR [rsp], xmm0
.L2:
; Печать очередного элемента массива
mov esi, DWORD PTR [rbx]
mov edi, OFFSET FLAT:.LC1
xor eax, eax
add rbx, 4
call printf
; Вычисление адреса конца массива
lea rax, [rsp+32]
; Цикл до конца массива
cmp rbx, rax
jne .L2
add rsp, 32
xor eax, eax
pop rbx
ret
.LC0:
.long 0
.long 1
.long 2
.long 3
Разницу в ассемблерном коде можно увидеть тут.
В этом случае компилятор воспользовался неопределённым поведением и просто не стал инициализировать массив a[1]. Зачем тратить на это время, если при печати элементов происходит выход за границу массива, и компилятор вправе сделать что угодно.
Соответственно, и результат выполнения этой программы зависит от вашего везения, фаз Луны и умения гадать на кофейной гуще. Вот что выдалось мне в первый раз:
Что интересно, компилятор GCC в этой ситуации выдал предупреждение:
:11:5: warning: iteration 4 invokes
undefined behavior [-Waggressive-loop-optimizations]
11 | printf(" %d", a[0][i]);
| ^~~~~~~~~~~~~~~~~~~~~~
:9:21: note: within this loop
9 | for (int i = 0; i < ROWS * COLS; ++i)
| ^
А также на этот код выдаёт предупреждение анализатор PVS-Studio:
V557 Array overrun is possible. The value of 'i' index could reach 7.
Как можно исправить?
Ответ прост — пишите циклы корректно, не эксплуатируйте неопределённое поведение:)
Но что, если мы хотим, чтобы массив гарантированно лежал в памяти последовательно и при этом иметь доступ к нему как одномерному, так и многомерному? Для C++ решение есть: в C++23 был введён std::mdspan, которым можно индексировать линейный массив в любой необходимой размерности.
Рассмотрим подробнее на примере:
int main()
{
int a[ROWS * COLS] = { 0, 1, 2, 3, 4, 5, 6, 7 };
auto view_2d = std::mdspan { a, ROWS, COLS };
for (auto i = 0uz; i < ROWS; ++i)
{
for (auto j = 0uz; j < COLS; ++j)
{
printf(" %d", view_2d[i, j]);
}
}
}
Здесь создаётся одномерный массив, но при необходимости мы можем трактовать его как двумерный. При этом объект std::mdspan не создаёт под коробкой никаких копий нашего исходного массива, т.к. является невладеющей обёрткой.
Примечание. На момент написания статьи std::mdspan имплементирован в Clang 18 (libc++). Поддержку в прочих компиляторах можно проверить на странице «С++ compiler support» поиском по фразе «std: mdspan: a non-owning multidimensional array reference».
Заключение
Надеюсь, эта небольшая статья помогла вам разобраться, почему использование двумерного массива как одномерного небезопасно и приводит к неопределённому поведению.
Мы уже не раз видели подобные проблемы и разбирали их в статьях. Однако, чтобы и вам было проще находить опасные участки кода в своём проекте, предлагаю попробовать статический анализатор PVS-Studio.
Если хотите поделиться этой статьей с англоязычной аудиторией, то прошу использовать ссылку на перевод: Aleksandra Uvarova. Safe array handling? Never heard of it.
