Александра Уварова

28 Мар 2025

Теги:

#Cpp #Knowledge

Безопасная работа с массивами? Нет, не слышали

28 Мар 2025

Автор: Александра Уварова

О чём речь?
А можно пример?
Да что такого может произойти?
Как можно исправить?
Заключение

Рано или поздно любому разработчику на С-подобном языке приходит в голову идея использовать двумерный массив как одномерный. Причины для этого всегда разные, а вот результат чаще всего один. В этой небольшой заметке разберём эту сомнительную технику и какие проблемы она может привнести в вашу программу.

1241_Safe_work_with_arrays_ru/image1.png

О чём речь?

Тема индексации массивов не раз обсуждалась в разных статьях, но мы решили рассмотреть её более детально. При анализе некоторых 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) open icon

.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 элемента.

Результат выполнения этой программы совпадает с нашими ожиданиями:

ASM generation compiler returned: 0
Execution build compiler returned: 0
Program returned: 0
 0 1 2 3 4 5 6 7

Ну раз компилятор генерирует код, в котором многомерный массив весь лежит последовательно, то у читателя может возникнуть следующий вопрос:

1241_Safe_work_with_arrays_ru/image2.png

Переписываем код на один цикл и проверяем это утверждение.

Ассемблерный код с индексацией, поведение которой не определено (x86-64, GCC 14.2) open icon

.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]. Зачем тратить на это время, если при печати элементов происходит выход за границу массива, и компилятор вправе сделать что угодно.

Соответственно, и результат выполнения этой программы зависит от вашего везения, фаз Луны и умения гадать на кофейной гуще. Вот что выдалось мне в первый раз:

ASM generation compiler returned: 0
Execution build compiler returned: 0
Program returned: 0
 0 1 2 3 -994840135 32766 100 0

Что интересно, компилятор GCC в этой ситуации выдал предупреждение:

<source>:11:5: warning: iteration 4 invokes
                        undefined behavior [-Waggressive-loop-optimizations]
   11 |     printf(" %d", a[0][i]);
      |     ^~~~~~~~~~~~~~~~~~~~~~
<source>: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.

#Cpp #Knowledge