Вашему вниманию предлагается восьмая часть электронной книги, которая посвящена неопределённому поведению. Книга не является учебным пособием и рассчитана на тех, кто уже хорошо знаком с программированием на C++. Это своего рода путеводитель C++ программиста по неопределённому поведению, причём по самым его тайным и экзотическим местам. Автор книги — Дмитрий Свиридкин, редактор — Андрей Карпов.
Определить, завершается или не завершается программа на конкретном наборе данных — алгоритмически невозможно в общем случае.
Но в стандартах C и C++ зачем-то сказано, что валидная программа должна либо гарантированно завершаться, либо гарантированно производить обозреваемые эффекты: запрашивать ввод-вывод, взаимодействовать с volatile-переменными и подобное. А иначе поведение программы неопределённое. Так что "правильные" компиляторы C++ настолько суровы, что способны решать алгоритмически неразрешимые задачи.
Если в программе есть бесконечный цикл, и компилятор решил, что этот цикл не имеет обозреваемых эффектов, то он не имеет смысла и может быть выброшен.
Занятный пример — таким образом можно "опровергнуть" великую теорему Ферма:
#include <iostream>
int fermat () {
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;
}
int main () {
if (fermat()) {
std::cout <<
"Fermat's Last Theorem has been disproved.\n";
} else {
std::cout <<
"Fermat's Last Theorem has not been disproved.\n";
}
return 0;
}
Собрав с помощью GCC 14.1 и ключом -O3, уверенно получим: Fermat's Last Theorem has been disproved.
Компилятор увидел, что единственный выход из цикла — return 1. У цикла нет никаких видимых эффектов, так что компилятор просто заменил его на return 1.
Если же попытаться узнать, что за тройку "нашла" программа, цикл вернётся.
В constexpr-контексте получим ошибку компиляции. Компилятор остановится при превышении определённой глубины анализа: 'constexpr' loop iteration count exceeds limit of 262144 (use '-fconstexpr-loop-limit=' to increase the limit).
Может показаться, будто проблема в том, что условие продолжения цикла не зависит от его тела. Но и в исправленной версии цикл исчезает:
int fermat() {
const int MAX = 1000;
int a=1,b=1,c=1;
while ((a*a*a) != ((b*b*b)+(c*c*c))) {
a++;
if (a>MAX) {
a=1;
b++;
}
if (b>MAX) {
b=1;
c++;
}
if (c>MAX) {
c=1;
}
}
return 1;
}
Даже если в цикле будут операции I/O, он всё равно может исчезнуть, если компилятор увидит, что эти операции от цикла не зависят.
int fermat () {
const int MAX = 1000;
int a=1,b=1,c=1;
while (1) {
if ( (a*a*a) == (b*b*b) + (c*c*c) ) {
std::cout << "Found!\n";
return 1;
}
a++;
if (a>MAX) {
a=1;
b++;
}
if (b>MAX) {
b=1;
c++;
}
if (c>MAX) {
c=1;
}
}
return 0;
}
Собираем с помощью GCC 14.1 -O3 -std=c++20 и получаем:
Found!
Fermat's Last Theorem has been disproved.
Так что предполагать, что программа в каких-то случаях должна зацикливаться, и строить под эти случаи тесты в C и C++ просто так нельзя. Отлаживаться принтами с наскоку тоже нельзя. И строить тесты, проверяющие, что программа не зацикливается, также может оказаться бесполезно.
Многие алгоритмы очень красиво и компактно записываются в рекурсивной форме: сортировки, обходы графов, строковые алгоритмы.
Однако рекурсия требует места для хранения промежуточного состояния — на куче или в стеке. Конечно, есть хвостовая рекурсия, которая естественным образом может быть оптимизирована в цикл. Но это не гарантировано стандартом. Да и не всегда рекурсия именно хвостовая.
Stack Overflow не совсем неопределённое поведение, но точно не то, что хочется видеть на боевом стенде. Потому в серьёзных приложениях предпочитают итеративные алгоритмы рекурсивным. Если, конечно, нет гарантии, что глубина рекурсии мала.
В деле искоренения рекурсии из своей программы нужно быть очень внимательным. И не только в корректной имплементации алгоритмов. Помимо алгоритмов, рекурсивными могут быть и структуры данных. И тут в игру вступают RAII, правила нуля, порядок вызовов деструкторов и noexcept.
struct Node {
int value = 0;
std::vector<Node> children;
};
Такая структура совершенно законна для определения дерева, она компилируется и работает. И может быть удобнее, чем вариант с умными указателями.
Нам не нужно никак вручную управлять ресурсами, вектор позаботится обо всем самостоятельно. Пользуемся "правилом нуля" и не пишем ни деструктор, ни конструктора копирования, ни оператора перемещения/копирования, ничего. Красота!
Однако деструктор, сгенерированный компилятором, будет рекурсивным! И при слишком большой глубине дерева мы получим переполнение стека.
Хорошо, пишем свой деструктор: нам нужна очередь, чтобы обойти вершины дерева... А очередь — это аллокация памяти. А аллокация памяти — операция, бросающая исключения. И вот у нас деструктор будет бросать исключения. Что совсем нехорошо.
Можно написать деструктор без аллокаций и рекурсии, но его алгоритмическая сложность будет квадратичной:
Для обычного связанного списка проблема также сохраняется:
struct List {
int value = 0;
std::unique_ptr<List> next;
};
Но в этом случае рекурсия является хвостовой, и можно надеяться, что оптимизатор справится. Но вы же гоняете тесты и на дебажных сборках, верно?
Так что пишем деструктор, а вместе с ним все остальные специальные методы (в указанном случае — только перемещающие операции):
struct List {
int value = 0;
std::unique_ptr<List> next;
~List() {
while (next) {
// Деструктор всё также рекурсивен,
// но теперь глубина рекурсии — 1 вызов.
next = std::move(next->next);
}
}
List() noexcept = default;
List(List&&) noexcept = default;
List& operator=(List&&) noexcept = default;
};
С рекурсивными структурами данных в C++ нужно быть очень аккуратными. Не просто так в Rust написать их "очевидным" способом тяжело.
Начиная с 11 стандарта, мы можем помечать функции и методы спецификатором noexcept, говоря тем самым компилятору, что эта функция или метод не бросают исключения.
И вроде бы всё хорошо: получив такую информацию, компилятор может не генерировать дополнительные инструкции для обработки раскрутки стека. Бинарники становятся меньше, а программы — быстрее.
Но проблема в том, что этот спецификатор не заставляет компиляторы проверять, что функция действительно не бросает исключений.
Если мы пометим функцию как noexcept, а она возьмёт да и кинет исключение, то произойдёт что-то странное, заканчивающееся внезапным std::terminate.
Так, например, неожиданно перестанут работать try-catch блоки:
void may_throw(){
throw std::runtime_error("wrong noexcept");
}
struct WrongNoexcept {
WrongNoexcept() noexcept {
may_throw();
}
};
// Попытки обернуть в try-catch эту функцию или любой код,
// использующий её — бесполезны.
void throw_smth() {
if (rand() % 2 == 0) {
throw std::runtime_error("throw");
} else {
WrongNoexcept w;
}
}
Собрав этот код с помощью GCC или Clang, получим уверенный access violation:
terminate called after throwing an instance of 'std::runtime_error'
what(): wrong noexcept
Program terminated with signal: SIGSEGV
Может быть очень сложно понять, почему это произошло, если код разнесён по разным единицам трансляции.
В С++ любят экономить на ключевых словах:
Есть спецификатор noexcept(condition). И просто noexcept — синтаксический сахар для конструкции noexcept(true).
А есть предикат noexcept(expr), проверяющий, что выражение expr не кидает исключений по самой своей природе (сложение чисел, например) или же помечено как noexcept.
И вместе они порождают конструкцию для условного навешивания noexcept:
void fun() noexcept(noexcept(used_expr))
void may_throw(){
throw std::runtime_error("wrong noexcept");
}
struct ConditionalNoexcept {
ConditionalNoexcept() noexcept(noexcept(may_throw())) {
may_throw();
}
};
// Теперь с этой функцией всё хорошо.
void throw_smth() {
if (rand() % 2 == 0) {
throw std::runtime_error("throw");
} else {
ConditionalNoexcept w;
}
}
Чтобы избежать проблем, нужно всегда и везде использовать условный noexcept с аккуратной проверкой каждой используемой функции. Либо вовсе не использовать noexcept. Но во втором случае стоит помнить, что операции перемещения, а также swap, должны помечаться как noexcept (и быть действительно noexcept!) для эффективной работы со стандартными контейнерами.
Не забывайте писать негативные тесты. Без них можно проморгать появление ложного noexcept и получить std::terminate на боевом стенде.
Также обратите внимание на тонкий и неприятный нюанс: если вам ну очень сильно надо кидать исключения из деструктора, обязательно явно пишите в его объявлении noexcept(false). По умолчанию все ваши функции и методы помечены неявно noexcept(false), но для деструкторов в C++ сделано исключение. Они неявно помечены noexcept(true). Так что:
struct SoBad {
// invoke std::terminate
~SoBad() {
throw std::runtime_error("so bad dtor");
}
};
struct NotSoBad {
// OK
~NotSoBad() noexcept(false) {
throw std::runtime_error("not so bad dtor");
}
};
Переполнение буфера и выход за границы массива — злобные ошибки и причины не только простых падений программ, но дыр в безопасности, позволяющих получать доступ куда не следует или даже исполнять произвольный код.
В стандартной библиотеке C, доставшейся C++ по наследству, великое множество дырявых функций, позволяющих добиться переполнения буфера, если программист не удосужился проверить все возможные и невозможные варианты:
И ещё многие другие, преимущественно работающие со строками, функции.
Эти функции доставляли и продолжают доставлять проблемы. Некоторые компиляторы (MSVC) по умолчанию откажутся собирать ваш код, если увидят одну из них. Другие будут менее заботливыми и, возможно, выдадут предупреждение. По крайней мере, про функцию gets уж точно. Если с другими функциями у программиста есть возможность уберечься (проверка до вызова; у scanf можно указать размер для ограничения строки), то с gets — без вариантов.
Для большинства старых небезопасных "сишных" функций сейчас есть "безопасные" аналоги с размерами буферов. Часть из них не стандартизирована, часть стандартизирована. Всё это породило огромное количество костылей с макроподстановками для работы со всем этим зоопарком. Но сейчас не об этом.
Проверки размеров — дополнительная работа. Генерировать под них инструкции — замедлять программу. Тем более программист мог всё проверить сам. Так что в C и С++ обращение за границы массива хоть на запись, хоть на чтение влечёт неопределённое поведение. И дыры в безопасности могут зарастать различными спецэффектами.
В большинстве случаев, если нарушение размеров происходит не всегда, попытка прочитать за границами массива проявится либо получением мусорных результатов, либо простой и так всеми любимой ошибкой сегментации (SIGSEGV).
Но иногда начинается веселье:
const int N = 10;
int elements[N];
bool contains(int x) {
for (int i = 0; i <= N; ++i) {
if (x == elements[i]) {
return true;
}
}
return false;
}
int main() {
for (int i = 0; i < N; ++i) {
std::cin >> elements[i];
}
return contains(5);
}
Эта программа, собранная GCC c оптимизациями, всегда "найдёт" пятёрку в массиве. Независимо от того, какие числа будут введены. Причём никаких предупреждений ни Clang, ни GCC не выдают. Ну хотя бы PVS-Studio ругается:
V557 Array overrun is possible. The value of 'i' index could reach 10.
Происходит такой спецэффект из следующих соображений:
1. Компиляторы вольны считать, что UB в программах не бывает.
2. В этом цикле будет обращение за границы массива, а значит UB.
for (int i = 0; i <= N; ++i) {
if (x == elements[i]) {
return true;
}
}
3. Но, поскольку UB не бывает, до N+1 итерации дело дойти не должно!
4. Значит, мы выйдем из цикла по return true.
5. А значит вся функция contains — это один return true. Оптимизировано!
Или вот, конечный цикл становится бесконечным:
const int N = 10;
int main() {
int decade[N];
for (int k = 0; k <= N; ++k) {
printf("k is %d\n",k);
decade[k] = -1;
}
}
И фокус здесь не менее хитрый:
В этих примерах, конечно, сразу же должен броситься в глаза "<=" в заголовках циклов. Но и с более привычным "<" тоже можно изобрести себе проблемы. Константа N, например, может быть не связана с размером массива. И всё, приехали.
В дружелюбных и безопасных языках вы получите ошибку во время выполнения. А ещё панику или исключение. В C++ же всё надо проверять, проверять и ещё раз проверять самим:
Да, вы не ослышались. И глаза вам не врут. И я не сошёл с ума. И вы тоже. Скорее всего.
C++ — уникальный язык. В его стандарте есть описание того, что в языке почти наверняка не появится. Есть поддержка сборщика мусора, но самого сборщика мусора нет. И поддержка эта сделана самым естественным для C++ способом: введением неопределённого поведения.
Неопределённое поведение возникает в следующей ситуации:
Ну, действительно, если у нас когда-нибудь будет сборщик мусора, то уничтожение последнего указателя на объект позволит сборщику мусора этот объект удалить. А значит последующий доступ к этому объекту ни к чему хорошему не приведёт. Сборщик мусора может его успеть удалить. А может не успеть. Вот вам и UB.
Но у нас нет! Ни один из компиляторов его не поддерживает! А стандарт поддерживает.
Так что, если вы, например, храните в младших битах указателя (а это иногда можно делать из-за выравнивания) какую-то метаинформацию, экономя память, скорее всего, в вашей программе есть UB, связанное с поддержкой сборщика мусора. Оно наверняка никогда не выстрелит, но оно есть.
template <class T>
struct MayBeUninitialized {
static_assert(alignof(T) >= 2);
MayBeUninitialized() {
// Выделяем сырую память с помощью явного вызова operator new.
// Вся эта ерунда с поддержкой сборщика мусора описана
// только для глобального operator new. std::malloc,
// placement new и прочие не участвуют.
ptr_repr_ = reinterpret_cast<uintptr_t>(
operator new (sizeof(T),
std::align_val_t(alignof(T))));
// Единственный указатель только был создан и
// сразу же уничтожился.
ptr_repr_ |= 1; // set unitialized flag
}
~MayBeUninitialized() {
Deinit();
operator delete(GetPointer(), sizeof(T),
std::align_val_t(alignof(T)));
}
void Deinit() {
if (!IsInitialized()) {
return;
}
GetPointer()->~T();
}
bool IsInitialized() const {
return !(ptr_repr_ & 1);
}
void Set(T x) {
Deinit();
new (GetPointer()) T(std::move(x));
// drop unitialized flag
ptr_repr_ &= (~static_cast<uintptr_t>(1));
}
const T& Get() const {
if (!IsInitialized()) {
throw std::runtime_error("not init");
}
return *GetPointer(); // UB
}
private:
T* GetPointer() const {
constexpr auto mask = ~static_cast<uintptr_t>(1);
auto ptr = reinterpret_cast<T*>(ptr_repr_ & mask);
// Восстановили указатель. Но разыменование его — UB.
return ptr;
}
uintptr_t ptr_repr_;
};
Устраняется такое недоразумение с бессмысленным для текущего положения дел в C++ неопределённым поведением при помощи пары функций declare_reachable и undeclare_reachable:
MayBeUninitialized() {
void* ptr = operator new (sizeof(T),
std::align_val_t(alignof(T)));
std::declare_reachable(ptr);
ptr_repr_ = reinterpret_cast<uintptr_t>(ptr);
// Единственный указатель только был создан и
// сразу же уничтожился, но мы пометили память под ним
// достижимой, чтобы отвадить мифический сборщик мусора.
ptr_repr_ |= 1; // set unitialized flag
}
~MayBeUninitialized() {
Deinit();
void* ptr = GetPointer();
std::undeclare_reachable(ptr);
operator delete (ptr, sizeof(T), std::align_val_t(alignof(T)));
}
Эти функции в настоящее время ничего не делают. Они нужны только для формального следования букве стандарта.
Если вы верите, что когда-нибудь в C++ появится сборщик мусора, будьте любезны пользоваться этими прекрасными функциями, чтобы ваша программа оставалась корректной и в далёком будущем.
Если не верите, то можете про них забыть. Пожалуй, это единственное UB, которое нигде и никак не проявляется. И не проявится. Скорее всего не проявится. Даже есть предложения удалить эту совершенно дурную для C++ "фичу".
Надо понимать, что сам по себе сборщик мусора для C++ не является чем-то сверхъестественным. На C и C++ написаны, например, сборщики мусора для JVM. Никто не мешает задействовать их же в C++-программах: просто используем альтернативные функции для выделения памяти. С их помощью даже можно переопределить поведение операторов new и delete. Но очень мало какой код на C++ пишется с предположением, что под этими операторами работает сборщик мусора.
Проверить, не запустили ли вашу программу в светлом мире со сборщиком мусора, можно, вызвав функцию get_pointer_safety. Она возвращает одно из трёх значений:
int main() {
switch (std::get_pointer_safety())
{
case std::pointer_safety::strict:
std::cout << "strict" << std::endl;
break;
case std::pointer_safety::relaxed:
std::cout << "relaxed" << std::endl;
break;
default:
std::cout << "preferred" << std::endl;
}
}
Отмечу, что при запуске этого кода под valgrind-3.15.0 для Ubuntu 20.04 (x86_64) выводимое сообщение (relaxed) никак не меняется.
Автор — Дмитрий Свиридкин
Более восьми лет работает в сфере коммерческой разработки высокопроизводительного программного обеспечения на C и C++. С 2019 по 2021 год преподавал курсы системного программирования под Linux в СПбГУ и практики C++ в ВШЭ. В настоящее время — Software Engineer в AWS (Cloudfront), занимается системной и embedded-разработкой на Rust и C++ для edge-серверов. Основная сфера интересов — безопасность программного обеспечения.
Редактор — Андрей Карпов
Более 15 лет занимается темой статического анализа кода и качества программного обеспечения. Автор большого количества статей, посвящённых написанию качественного кода на языке C++. С 2011 по 2021 год удостаивался награды Microsoft MVP в номинации Developer Technologies. Один из основателей проекта PVS-Studio. Долгое время являлся CTO компании и занимался разработкой С++ ядра анализатора. Основная деятельность на данный момент — управление командами, обучение сотрудников и DevRel активности.