C2018/Неопределённое поведение

Материал из iRunner Wiki

What Every C Programmer Should Know About Undefined Behavior

Понятие

Неопределённое поведение (undefined behaviour, UB) — свойство некоторых языков программирования (наиболее заметно в C), программных библиотек и аппаратного обеспечения в определённых маргинальных ситуациях выдавать результат, зависящий от реализации компилятора (библиотеки, микросхемы) и случайных факторов наподобие состояния памяти.

Спецификация не определяет поведение языка в любых возможных ситуациях, а говорит: «при условии А результат операции Б не определён». Допускать такую ситуацию в программе считается ошибкой; даже если на некотором компиляторе программа успешно выполняется, она не будет кроссплатформенной и может отказать на другой машине, в другой ОС или при других настройках компилятора.

При UB результат выполнения программы может быть любым: она аварийно завершиться, может отформатировать вам диск…

Причины

Все знают, что C — это низкоуровневый язык. Все знают, что это не переносимый язык (это не Java и не JavaScript). Однако есть непонимание места C (и стандартов ANSI C и ISO C) в этом мире.

Язык C был создан для главной цели — для написания операционной системы UNIX. То есть для низкоуровневого кода. Однако важно, что UNIX — не только многозадачная и многопользовательская система, но она ещё и переносимая.

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

Разработчики UNIX (и C) пошли другим путём. Язык они сделали непереносимым, а вот написанный на нём UNIX — очень даже переносимым. Как этого добились? Запретами. Сдвиг на сильно большие величины на разных процессорах даёт разные результаты? Значит, использовать такие сдвиги в программе нельзя. Один процессор при переполнении выбрасывает исключения, а другой «тихо» порождает отрицательное число? Значит использовать такую конструкцию в программе нельзя. И так далее. Таких правил, призванных обеспечить переносимость кода, накопились десятки и сотни.

Заметьте: эти правила — ориентированы на программиста, ни в коем случае не на разработчика компилятора. Это программисту нужен переносимый код, не компилятору. А для компилятора — эти правила, наоборот, дают простор для реализации. Если у нас сложение порождает отрицательные числа, а вычитание — бросает исключение, то что нам делать? Да неважно: программист же должен всё равно позаботится о том, чтобы такого не происходило.

Именно это приводит к тому, что UNIX (и его «идейный наследник» Linux) поддерживают совершенно невероятное число платформ. И многие программы, написанные на этом непереносимом языке, тоже работают в куда большем числе мест, чем программы написанные «на истинно переносимых языках» типа С# или Java. Дело в том, что переносимость в случае использования C# или Java возлагается в первую очередь на компилятор, а вот в C — на программиста. И если программист всё делает аккуратно, то программа на C будет работать.

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

В чём плюсы UB

Только тем, что упрощает работу компилятора и позволяет ему генерировать очень эффективный код.

В чём минусы UB

Обычно нельзя доверять программисту, что в его коде нет UB. Иногда гарантии надёжности важнее небольшого прироста скорости (особенно если данные приходят извне от непроверенных источников, например в веб-сервере или браузере).

Примеры

Чтение из неинициализированных переменных

Локальные переменные на стеке по умолчанию не инициализированы. Память, которую выделяет malloc, также не инициализирована.

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

Переполнение знаковых целых типов

Не гарантируется, что INT_MAX+1 даст INT_MIN.

Такая программа:

#include <limits.h>
#include <stdio.h>
 
int main (void)
{
  printf ("%d\n", (INT_MAX+1) < 0);
  return 0;
}

согласно стандарту может напечатать

0

или

1

или

42

или отформатировать жёсткий диск. И не важно, что вы запускаете это на x86, где для хранения отрицательных чисел используется дополнительный код, а инструкция ADD одна и та же для знаковых и беззнаковых. Стандарт ничего не гарантирует.

Это даёт основание для многих оптимизаций.

  • x + 1 > x всегда истинно,
  • x * 2 / 2 всегда равно x,
  • цикл вида for (i = 0; i <= N; ++i) { ... } всегда конечен и делает N+1 итерацию, и не нужно рассматривать частные случаи типа N == INT_MAX.

Для беззнаковых целых гарантируется переполнение "с заворотом".

Битовые сдвиги на недопустимые значения

Сдвиги uint32_t на 32 и более бит — неопределённое поведение.

Например, процессор x86 при сдвигах 32-битного числа от величины сдвига берёт только младшие пять бит, поэтому сдвиг на 32 эквивалентен сдвигу на 0.

Разыменование нулевого указателя

Это неопределённое поведение.

  • Не гарантируется, что программа упадёт.
  • Если на какой-то платформе удастся разместить данные в памяти с нулевого адреса, то не гарантируется, что вы получите к ним доступ.

Макрос NULL по-разному определяется в C и C++.

    #ifdef __cplusplus
        #define NULL 0
    #else
        #define NULL ((void *)0)
    #endif

Стандарт гарантирует, что никакой указатель на переменную или функцию не будет равен NULL.

Разыменование некорректного указателя

  • Неинициализированный указатель
  • Указатель на освобождённую с помощью free память
  • Указатель на освобождённую стековую память
  • Выход за границы массива
  • В частности, разыменование указателя, полученного через malloc(0)
  • Адресная арифметика за пределами массива

Чтобы в этом случае реализовать определённое поведение, нудно уметь понимать, корректный ли это указатель и можно ли разыменовывать. Везде с указателями на память нужно было бы хранить границы этой памяти, учитывать в адресной арифметике... Это чрезвычайно накладно.

int arr[4] = {0, 1, 2, 3};
int *p = arr + 5;  // undefined behavior

strict aliasing

Явление aliasing — когда на один и тот же участок памяти указывают несколько разных указателей.

int a;
int* b = &a;
int* c = &a;

У переменной a здесь целых три имени (alias'а), это совершенно нормальный и корректный код.

Оптимизации и restrict

Компилятор обязан понимать и помнить про aliasing не только в таком наглядном случае, но и там, где человек неявно никаких алиасов не предполагает. Например:

void SumIt(int* out, const int* in, size_t count) {
    for (size_t i = 0; i < count; i++) {
        *out += *in++;
    }
}

Компилятору никто не дал гарантий, что out-переменная по адресу *out решительно не пересекается с in-данными по адресу *in. Поэтому на каждой итерации внутреннего цикла происходит запись *out обратно в память, даже при максимальном уровне оптимизации.

    int a[] = { 1, 2, 3 };
 
    int s = 0;
    SumIt(&s, a, 3);
    printf("%d\n", s); // печатает 6
 
    SumIt(&a[2], a, 3);
    printf("%d\n", a[2]);  // печатает 12
0000000000000000 <SumIt>:
   0: 48 85 d2              test   rdx,rdx
   3: 74 19                 je     1e <SumIt+0x1e>
   5: 8b 0f                 mov    ecx,DWORD PTR [rdi]
   7: 31 c0                 xor    eax,eax
   9: 0f 1f 80 00 00 00 00  nop    DWORD PTR [rax+0x0]
  10: 03 0c 86              add    ecx,DWORD PTR [rsi+rax*4]
  13: 48 83 c0 01           add    rax,0x1
  17: 48 39 c2              cmp    rdx,rax
  1a: 89 0f                 mov    DWORD PTR [rdi],ecx
  1c: 75 f2                 jne    10 <SumIt+0x10>
  1e: f3 c3                 repz ret 

В стандарте C99 введено новое ключевое слово — restrict. В стандарт C++ оно так и не было включено.

Ключевое слово restrict позволяет программисту сообщить компилятору, что в течение времени жизни указателя только он сам и непосредственно полученные из него указатели (например "указатель + 1") будут указывать на конкретный блок памяти.

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

void SumIt(int* restrict out, const int* restrict in, size_t count) {
    for (size_t i = 0; i < count; i++) {
        *out += *in++;
    }
}
0000000000000000 <SumIt>:
   0: 48 85 d2              test   rdx,rdx
   3: 74 19                 je     1e <SumIt+0x1e>
   5: 8b 0f                 mov    ecx,DWORD PTR [rdi]
   7: 31 c0                 xor    eax,eax
   9: 0f 1f 80 00 00 00 00  nop    DWORD PTR [rax+0x0]
  10: 03 0c 86              add    ecx,DWORD PTR [rsi+rax*4]
  13: 48 83 c0 01           add    rax,0x1
  17: 48 39 c2              cmp    rdx,rax
  1a: 75 f4                 jne    10 <SumIt+0x10>
  1c: 89 0f                 mov    DWORD PTR [rdi],ecx
  1e: f3 c3                 repz ret 

Видно, что сохранение в память вынесено из цикла.

Замеры показывают, что код ускоряется примерно в 1,5 раза.

Правило strict aliasing

Как видим, устранение алиасинга может вылиться в неплохое улучшение скорости. Из этих соображений в стандарте C99, а следом в C++, ввели "strict aliasing rule".

В режиме strict aliasing компилятор считает, что объекты, на которые показывают указатели «существенно различных» типов, не могут храниться в одном и том же участке памяти, и может использовать это при оптимизациях.

Когда правило не действует?

  • Для указателей типов char* (включая знаковый и беззнаковый). Они могут указывать куда угодно в памяти.
  • Указатели на знаковый и соответствующий беззнаковый тип не считаются существенно различными.
  • Указатели, отличающиеся const-, volatile-квалификаторами, не считаются существенно различными.
  • Допустимо иметь указатель на struct или union и указатель на отдельное поле.

Пример: доступ к битам вещественного числа

Пусть мы хотим реализовать вычисление модуля вещественного числа путём ручного сброса старшего бита.

float funky_float_abs(float a)
{
    unsigned int temp = *(unsigned int *)&a;
    temp &= 0x7fffffff;
    return *(float *)&temp;
}

Этот код не является корректным с точки зрения стандарта C, так как нарушается правило strict aliasing: указатели разных типов int* и float* указывают на одну и ту же память.

Как же добиться нужного эффекта правильно?

Первый способ. Использовать указатели типа char.

float funky_float_abs(float a)
{
    // valid, because it's a char pointer. These are special.
    unsigned char * temp = (unsigned char *)&a;
    temp[3] &= 0x7f;
    return a;
}

Второй способ. Использовать memcpy. Эта функция принимает указатели void*, это разрешает aliasing.

float funky_float_abs (float a)
{
    int i;
    float result;
    memcpy (&i, &a, sizeof (int));
    i &= 0x7fffffff;
    memcpy (&result, &i, sizeof(int));
    return result;
}

Третий способ. Использовать union. Это допускается в соответствии со стандартом C99.

float funky_float_abs (float a)
{
    union 
    {
        unsigned int i;
        float f;
    } cast_helper;
 
    cast_helper.f = a;
    cast_helper.i &= 0x7fffffff;
    return cast_helper.f;
}

Поддержка в компиляторах

В gcc и clang есть возможность отключить strict aliasing rule ключом -fno-strict-aliasing.

Компилятор MSVC не рассчиывает на это правило.

Точки следования

Точка следования (англ. sequence point) — любая точка программы, в которой гарантируется, что все побочные эффекты предыдущих вычислений уже проявились, а побочные эффекты последующих ещё отсутствуют.

Точка следования

Модификация объекта между двумя точками следования более одного раза вызывает UB.

i = i + 1; // OK
i = i++ + 1; // undefined behavior

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

a[i++] = 4; // OK
a[i] = i++; // undefined behavior
printf("%d %d\n", ++n, power(2, n)); // also undefined behavior

Переполнение стека

#include <stdio.h>
 
int main() {
    int n, m;
    long long ans = 0;
    int a[300000], b[300000];
    scanf("%d %d\n", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &a[i], &b[i]);
    }
    return 0;
}

memcpy

  • Использование memcpy для копирования перекрывающихся областей памяти.
  • memcpy(0, 0, 0): даже если копируется ноль байт, указатели обязаны быть валидными.

Деление на 0

Целочисленное деление. Вещественное деление рассматривали на прошлой паре.

int x = 1;
return x / 0; // undefined behavior

Модификация строкового литерала

char *p = "wikipedia"; // valid C, ill-formed C++11, deprecated C++98/C++03
p[0] = 'W'; // undefined behavior

Забытый return

В не-void функциях, кроме main().

int f()
{
}  /* undefined behavior if the value of the function call is used*/

Бесконечный цикл

Стандарт C объявляет «неопределённым действием» бесконечный цикл без изменения внешнего состояния — поэтому компиляторы C вправе считать любой такой цикл конечным.

В стандарте C11 разрешили бесконечные циклы, где условное выражение является константой.

while (1);

no newline at end of file

Согласно стандарту, непустой файл обязан заканчиваться переводом строки.

Пример, когда это важно.

foo.h:

blah blah blah<no newline>

bar.c:

#include "foo.h"
#include "grill.h"

Получается

blah blah blah#include "grill.h"

В языке C++ в версии C++11 это правило было ликвидировано.

Неуточняемое поведение

Кроме неопределённого поведения, есть ещё два схожих понятия, но менее опасных.

Согласно стандарту языка C99,

  • 3.4.3. неуточняемое поведение (unspecified behavior) — использование неуточняемого значения или иное поведение, где данный Международный стандарт предоставляет два или более варианта и не налагает никаких других требований на выбор в каждом конкретном случае.

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

Порядок вычисления аргументов функции

В С и C++ (в отличие от языка Java) порядок вычисления параметров функции является неуточняемым; следовательно, в программе, указанной ниже, порядок, в котором будут напечатаны строки «F» и «G», зависит от компилятора.

#include <stdio.h>
int f() {
  puts("F");
  return 3;
}
 
int g() {
  puts("G");
  return 4;
}
 
int h(int i, int j) {
  return i + j;
}
 
int main() {
  return h(f(), g()); 
}

В каждом конкретном случае компилятор волен выбирать более удобный ему вариант, но всё-таки он должен сначала вычислить их обе, а уж потом результаты сложить.

Поведение, определяемое реализацией

Согласно стандарту языка C99,

  • 3.4.1. поведение, определяемое реализацией (implementation-defined behavior) — неуточняемое поведение, где каждая реализация документирует выбор поведения;

Размеры типов данных

Классическим примером поведения, определяемого реализацией (поведения, которое обязано быть документировано реализациями), является размер типов данных; например long в различных компиляторах и операционных системах может быть размером в 32 или 64 бит.

Преобразование знаковых и беззнаковых чисел

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

Положительные числа, представимые в обоих вариантах при этом гарантированно сохраняются, что здорово облегчает жизнь.

Проблемы кода с UB

Программа, которая содержит undefined behavior, может внезапно перестать работать при смене компилятора или платформы.

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