- PVSM.RU - https://www.pvsm.ru -
В соответствии со стандартами C и C++, если выполнение программы приводит к переполнению знаковой целой переменной, или к любому из сотен других «неопределённых действий» (undefined behaviour, UB), то результат выполнения программы может быть любым: она может запостить на Твиттер непристойности, может отформатировать вам диск…
Увы, в действительности «пасхальные яйца», которые бы заставляли программу в случае UB делать что-то из ряда вон выходящее, не встречались со времён GCC 1.17 — та запускала nethack [1], когда встречала в коде программы неизвестные #pragma
. Обычно же результат UB намного скучнее: компилятор просто оптимизирует код для тех случаев, когда UB не происходит, не придавая ни малейшего значения тому, что этот код будет делать в случае UB — ведь стандарт разрешает сделать в этом случае что угодно!
В качестве иллюстрации того, как изобилие UB в стандарте позволяет компилятору выполнять неочевидные оптимизации, Реймонд Чен приводит [2] такой пример кода:
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;
}
Такие оптимизации иногда застают программистов врасплох. Джон Регер приводит [3] подборку примеров, когда UB приводило к значительным последствиям:
NULL
позволило [5] компилятору удалить эту проверку, создав уязвимость в системе.p
не инициализирована, программа может [7] выполнить и код внутри if (p) { ... }
, и код внутри if (!p) { ... }
.x
равна INT_MAX
, выражение (x+1)>x
в разных местах одной программы может [8] трактоваться и как истинное, и как ложное.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». Один из победителей [11] воспользовался тем, что использование указателя после того, как он передан параметром в 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
Программы остальных победителей конкурса, на мой взгляд, скучнее и частично перекрываются с ранее приведёнными примерами.
Но ничто не сравнится с примером самого Регера — «опровержением» компилятором теоремы Ферма [12].
Он объясняет, что для какого-то встроенного приложения ему нужно было написать на 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
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/65065
Ссылки в тексте:
[1] nethack: https://ru.wikipedia.org/wiki/NetHack
[2] приводит: http://blogs.msdn.com/b/oldnewthing/archive/2014/06/27/10537746.aspx
[3] приводит: http://blog.regehr.org/archives/759
[4] позволило: http://code.google.com/p/nativeclient/issues/detail?id=245
[5] позволило: https://isc.sans.edu/diary.html?storyid=6820
[6] привело: http://kqueue.org/blog/2012/06/25/more-randomness-or-less/
[7] может: http://markshroyer.com/2012/06/c-both-true-and-false/
[8] может: http://www.cs.utah.edu/~regehr/papers/overflow12.pdf
[9] может: http://blog.regehr.org/archives/161
[10] может: http://blog.regehr.org/archives/232
[11] Один из победителей: http://blog.regehr.org/archives/767
[12] «опровержением» компилятором теоремы Ферма: http://blog.regehr.org/archives/140
[13] Источник: http://habrahabr.ru/post/229963/
Нажмите здесь для печати.