Неопределённое поведение и правда не определено

Термином «неопределённое поведение» в языке C и C++ обозначают ситуацию, в которой буквально «чего только не бывает». Исторически, к неопределённому поведению относили случаи, когда прежние компиляторы для C (и архитектуры на нём) вели себя несовместимым образом, и комитет по разработке стандарта, в своей безграничной мудрости, решил ничего не решать по этому поводу (т.е. не отдавать предпочтение какой-то одной из конкурирующих реализаций). Неопределённым поведением также называли возможные ситуации, в которых стандарт, обычно столь исчерпывающий, не предписывал никакого конкретного поведения. У этого термина есть и третье значение, которое в наше время становится всё более актуальным: неопределённое поведение — это возможности для оптимизации. А разработчики на C и C++ обожают оптимизации; они настойчиво требуют, чтобы компиляторы прикладывали все усилия для ускорения работы кода.

Данная статья была впервые опубликована на сайте Cryptography Services. Перевод публикуется с разрешения автора Томаса Порнина (Thomas Pornin).

Вот классический пример:

void
foo(double *src, int *dst)
{
    int i;

    for (i = 0; i < 4; i ++) {
        dst[i] = (int)src[i];
    }
}

Скомпилируем этот код GCC на 64-битной x86-платформе под Linux (я работаю на свежей версии Ubuntu 18.04, версия GCC — 7.3.0). Включим полную оптимизацию, а затем посмотрим на листинг ассемблера, для чего задействуем ключи "-W -Wall -O9 -S" (аргументом "-O9" задаётся максимальный уровень оптимизации GCC, который на практике эквивалентен "-O3", хотя в некоторых форках GCC определены и более высокие уровни). Получаем следующий результат:

        .file   "zap.c"
        .text
        .p2align 4,,15
        .globl  foo
        .type   foo, @function
foo:
.LFB0:
        .cfi_startproc
        movupd  (%rdi), %xmm0
        movupd  16(%rdi), %xmm1
        cvttpd2dq       %xmm0, %xmm0
        cvttpd2dq       %xmm1, %xmm1
        punpcklqdq      %xmm1, %xmm0
        movups  %xmm0, (%rsi)
        ret
        .cfi_endproc
.LFE0:
        .size   foo, .-foo
        .ident  "GCC: (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0"
        .section        .note.GNU-stack,"",@progbits

Каждая из первых двух инструкций movupd перемещает два значения типа double в 128-битный регистр SSE2 (double имеет размер 64 бита, поэтому регистр SSE2 может хранить два значения типа double). Другими словами, сначала считываются четыре исходных значения, а уже потом они приводятся к int (операции cvttpd2dq). Операция punpcklqdq перемещает четыре полученных 32-битных целых значения в один регистр SSE2 (%xmm0), содержимое которого затем записывается в оперативную память (movups). А теперь главное: наша C-программа формально требует, чтобы доступ к памяти происходил в следующем порядке:

• Считать первое значение типа double из src[0].
• Записать первое значение типа int в dst[0].
• Считать второе значение типа double из src[1].
• Записать второе значение типа int в dst[1].
• Считать третье значение типа double из src[2].
• Записать третье значение типа int в dst[2].
• Считать четвёртое значение типа double из src[3].
• Записать четвёртое значение типа int в dst[3].

Однако все эти требования имеют смысл только в контексте абстрактной машины, которую и определяет стандарт C; порядок действий на реальной машине может отличаться. Компилятор волен переставлять или изменять операции при условии, что их результат не противоречит семантике абстрактной машины (так называемое правило as-if — «как если бы»). В нашем примере порядок действия как раз другой:

• Считать первое значение типа double из src[0].
• Считать второе значение типа double из src[1].
• Считать третье значение типа double из src[2].
• Считать четвёртое значение типа double из src[3].
• Записать первое значение типа int в dst[0].
• Записать второе значение типа int в dst[1].
• Записать третье значение типа int в dst[2].
• Записать четвёртое значение типа int в dst[3].

Таков язык C: всё содержимое памяти в конечном счёте есть байты (т.е. слоты со значениями типа unsigned char, а на практике — группы из восьми битов), и разрешены любые произвольные операции с указателями. В частности, указатели src и dst при вызове могут быть использованы для обращения к перекрывающимся участкам памяти (такая ситуация именуется «алиасингом»). Таким образом, порядок чтения и записи может быть важен в том случае, если байты записываются, а затем снова считываются. Чтобы реальное поведение программы соответствовало абстрактному, определённому стандартом C, компилятор должен был бы чередовать операции чтения и записи, обеспечивая полный цикл обращений к памяти на каждой итерации. Получившийся в результате код имел бы больший размер и работал бы гораздо медленнее. Для C-разработчиков это было бы горе.

Вот тут, к счастью, на помощь и приходит неопределённое поведение. Стандарт C гласит, что доступ к значениям «не может» быть осуществлён через указатели, тип которых не соответствует текущим типам этих значений. Проще говоря, если значение записывается в dst[0], где dst -указатель типа int, то соответствующие байты не могут быть считаны через src[1], где src — указатель типа double, так как в этом случае мы попытались бы получить доступ к значению, которое теперь имеет тип int, с помощью указателя несовместимого типа. В этом случае возникло бы неопределённое поведение. Об этом говорится в параграфе 7 раздела 6.5 стандарта ISO 9899:1999 («C99») (в новой редакции 9899:2018, или «C17», формулировка не изменилась). Это предписание называется правилом строгого алиасинга(strict aliasing). Как следствие, компилятору C разрешено действовать, исходя из предположения, что операции доступа к памяти, приводящие к неопределённому поведению из-за нарушения правила строгого алиасинга, не происходят. Таким образом, компилятор может переставлять операции чтения и записи в любом порядке, поскольку они не должны обращаться к перекрывающимся участкам памяти. В этом и состоит оптимизация кода.

Смысл неопределённого поведения, если кратко, заключается в следующем: компилятор может допустить, что неопределённого поведения не будет, и сгенерировать код, исходя из этого допущения. В случае правила строгого алиасинга — при условии, что алиасинг имеет место быть, — неопределённое поведение позволяет проводить важные оптимизации, реализовать которые иначе было бы сложно. Если говорить в целом, каждая инструкция в процедурах генерации кода, используемых компилятором, имеет зависимости, ограничивающие алгоритм планирования операций: инструкция не может быть выполнена раньше тех инструкций, от которых она зависит, или после тех инструкций, которые зависят от неё. В нашем примере неопределённое поведение устраняет зависимости между операциями записи в dst[] и «последующими» операциями чтения из src[]: такая зависимость может существовать только в тех случаях, когда при доступе к памяти возникает неопределённое поведение. Точно также понятие неопределённого поведения позволяет компилятору просто удалять код, который не может быть выполнен без вхождения в состояние неопределённого поведения.

Всё это, конечно, хорошо, но такое поведение иногда воспринимается как вероломное предательство со стороны компилятора. Можно часто услышать такую фразу: «Компилятор использует понятие неопределённого поведения как предлог сломать мне код». Допустим, некто пишет программу, которая складывает целые числа, и опасается переполнения — вспомним случай с Bitcoin. Он может размышлять так: для представления целых чисел процессор использует дополнительный код, а значит если переполнение случится, то случится оно потому, что результат будет усечён до размера типа, т.е. 32 бит. Значит, результат переполнения можно предсказать и проверить тестом.

Наш условный разработчик напишет так:

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

int
add(int x, int y, int *z)
{
    int r = x + y;
    if (x > 0 && y > 0 && r < x) {
        return 0;
    }
    if (x < 0 && y < 0 && r > x) {
        return 0;
    }
    *z = r;
    return 1;
}

int
main(int argc, char *argv[])
{
    int x, y, z;
    if (argc != 3) {
        return EXIT_FAILURE;
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    if (add(x, y, &z)) {
        printf("%d\n", z);
    } else {
        printf("overflow!\n");
    }
    return 0;
}

Теперь попробуем скомпилировать этот код с помощью GCC:

$ gcc -W -Wall -O9 testadd.c
$ ./a.out 17 42
59
$ ./a.out 2000000000 1500000000
overflow!

Хорошо, вроде работает. Теперь попробуем другой компилятор, например, Clang (у меня версия 6.0.0):

$ clang -W -Wall -O3 testadd.c
$ ./a.out 17 42
59
$ ./a.out 2000000000 1500000000
-794967296

Шта?

Выходит, что, когда операция со знаковыми целыми типами приводит к результату, который не может быть представлен целевым типом, мы вступаем на территорию неопределённого поведения. Но ведь компилятор может допустить, что оно не происходит. В частности, оптимизируя выражение x > 0 && y > 0 && r < x, компилятор делает вывод, что раз значения x и y строго положительные, то третья проверка не может быть истинной (сумма двух значений не может быть меньше любого из них), и всю эту операцию можно пропустить. Другими словами, так как переполнение — это неопределённое поведение, оно «не может произойти» с точки зрения компилятора, и все инструкции, которые зависят от этого состояния, можно удалить. Механизм обнаружения неопределённого поведения попросту исчез.

Стандарт никогда не предписывал допускать, что в вычислениях со знаковыми типами используется «семантика заворачивания» (которая действительно используется в операциях процессора); так сложилось скорее в силу традиции — ещё в те времена, когда компиляторы не были достаточно сообразительны, чтобы оптимизировать код, ориентируясь на диапазон значений. Заставить Clang и GCC применять семантику заворачивания к знаковым типам можно через специальный флаг -fwrapv (в Microsoft Visual C для этого можно использовать -d2UndefIntOverflow-, как описано здесь). Однако этот подход ненадёжен, флаг может исчезнуть при переносе кода в другой проект или на другую архитектуру.

Мало кто знает о том, что переполнение знаковых типов подразумевает неопределённое поведение. Про это сказано в параграфе 5 раздела 6.5 стандартов C99 и C17:

Если при вычислении выражения возникает исключительное состояние (т.е. если результат математически не определён или находится вне диапазона допустимых значений данного типа), поведение не определено.

Для беззнаковых типов, однако, гарантирована модульная семантика. В параграфе 9 раздела 6.2.5 сказано следующее:

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

Ещё одним примером неопределённого поведения в операциях со знаковыми типами является операция деления. Как всем известно, результат деления на ноль математически не определён, поэтому, согласно стандарту, эта операция влечёт за собой неопределённое поведение. Если в операции idiv на x86-процессоре делитель равен нулю, возникает исключение процессора. Подобно запросам на прерывание, исключения процессора обрабатываются операционной системой. На Unix-подобных системах, например Linux, исключение процессора, спровоцированное операцией idiv, переводится в сигнал SIGFPE, который посылается процессу, и тот завершается обработчиком по умолчанию (не удивляйтесь, что «FPE» расшифровывается как «floating-point exception» (исключение в операции с плавающей запятой), тогда как idiv работает с целыми числами). Но есть ещё одна ситуация, которая приводит к неопределённому поведению. Рассмотрим следующий код:

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

int
main(int argc, char *argv[])
{
    int x, y;
    if (argc != 3) {
        return EXIT_FAILURE;
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    printf("%d\n", x / y);
    return 0;
}
Запустим его:
$ gcc -W -Wall -O testdiv.c
$ ./a.out 42 17
2
$ ./a.out -2147483648 -1
zsh: floating point exception (core dumped)  ./a.out -2147483648 -1

И правда: на этой машине (всё та же x86 под Linux) тип int представляет диапазон значений от -2 147 483 648 до [phone]. Если разделить -2 147 483 648 на -1, должно получиться [phone]. Но это число не входит в диапазон значений типа int. Поэтому поведение не определено. Может случиться всё что угодно. В данном случае процесс принудительно завершается. На другой системе, особенно с небольшим процессором, в котором нет операции деления, результат может отличаться. В таких архитектурах деление выполняется программно — с помощью процедуры, обычно предоставляемой компилятором, и вот она может сделать с неопределённым поведением всё, что ей заблагорассудится, ведь именно в этом оно и заключается.

Замечу, что SIGFPE можно получить при тех же условиях и с помощью оператора деления по модулю (%). И в самом деле: под ним скрывается всё та же операция idiv, которая вычисляет и частное, и остаток, поэтому срабатывает то же самое исключение процессора. Что интересно, стандарт C99 говорит, что выражение INT_MIN % -1 не может приводить к неопределённому поведению, поскольку результат математически определён (ноль) и однозначно входит в диапазон значений целевого типа. В версии C17 текст параграфа 6 раздела 6.5.5 был изменён, и теперь этот случай также учитывается, что приближает стандарт к реальному положению дел на распространённых аппаратных платформах.

Существует множество неочевидных ситуаций, также приводящих к неопределённому поведению. Взгляните на этот код:

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

unsigned short
mul(unsigned short x, unsigned short y)
{
    return x * y;
}

int
main(int argc, char *argv[])
{
    int x, y;
    if (argc != 3) {
        return EXIT_FAILURE;
    }
    x = atoi(argv[1]);
    y = atoi(argv[2]);
    printf("%d\n", mul(x, y));
    return 0;
}

Как думаете, что программа, следуя стандарту C, должна распечатать, если в функцию передать множители 45 000 и 50 000?

• 18 048
• 2 250 000 000
• Боже, храни Королеву!

Правильный ответ… да всё вышеперечисленное! Вы, возможно, рассуждали так: раз unsigned short — беззнаковый тип, он должен поддерживать семантику заворачивания по модулю 65 536, потому что на x86-процессоре размер этого типа, как правило, составляет именно 16 бит (стандарт допускает и больший размер, но на практике это всё-таки 16-битный тип). Поскольку математически произведение равно 2 250 000 000, оно будет усечено по модулю 65 536, что даёт ответ 18 048. Однако, размышляя так, мы забываем о расширении целых типов. Согласно стандарту C (раздел 6.3.1.1, параграф 2), если операнды имеют тип, чей размер строго меньше размера int, и значения этого типа могут быть представлены типом int без потери разрядов (а у нас как раз такой случай: на моём x86 под Linux размер int — 32 бита, и он явно может хранить значения от 0 до 65 535), то оба операнда приводятся к типу int и операция совершается уже над преобразованными значениями. А именно: произведение вычисляется как значение типа int и уже только при возврате из функции приводится обратно к unsigned short (т.е. именно в этот момент происходит усечение по модулю 65 536). Проблема в том, что математически результат перед обратным преобразованием равен 2 250 000 000, а это значение превышает диапазон int, который является знаковым типом. В итоге получаем неопределённое поведение. После этого случиться может всё что угодно, в том числе и внезапные приступы английского патриотизма.

Однако на практике, с обычными компиляторами, получится значение 18 048, поскольку не известно ещё такой оптимизации, которая смогла бы воспользоваться неопределённым поведением в данной конкретной программе (можно вообразить более искусственные сценарии, где оно действительно натворило бы бед).

Напоследок ещё один пример, теперь уже на C++:

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

int
main(int argc, char *argv[])
{
    std::array<char, 16> tmp;
    int i;

    if (argc < 2) {
        return EXIT_FAILURE;
    }
    memset(tmp.data(), 0, 16);
    if (strlen(argv[1]) < 16) {
        strcpy(tmp.data(), argv[1]);
    }
    for (i = 0; i < 17; i ++) {
        printf(" %02x", tmp[i]);
    }
    printf("\n");
}

Это вам не типичный «плохой ужасный strcpy()!». Ведь здесь функция strcpy() выполняется, только если размер исходной строки, включая терминальный ноль, достаточно мал. Более того, элементы массива явно инициализируются нулём, поэтому все байты в массиве имеют заданное значение независимо от того, большая или маленькая строка передаётся в функцию. Вместе с тем, цикл в конце некорректен: он считывает на один байт больше, чем положено.

Запустим код:

$ g++ -W -Wall -O9 testvec.c
$ ./a.out foo
 66 6f 6f 00 00 00 00 00 00 00 00 00 00 00 00 00 10 58 ffffffca ff
ffffac ffffffc0 55 00 00 00 ffffff80 71 34 ffffff99 07 ffffffba ff
ffffea ffffffd0 ffffffe5 44 ffffff83 fffffffd 7f 00 00 00 00 00 00
 00 00 00 00 10 58 ffffffca ffffffac ffffffc0 55 00 00 ffffff97 7b
 12 1b ffffffa1 7f 00 00 02 00 00 00 00 00 00 00 ffffffd8 ffffffe5
 44 ffffff83 fffffffd 7f 00 00 00 ffffff80 00 00 02 00 00 00 60 56
(...)
62 64 3d 30 30
zsh: segmentation fault (core dumped)  ./a.out foo
Шта++?

Вы можете наивно возразить: ну хорошо, он считывает лишний байт за границей массива; но это не так уж и страшно, ведь на стеке этот байт всё равно есть, в память отображается, так что единственная проблема тут — это лишний семнадцатый элемент с неизвестным значением. Цикл всё равно напечатает ровно 17 целых чисел (в шестнадцатеричном формате) и завершится без нареканий.

Но у компилятора своё мнение на этот счёт. Он прекрасно понимает, что семнадцатое считывание провоцирует неопределённое поведение. По его логике, любая последующая инструкция оказывается в подвешенном состоянии: нет такого требования, что после неопределённого поведения что-то вообще должно существовать (формально даже предыдущие инструкции могут оказаться под ударом, так как неопределённое поведение действует и в обратную сторону). В нашем случае компилятор просто проигнорирует проверку условия в цикле, и тот будет крутиться вечно, точнее, до тех пор, пока не начнёт читать за пределами выделенной под стек памяти, после чего сработает сигнал SIGSEGV.

Забавно, но если GCC запустить с менее агрессивными настройками для оптимизаций, он выдаст предупреждение:

$ g++ -W -Wall -O1 testvec.c
testvec.c: In function 'int main(int, char**)':
testvec.c:20:15: warning: iteration 16 invokes undefined behavior
[-Waggressive-loop-optimizations]
         printf(" %02x", tmp[i]);
         ~~~~~~^~~~~~~~~~~~~~~~~
testvec.c:19:19: note: within this loop
     for (i = 0; i < 17; i ++) {
                 ~~^~~~

На уровне -O9 это предупреждение почему-то исчезает. Возможно, дело в том, что на высоких уровнях оптимизации компилятор более агрессивно навязывает развёртывание цикла. Возможно (но неточно), что это баг GCC (в смысле пропажа предупреждения; так-то действия GCC в любом случае не противоречат стандарту, ведь тот не требует выдачи «диагностик» в такой ситуации).

Вывод: если вы пишете код на C или C++, будьте предельно внимательны и избегайте ситуаций, приводящих к неопределённому поведению, даже когда кажется, что «ничего страшного».

Беззнаковые целочисленные типы — хороший помощник в арифметических вычислениях, поскольку для них гарантирована модульная семантика (но всё равно можно получить проблемы, связанные с расширением целых типов). Ещё один вариант — почему-то непопулярный — вовсе не писать на C и C++. По ряду причин это решение не всегда подходит. Но если есть возможность выбрать, на каком языке писать программу, т.е. когда вы только приступаете к новому проекту на платформе с поддержкой Go, Rust, Java или других языков, может быть выгоднее отказаться от использования C в качестве «языка по умолчанию». Выбор инструментов, в том числе языка программирования, — это всегда компромисс. Подводные камни C, особенно неопределённое поведение в операциях со знаковыми типами, ведут к дополнительным издержкам при дальнейшем сопровождении кода, которые часто недооцениваются.