В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack, когда встречала в коде программы неизвестные . Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит такой пример кода:
int table[4];
bool exists_in_table(int v)
{
for (int i = 0; i <= 4; i++) {
if (table[i] == v) return true;
}
return false;
}
В условии цикла мы ошиблись на единицу, поставив <=
вместо <
. В итоге exists_in_table()
либо должна вернуть true
на одной из первых четырёх итераций, либо она прочтёт table[4]
, что является UB, и в этом случае exists_in_table()
может сделать всё что угодно — в том числе, вернуть true
! В полном соответствии со стандартом, компилятор может соптимизировать код exists_in_table()
до
int table[4];
bool exists_in_table(int v)
{
return true;
}
Такие оптимизации иногда застают программистов врасплох. Джон Регер приводит подборку примеров, когда UB приводило к значительным последствиям:
- UB при знаковом сдвиге влево позволило компилятору удалить из NaCl проверку адреса возврата, важную для безопасности.
- В ядре Linux, разыменование указателя перед его проверкой на
NULL
позволило компилятору удалить эту проверку, создав уязвимость в системе. - В Debian, использование неинициализированного массива в качестве источника случайных данных для инициализации RNG seed привело к тому, что всё вычисление seed было удалено компилятором.
- Когда переменная
p
не инициализирована, программа может выполнить и код внутриif (p) { ... }
, и код внутриif (!p) { ... }
. - Когда знаковая переменная
x
равнаINT_MAX
, выражение(x+1)>x
в разных местах одной программы может трактоваться и как истинное, и как ложное. - Бесконечный цикл, например поиск несуществующего значения, может быть удалён компилятором. Например, так компилятор может «опровергнуть» Великую теорему Ферма. (Этот пример мы ещё разберём подробно.)
- Компилятор может сделать программу «ясновидящей», переставив операцию, потенциально способную обрушить процесс (деление на ноль, чтение по нулевому указателю и т.п.), вперёд операции вывода. Например, вот этот код:
int a; void bar (void) { setlinebuf(stdout); printf ("hello!n"); } void foo3 (unsigned y, unsigned z) { bar(); a = y%z; } int main (void) { foo3(1,0); return 0; }
— успеет напечатать сообщение перед SIGFPE, если его скомпилировать без оптимизаций; и рухнет сразу при старте, если включить оптимизацию. Программа «заранее знает», что ей суждено упасть с SIGFPE, и поэтому даже не заморачивается печатью сообщения. Похожий пример, только с SIGSEGV, приводит и Чен.
В 2012 Регер объявил конкурс на «самый причудливый результат UB». Один из победителей воспользовался тем, что использование указателя после того, как он передан параметром в realloc()
, является UB. Его программа печатает разные значения по одному и тому же указателю:
#include <stdio.h>
#include <stdlib.h>
int main() {
int *p = (int*)malloc(sizeof(int));
int *q = (int*)realloc(p, sizeof(int));
*p = 1;
*q = 2;
if (p == q)
printf("%d %dn", *p, *q);
}
$ clang -O realloc.c ; ./a.out 1 2
Программы остальных победителей конкурса, на мой взгляд, скучнее и частично перекрываются с ранее приведёнными примерами.
Но ничто не сравнится с примером самого Регера — «опровержением» компилятором теоремы Ферма.
Он объясняет, что для какого-то встроенного приложения ему нужно было написать на C++ бесконечный цикл так, чтобы оптимизирующий компилятор не смог удалить из программы весь код, следующий за циклом. Современные компиляторы достаточно умны, чтобы узнавать «идиомы» навроде while (1) { }
или for (;;) { }
— они понимают, что код, следующий за таким циклом, никогда не выполнится, а значит, его и компилировать незачем. Например, функцию
void foo (void)
{
for (;;) { }
open_pod_bay_doors();
}
— большинство компиляторов «укоротят» до единственной инструкции:
foo:
L2: jmp L2
Clang оказывается ещё умнее, он способен распознавать (и удалять) даже такие замаскированные бесконечные циклы:
unsigned int i = 0;
do {
i+=2;
} while (0==(i&1));
Здесь, как и в предыдущем примере, компилятор способен доказать, что выход из цикла невозможен, а значит, его можно заменить одной инструкцией jmp
.
Регер решил: уж теорему Ферма-то компиляторы вряд ли смогут доказать во время компиляции?
int fermat (void)
{
const int MAX = 1000;
int a=1,b=1,c=1;
while (1) {
if (((a*a*a) == ((b*b*b)+(c*c*c)))) return 1;
a++;
if (a>MAX) {
a=1;
b++;
}
if (b>MAX) {
b=1;
c++;
}
if (c>MAX) {
c=1;
}
}
return 0;
}
#include <stdio.h>
int main (void)
{
if (fermat()) {
printf ("Fermat's Last Theorem has been disproved.n");
} else {
printf ("Fermat's Last Theorem has not been disproved.n");
}
return 0;
}
regehr@john-home:~$ icc fermat2.c -o fermat2 regehr@john-home:~$ ./fermat2 Fermat's Last Theorem has been disproved. regehr@john-home:~$ suncc -O fermat2.c -o fermat2 "fermat2.c", line 20: warning: statement not reached regehr@john-home:~$ ./fermat2 Fermat's Last Theorem has been disproved.
Как так? Цикл завершится по return 1;
— компилятор смог доказать, что теорема Ферма неверна?!
Интересно, какие же значения a,b,c
он «нашёл»?
Регер добавил печать «найденных значений» перед return 1;
— вот тогда компилятор признал бессилие и честно скомпилировал бесконечный цикл. (Ничего, естественно, не напечаталось.)
Несмотря на то, что эта программа не содержит никаких арифметических переполнений (множители изменяются в пределах 1..1000, сумма их кубов не превосходит 231), стандарт C++ объявляет «неопределённым действием» бесконечный цикл без изменения внешнего состояния — поэтому компиляторы C++ вправе считать любой такой цикл конечным.
Компилятор легко видит, что единственный выход из цикла while(1)
— это оператор return 1;
, а оператор return 0;
в конце fermat()
недостижим; поэтому он оптимизирует эту функцию до
int fermat (void)
{
return 1;
}
Иначе говоря, единственная возможность написать на C++ такой бесконечный цикл, который компилятор не смог бы удалить — это добавить внутрь цикла изменение внешнего состояния. Самый простой (и стандартный!) способ сделать это — изменять переменную, объявленную как volatile
.
Автор: tyomitch