Многие считают, что неопределённое поведение программы возникает из-за грубых ошибок (например, запись за границы массива) или на неадекватных конструкциях (например, i = i++ + ++i). Поэтому для многих является неожиданностью, когда неопределенное поведение вдруг проявляет себя во вполне привычном и ничем не настораживающем коде. Рассмотрим один из таких примеров. Программируя на C/C++ никогда нельзя терять бдительность. Ад ближе чем кажется.Описание ошибки
Я давненько не поднимал тему 64-битных ошибок. Тряхну стариной. В данном случае неопределённое проведение будет проявлять себя в 64-битной программе.
Рассмотрим некорректный синтетический пример кода.
size_t Count = 1024*1024*1024; // 1 Gb
if (is64bit)
Count *= 5; // 5 Gb
char *array = (char *)malloc(Count);
memset(array, 0, Count);
int index = 0;
for (size_t i = 0; i != Count; i++)
array[index++] = char(i) | 1;
if (array[Count - 1] == 0)
printf("The last array element contains 0.\n");
free(array);Этот код корректно работает, если собрать 32-битную версию программы. А вот если собрать 64-битный вариант программы, всё намного интересней.
64-битная программа выделяет массив байт размеров в 5 гигабайт и заполняет его нулями. Затем в цикле массив заполняется какими-то случайными числами, неравными нулю. Чтобы числа не были равны 0, используется "| 1".
Попробуйте угадать, как поведёт себя эта программа, собранная в режиме x64 с помощью компилятора, входящего в состав Visual Studio 2015. Заготовили ответ? Если да, то продолжим.
Если вы запустите отладочную версию этой программы, то она упадёт из-за выхода за границу массива. В какой-то момент переменная index переполнится и её значение станет равно ?2147483648 (INT_MIN).
Логичное объяснение? Ничего подобного! Это неопределённое поведение и произойти может всё что угодно.
Дополнительные ссылки:
- Integer overflow
- Understanding Integer Overflow in C/C++
- Is signed integer overflow still undefined behavior in C++?
Когда я или кто-то ещё говорит, что это неопределённое поведение, люди начинают ворчать. Я не знаю почему, но люди уверены, что точно знают, как работают вычисления в C/C++ и как ведут себя компиляторы.
Но на самом деле они этого не знают. Если бы знали, они бы не говорили всякие глупости. Обычно глупости выглядят как-то так (собирательный образ):
Вы несете теоретический бред. Ну да, формально переполнение 'int' приводит к неопределенному повреждению. Но это не более чем болтовня. На практике, всегда можно сказать что получится. Если к INT_MAX прибавить 1, мы получим INT_MIN. Быть может и есть какие-то экзотические архитектуры, где это не так, но мой компилятор Visual C++ / GCC выдают корректный результат.
Так вот, сейчас я без всякой магии на простом примере продемонстрирую неопределённое поведение и не на какой-то волшебной архитектуре, а в Win64-программе.
Достаточно собрать приведённый выше пример в режиме Release x64 и запустить его. Программа перестанет падать, а сообщение «the last array element contains 0» выдано не будет.
Неопределенное поведение здесь проявило себя следующим образом. Массив будет полностью заполнен, не смотря, на то, что тип 'int' недостаточен для индексации всех элементов массива. Для тех, кто не верит, предлагаю взглянуть на ассемблерный код:
int index = 0;
for (size_t i = 0; i != Count; i++)
000000013F6D102D xor ecx,ecx
000000013F6D102F nop
array[index++] = char(i) | 1;
000000013F6D1030 movzx edx,cl
000000013F6D1033 or dl,1
000000013F6D1036 mov byte ptr [rcx+rbx],dl
000000013F6D1039 inc rcx
000000013F6D103C cmp rcx,rdi
000000013F6D103F jne main+30h (013F6D1030h)Вот оно проявление неопределенного поведения! И никаких экзотических компиляторов. Это VS2015.
Если заменить 'int' на 'unsigned' неопределённое поведение исчезнет. Массив будет заполнен только частично и в конце будет выдано сообщение «the last array element contains 0».
Ассемблерный код, когда используется 'unsigned':
unsigned index = 0;
000000013F07102D xor r9d,r9d
for (size_t i = 0; i != Count; i++)
000000013F071030 mov ecx,r9d
000000013F071033 nop dword ptr [rax]
000000013F071037 nop word ptr [rax+rax]
array[index++] = char(i) | 1;
000000013F071040 movzx r8d,cl
000000013F071044 mov edx,r9d
000000013F071047 or r8b,1
000000013F07104B inc r9d
000000013F07104E inc rcx
000000013F071051 mov byte ptr [rdx+rbx],r8b
000000013F071055 cmp rcx,rdi
000000013F071058 jne main+40h (013F071040h)Примечание про PVS-Studio
Анализатор PVS-Studio напрямую не диагностирует переполнение знаковых переменных. Это неблагодарное занятие. Почти невозможно предсказать, какие значения будут иметь те или иные переменные и произойдет переполнение или нет. Однако, он может заметить в этом коде ошибочные паттерны, которые он связывает с «64-битными ошибками».
На самом деле никаких 64-битных ошибок нет. Есть просто ошибки, например, неопределённое поведение. Просто эти ошибки спят в 32-битном коде и проявляют себя в 64-битном. Но если говорить про неопределённое поведение, то это не интересно, и никто покупать анализатор не будет. Да ещё и не поверят, что могут быть какие-то проблемы. А вот если анализатор говорит, что переменная может переполниться в цикле, и что это ошибка «64-битная», то совсем другое дело. Profit.
Приведенный выше код PVS-Studio считает ошибочным и выдаёт предупреждения, относящиеся к группе 64-битных диагностик. Логика следующая: в Win32 переменные типа size_t являются 32-битными, массив на 5 гигабайт выделить нельзя и всё корректно работает. В Win64 стало много памяти, и мы захотели работать с большим массивом. Но код отказал и даёт сбой. Т.е. 32-битный код работает, а 64-битный нет. В рамках PVS-Studio это называется 64-битной ошибкой.
Вот диагностические сообщения, которые выдаст PVS-Studio на код приведённый в начале:
- V127 An overflow of the 32-bit 'index' variable is possible inside a long cycle which utilizes a memsize-type loop counter. consoleapplication1.cpp 16
- V108 Incorrect index type: array[not a memsize-type]. Use memsize type instead. consoleapplication1.cpp 16
Подробнее на тему 64-битных ловушек предлагаю познакомиться со следующими статьями:
- Разработка 64-битных приложений на языке Си/Си++
- 64-битный конь, который умеет считать
- Коллекция примеров 64-битных ошибок в реальных программах
- C++11 и 64-битные ошибки
Корректный код
Чтобы всё работало хорошо, надо использовать подходящие типы данных. Если вы собираетесь обрабатывать большие массивы, то забудьте про int и unsigned. Для этого есть типы ptrdiff_t, intptr_t, size_t, DWORD_PTR, std::vector::size_type и так далее. В данном случае пусть будет size_t:
size_t index = 0;
for (size_t i = 0; i != Count; i++)
array[index++] = char(i) | 1;Вывод
Если конструкция языка С++ вызывает неопределённое поведение, то она его вызывает и не надо с этим спорить или предсказывать как оно проявит себя. Просто не пишите опасный код.
Есть масса упрямых программистов, которая не хочет видеть ничего опасного в сдвигах отрицательных чисел, переполнении знаковых чисел, сравнивании this c нулём и так далее.
Не будьте в их числе. То, что программа сейчас работает, ещё ничего не значит. Как проявит UB предсказать невозможно. Ожидаемое поведение программы — это всего лишь один из вариантов UB.
Комментарии (43)
lany
05.02.2016 14:36Я, может, немного затупляю, но почему с unsigned нет undefined behavior?
* Edit: а, тупо в спецификации так написано? Ок… А почему такая разница между signed/unsigned?
Halt
05.02.2016 14:38+5Потому что переполнение unsigned значений разрешено в стандарте. Оно все равно будет некорректным с точки зрения программиста, но определенным с точки зрения компилятора.
lany
05.02.2016 15:05-1Ну да, я понял, что разрешено. А почему такое различие между казалось бы схожими типами? Чем это обусловлено?
vladon
05.02.2016 16:19Андрей, планируете ли вы делать проверки на соответствие Cpp Core Guidelines?
Andrey2008
05.02.2016 16:33+7Я смотрел этот документ и даже сделал себе пару пометок, о том, что можно добавить в анализатор.
Но в целом, ответ нет. Обоснование:
1. Многие рекомендации весьма размыты. Непонятно, что собственно должен сообщать анализатор кода, куда указывать и что рекомендовать.
2. Там описано много плохих паттернов. Но далеко не каждый плохой паттерн — это ошибка. Нам не нравится выдавать просто рекомендации. От этого анализатор быстро портится. Посмотрит человек первые 20 предупреждений, а там что-то в духе: класс плохо назван, локальных переменных много и т.п. Скажет — ага, понятно. И удалит анализатор. Хотя среди всего этого мусора были полезные предупреждения. Поэтому мы ориентируемся именно на поиск ошибок, а не на выдачу рекомендаций по улучшению.leremin
05.02.2016 19:12Вел один проект, который собирался с полным выводов ворнингов в GCC: pedantic, wall, weffc++… Там во многих местах компилятор ругался на ерунду. Я просто дефайнами отключил ворнинги в нужных участках кода. Почему не поступать как-нибудь в этом роде?
Andrey2008
05.02.2016 19:58+3Отключить то не проблема. И, кстати, в PVS-Studio есть масса механизмов для этого. Можно писать комментарии в специальных местах, можно использовать глобальные комментарии для макросов и иных повторяющихся конструкций, есть специальный #ifdef, есть база разметки неинтересных сообщений (для быстрого внедрения анализатора), и так далее.
Но всё это не решает проблему знакомства с инструментом. А он крайне важна. Мы знаем это и на своем опыте знаем, и у Coverity в статье читали. Если потенциальный пользователь в первых 10 сообщениях не увидит настоящую ошибку, то с большой вероятностью он не будет использовать инструмент. Но даже если он продолжит, дело плохо. У человека снижается внимательность. Если 15-ое сообщение укажет на ошибку, он с большой вероятностью посчитает его ложным.
Можно конечно по умолчанию отключать малоприоритетное. Что кстати мы и делаем в демонстрационной версии. Но в целом проблема есть и очень большая. Никто ведь не мешает включить всё на максимум, когда мы выдаём пробный ключ для более плотного изучения. Все почему-то сразу лезут в настройки и включают всё что могут (например, заказные диагностики). Не знаю, почему так происходит. Но сам не раз наблюдал такое поведение на подопытных кроликах. :)
datacompboy
05.02.2016 20:11+1Расскажу свой опыт, как я играюсь с разными анализаторами: я включаю всё-всё-всё, прогоняю, складываю в лог.
Результат отсортирую и разбиваю по каждой отдельной проверке.
Затем их отсортировал по размеру от маленьких к большим (по результатам).
С мелкими понятно — их проверяю целиком, и веду список «реальные» и «нереальные», раскладывая по разным папкам.
Всё, что в «нереальных» — просто исключаю фильтрами на будущее.
Всё, что нашлось в реальных — правлю, примерно прикидывая % ложных, чтобы оценить когда надо править код, а когда подавлять.
Например, на PVS у меня получилось:
DISABLE_CHECKS=«V122|V813|V128|V690|V112|V616»
Может оно и полезно, но не в этой жизни.
При этом никакого негатива вышеуказанные мне не доставляли, просто они не применимы в нашей реальности. И если бы их от меня анализатор прятал — я бы скорее обиделся.
… вот только в итоге реально было 2 фикса, и мне не удалось найти хорошего примера в истории изменений, где бы анализатор смог найти что-то, что не было бы поймано на первом же ревью и/или тестами.
samo-delkin
06.02.2016 07:44Этот код корректно работает, если собрать 32-битную версию программы.
Этот код точно такой же некорректный и для 32-битной версии.
Надо всегда помнить, что int не может быть короче short int'а (по стандарту C89), но легко может быть равен ему.
Поэтому перебор миллиарда символов там тоже может привести к переполнению на ЛЮБОМ компиляторе.
xiWera
06.02.2016 14:06-7Так много человек незамечают, что пример в самом начале статьи использовать не совсем верно… И так мало человек отвечают правильно на вопрос когда его кто-то задает на собеседованиях, в том числе сами «собеседователи»…
Дело в том, что это выражение ( i = i++ + ++i) всегда определЁнно, хотя порядок вычисления операндов сложения не определён :)
например, пусть в i у нас 1, сначала вычисляется левый операнд:
1 + 3 = 4
сначала вычисляется правый операнд:
2 + 2 = 4
и тд для всех целыхkhim
06.02.2016 23:44+3Для того, чтобы понять где и почему вы неправы нужно немного знать про то как устроен не только C, но и ассемблер. Вот сколько у вас тут операций, по вашему происходит? Три? Как бы не так: восемь (а может и больше: скомпилируйте программу с -O0 — сами увидите)!
i++
A1. Прочитать значение i из памяти в регистр ?.
A2. Увеличить значение регистра ?.
A3. Положить значение в память из регистра ?.
++i:
B1. Прочитать значение i.
B2. Увеличить значение регистра ?.
B3. Записать значение регистра ? в память.
i++ + ++i:
C1. Сложить значение регистра ? после шага A1, но до шага A2 со значением регистра ? после шага B2, положив значение в регистр ?.
C2. Записать значение ? в память.
Никто не мешает компилятору, скажем, взять и выполнить операции в такой последовательности:
A1, B1, B2, C1, С2, B3, A2, A3.
В результате i будет равно 2.
Обычно компиляторы в современных CPU-архитектурах таких вещей не делают, так как непонятно что на этом можно выиграть, но если у вас есть, скажем, автоинкрементирующаяся память (как на PDP-7 и PDP-8, то подобные вещи вполне возможны.
Соотвественно в переносимой программе их быть не должно и компилятор имеет право на это опираться.xiWera
07.02.2016 16:35-4Нет. Ваше утверждение эквивалетно, что неопределено уже a=a+a. А это не так. В данном примере неопределенно только выполнение поярдка вычисления левого и правого операнда для операции сложения. Приравнивание уже вполне определенно будет принимать значение операции сложения. Именно поэтому хотя порядок неопределен, значение определено.
datacompboy
07.02.2016 17:31+2Нет, не эквивалентно, так как есть Sequence point перед присвоением результата.
В случае же с пре/пост инкрементами внутри вычисления их нет.
khim
07.02.2016 17:40+3В данном примере неопределенно только выполнение поярдка вычисления левого и правого операнда для операции сложения.
В данном примере не определено в какой последовательности произойдёт отставка трёх операций. Реализация, которая «выносит» все пост-и-прединкременты из выражений (и выполняет все принкременты до «основного» выражения, а все постинкременты — после) — абсолютно законна.
Почитайте хотя бы википедию.
datacompboy
Интересный подход. А как это так компилятор int (который, емнимс, на винде = 32бита) легко положил в 64битный регистр и сравнивает напрямую не ругаясь?!
Это обычные оптимизации, или мегажесть?
Andrey2008
Это неопределённое поведение, возникшее из-за переполнения signed integer. Проявляется в Release. Собственно, про это статья и написана :)
datacompboy
gcc -O2 a.cpp
a.cpp: In function ‘int main()’:
a.cpp:16:18: warning: iteration 2147483647ul invokes undefined behavior [-Waggressive-loop-optimizations]
array[index++] = char(i) | 1;
^
a.cpp:15:3: note: containing loop
for (size_t i = 0; i != Count; i++)
^
При этом результат тот же в релизе с -O2
.L3:
movl %edx, %ecx # i, tmp90
orl $1, %ecx #, tmp90
movb %cl, (%rbx,%rdx) # tmp90, MEM[base: array_7, index: i_25, offset: 0B]
addq $1, %rdx #, i
cmpq %rax, %rdx # tmp95, i
jne .L3 #,
movabsq $5368709119, %rax #, tmp92
cmpb $0, (%rbx,%rax) #, MEM[(char *)array_7 + 5368709119B]
Без оптимизаций или с O1 — падает с segmentation fault, то есть честно 32бита выдерживает.
Выходит, релиз в VCC включает аггрессивные оптимизации, но совершенно молча.
Halt
Компилятор считает, что неопределенного поведения в программе нет. Точка.
В случае int и инкремента операция выполняется из предположения, что переполнения регистра не произойдет (иначе было бы неопределенное поведение, которого быть не должно).
Значит, компилятор имеет полное право разместить переменную в 64 битном регистре, поскольку старшие биты не будут иметь значения в случае хранения 32 битного значения.
P.S.: Если есть время, могу посоветовать послушать мой доклад на конференции C++ Siberia, где затрагивались в том числе и эти вопросы с позиции разработчика компилятора.
datacompboy
А что тогда «warning: iteration 2147483647ul invokes undefined behavior» означает?
Я к тому, что UB есть, но при проведении аггрессивных оптимизаций компилятор вправе трактовать любые UB несущественными и оптимизировать считая что их нет — но поведение GCC с ворнингом на эту тему мне больше нравится.
Halt
Именно это. Компилятор намекает, что такое значение спровоцирует неопределенное поведение, но сам исходит из предположения, что программист не дурак и не рассчитывает на такой сценарий.
Предворяю вопрос типа: «ну ёлки палки! варнинг он дать додумался, а правильно код скомпилировать не может! как так?». Это несколько разные вещи: дать варнинг и написать код в соответствии со стандартом.
Проблема в том, что во-первых, далеко не всегда можно сказать, существует ли в заданном коде UB или нет. Во-вторых, задача компилятора генерировать корректный и быстрый код, а подобные проверки существенно усложнили бы логику компилятора, по прежнему не обеспечив безопасности, ибо см. пункт первый.
Разработчики стоят перед выбором: писать условно-безопасный код или писать быстрый. Исторически, языки семейства Си идут по пути скорости.
datacompboy
Вот кстати нет. GCC совершенно честно и правильно поступает с -O1: ворнинга нет, переменная signed 32 bit, идёт переполнение.
С -O2 сообщает об UB, и транслирует как посчитал нужным, на что имеет право.
У меня жалоба на VC — она не пожаловалась, но оттранслировала себе на уме. В том числе, следует помнить, что «int» это «не меньше 32 бит» а не «ровно 32 бита» — поэтому решение вполне корректное, но UB.
Halt
Проблема в том, что компиляторы работают с кодом очень отдаленно напоминающем исходный. После разбора AST и десятка-другого преобразований с удалением лишних деталей и инлайнингом нелишних, мы получаем кашу, которая не имеет ничего общего с изначальной программой. Она будет работать эквивалентно (в меру понимания компилятора) и только.
Потом, чтобы дать нормальный варнинг, надо хотя бы иметь представление о месте в коде, которое его провоцирует. Если код прошел через тридевять земель, пару десятков специализаций шаблонов и инлайнинг, компилятор уже сам не имеет понятия о том, какая реально строка его породила.
Если же протаскивать всю эту информацию через весь компилятор, то мы опять же обретаем лютый геморрой при довольно скромном профите.
Советую почитать вот эти статьи из блога LLVM:
khim
Это вам повезло просто. GCC 4.8.4 ничего не выдаёт, программа не падает.
Я уже писал: неопределённое поведение — оно вообще инструкцией для программистов, а не для разработчиков компилятора, является.
Компилятор исходит из аксиомы: «данная мне на вход программа никогда не вызывает неопределённого поведения». Выяснить правда это или нет он не может (всё упрётся в проблему остановки), потому поступает так же как и при нарушнии, скажем, ODR: пусть будет, как будет, ведь как-нибудь да будет, никогда ещё не было, чтобы никак не было.
Пожаловаться каждый раз, когда компилятор полагается на то, что в программе нет UB — раз плюнуть, но вы только представьте что будет, если каждый раз, когда компилятор какое-нибудь
if (a + 3 > b + 2)превращает в(a + 1 > b)он будет жаловаться. Вы же с ума сойдёте!