LINUX.ORG.RU

О неопределённом поведении и багах оптимизатора clang на примере разбора цикла статей Криса Латтнера, разработчика clang.

 , , , ,


11

10

про ud2 - лень читать комменты - но кто-то должен был оставить вот этот цикл из трех постов:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html

stevejobs, спасибо за ссылки. С интересом почитал. Ответ получился довольно длинным, даже движок форума не хочет принимать его в таком виде в качестве простого камента, поэтому я решил, что он тянет на отдельную тему. Тем более, что здесь разбирается не какой-то мелкий баг/фича clang'а, а общий подход к созданию оптимизатора, основанный на изложении и анализе статей одного из разработчиков этого компилятора Криса Латтнера (Chris Lattner). Ну и ещё мне пришлось полностью переписать один из его примеров, чтоб он начал работать и иллюстрировать излагаемые им идеи. Если хочешь, можешь послать ему код, чтоб вставил в свою статью вместо своего, не рабочего. Я не возражаю.

А для тех, кто не в теме, это продолжение темы Вызов никогда не вызываемой функции.

Основная мысль автора цикла статей, как я понял, выражена ближе к концу 3-ей статьи в короткой фразе:

c) is a lot of work to implement.

Т. е. автор, по сути, соглашается, что они реализовали какую-то дичь с этими оптимизациями, объясняя некоторые причины: что де оптимизатор не знает, что на входе получает компилятор и даже не знает, что получает он сам на предыдущем проходе, ну и некоторые другие причины. А в конце говорит: но переделывать эту неудачную архитектуру нам лень, поэтому пользуйтесь тем, что есть. Что ж, fixed. В любом случае, статьи полезны, т. к. проливают свет на реальное (и довольно печальное) положение дел, связанных с оптимизациями в компиляторе clang.

Теперь разберу примеры из статей.

1. В первом примере автор пытается показать, почему к указателю на int нельзя обращаться как к указателю на float:

float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
 }

int main() {
  P = (float*)&P;  // cast causes TBAA violation in zero_array.
  zero_array();
}

Этот код — полная дичь. Он будет вылетать и с оптимизациями, и без них, потому что в переменную P (которая по умолчанию инициализируется 0), записывается её собственный адрес, а дальше, начиная с этого адреса, записываются ещё 40000 байт, которые непременно выдут за границы выделенной памяти.

Я немного переделал этот пример, чтоб он заработал, добавив сразу после P массив достаточного размера, в который и будут записываться числа (тоже undefined, но по факту работает с обоими компиляторами — clang и gcc), и заменив запись 0 на запись адреса &P+1, для чего ввёл объединение ufp, т. к. иначе на первой же итерации P будет указывать на 0, после чего на 2-й итерации произойдёт сегфолт. Ну и ещё добавил printf'ы для вывода информации и return, как того требует gcc и стандарт. Тут же отмечу, что мне пришлось слегка повозиться с unsigned *p, объявленным внутри функции print_array(). Сначала я сделал его глобальным, объявив до указателя float *P, и получил похожий на приведённый, но не совсем верный вывод: вместо ожидаемого 0x601268, 0x0, 0x0, 0x601268 программа без оптимизаций выдавала 0x601268, 0x0, 0x601268, 0x0. После установки watchpoint'а в дебагере выяснилось, что массив повторно модифицируется функцией print_array(). Просмотр адресов глобальных переменных &P и &p показал, что и clang, и gcc вставляют p после P и перед массивом arr, хотя в тексте программы она была объявлена первой. Видимо, компиляторы зачем-то сортируют переменные по типам и располагают указатели на float раньше указателей на unsigned. После переноса unsigned *p внутрь функции, всё стало работать, как и ожидалось. Вот мой рабочий (хоть и намеренно некорректный) вариант:

#include <stdio.h>

float *P;

float arr[10000];

union ufp
{
  float** p; float f;
} fp={&P+1};

void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = fp.f;
 }

void print_array() {
   int i;
   unsigned *p;
   printf("&P==%p, P==%p\n", &P, P);
   for(i = -2; i < 10000; ++i)
    {
      p=(unsigned*)P;
      printf("&P[%i]==%p, P[%i]==%f (%p: 0x%X)\n", i, &P[i], i, P[i], p+i, *(p+i));
    }
}

int main() {
  P = (float*)&P;  // cast causes TBAA violation in zero_array.
  zero_array();
  //P=(float*)(&P+1); // restoring P for optimizer
  print_array();
  return 0;
}

При компиляции clang'ом без оптимизации:

clang -o zero_array zero_array.c

этот вариант выдаёт следующее:

&P==0x601260, P==0x601268
&P[-2]==0x601260, P[-2]==0.000000 (0x601260: 0x601268)
&P[-1]==0x601264, P[-1]==0.000000 (0x601264: 0x0)
&P[0]==0x601268, P[0]==0.000000 (0x601268: 0x0)
&P[1]==0x60126c, P[1]==0.000000 (0x60126c: 0x601268)
&P[2]==0x601270, P[2]==0.000000 (0x601270: 0x601268)
&P[3]==0x601274, P[3]==0.000000 (0x601274: 0x601268)
&P[4]==0x601278, P[4]==0.000000 (0x601278: 0x601268)
[skip]
&P[9994]==0x60ae90, P[9994]==0.000000 (0x60ae90: 0x601268)
&P[9995]==0x60ae94, P[9995]==0.000000 (0x60ae94: 0x601268)
&P[9996]==0x60ae98, P[9996]==0.000000 (0x60ae98: 0x601268)
&P[9997]==0x60ae9c, P[9997]==0.000000 (0x60ae9c: 0x601268)
&P[9998]==0x60aea0, P[9998]==0.000000 (0x60aea0: 0x601268)
&P[9999]==0x60aea4, P[9999]==0.000000 (0x60aea4: 0x601268)

и корректно завершается.

Если же включить оптимизацию:

clang -o zero_array -O2 zero_array.c

то получаем следующее:

$ ./zero_array
&P==0x601260, P==0x60126800601268
Ошибка сегментирования

Кстати, такой же результат будет, если откомпилировать эту программу компилятором gcc с включённой оптимизацией (там только адреса будут немного другими). Избавиться от этой ошибки можно 2 способами:

  1. Закомментировав вызов print_array() в функции main().

    Очевидно, что в этом случае никакого вывода мы не получим.

  2. Раскомментировав в main() строчку
    P=(float*)(&P+1); // restoring P for optimizer

    Тогда мы получим такой вывод:

    &P==0x601260, P==0x601268
    &P[-2]==0x601260, P[-2]==0.000000 (0x601260: 0x601268)
    &P[-1]==0x601264, P[-1]==0.000000 (0x601264: 0x0)
    &P[0]==0x601268, P[0]==0.000000 (0x601268: 0x601268)
    &P[1]==0x60126c, P[1]==0.000000 (0x60126c: 0x601268)
    &P[2]==0x601270, P[2]==0.000000 (0x601270: 0x601268)
    &P[3]==0x601274, P[3]==0.000000 (0x601274: 0x601268)
    &P[4]==0x601278, P[4]==0.000000 (0x601278: 0x601268)
    [skip]
    &P[9994]==0x60ae90, P[9994]==0.000000 (0x60ae90: 0x601268)
    &P[9995]==0x60ae94, P[9995]==0.000000 (0x60ae94: 0x601268)
    &P[9996]==0x60ae98, P[9996]==0.000000 (0x60ae98: 0x601268)
    &P[9997]==0x60ae9c, P[9997]==0.000000 (0x60ae9c: 0x601268)
    &P[9998]==0x60aea0, P[9998]==0.000000 (0x60aea0: 0x0)
    &P[9999]==0x60aea4, P[9999]==0.000000 (0x60aea4: 0x0)
    

Проблема тут очевидна: в цикле в P[i] записывается адрес &P+1. Но указатель P указывает на самого себя благодаря присвоению P = (float*)&P. Соответственно, элемент P[0] находится по тому же адресу, что и P. Когда при 1-й итерации цикла мы записываем туда адрес следующего элемента, указатель P меняется. В 64-битной ОС размер указателя равен 8 байтам, а размер float — 4, т. е. P у нас теперь указывает на начало arr. Дальше мы записываем 1-ый элемент от нового начала массива, т. е. по сути 3-й элемент, пропуская таким образом 2 элемента.

Когда же мы включаем оптимизатор (и в clang, и в gcc), он записывает все двойные слова подряд, начиная с 0-ого (в P[-1] у нас 0 потому, что мы перезаписали его после вызова zero_array(), чтобы программа не вылетела при вызове print_array()). Поэтому в первых 2 элементах у нас записано число 0x601268 (если представлять его как беззнаковое целое длиной в 4 байта), но 1-ые 2 элемента одновременно являются адресом, на который указывает P, т. е. адресом 0x0060126800601268 (0x601268 повторенное 2 раза). Если ничего не выводить, то всё тоже проходит успешно. Но как только мы вызываем print_array() (не модифицировав этот дикий адрес), программа сразу пытается отобразить содержимое не валидного адреса 0x601268, а того самого 0x0060126800601268, которого в нашем адресном пространстве просто нет. И получает сегфолт.

Почему printf отображает значения с плавающей точкой, которые в целочисленном виде выглядят как 0x601268, нулями, а не NAN, как по идее должно бы было быть, я не знаю. Видимо, это баг стандартной библиотеки (надо будет послать багрепорт, если никто мне не объяснит, что они правы).

Кстати, оба компилятора по неведомым мне причинам при оптимизации (а я пробовал разные уровни оптимизации) почему-то вместо записи поля fp.f memset'ом продолжают генерить цикл, только более короткий, чем без оптимизации (ассемблерные листинги я тут приводить не буду, кому интересно, могут сами откомпилировать с опцией -S). Хотя при записи константы 0 компилятор clang с вкючённой оптимизацией вместо цикла вызывает memset (gcc и в этом случае генерит цикл).

На всякий случай укажу версии использованных компиляторов:

$ clang --version
Debian clang version 3.5.0-10 (tags/RELEASE_350/final) (based on LLVM 3.5.0)
Target: x86_64-pc-linux-gnu
Thread model: posix

$ gcc --version
gcc (Debian 4.9.2-10) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
Это свободно распространяемое программное обеспечение. Условия копирования
приведены в исходных текстах. Без гарантии каких-либо качеств, включая 
коммерческую ценность и применимость для каких-либо целей.

К сожалению, мне пришлось писать рабочую программу за автора статьи, который не удосужился даже проверить тот код, который опубликовал (хотя там и без проверки видно, что код по-любому не рабочий, хоть оптимизируй, хоть нет). Впрочем, автор всё честно объяснил:

c) is a lot of work to implement.

Такие они, разработчики clang'а.

Но идею я понял: при заполнении массива 0 или другими значениями в цикле, опасно одновременно менять указатель на этот массив. Но при чём тут изначальное утверждение о том, что

It is undefined behavior to cast an int* to a float* and dereference it (accessing the «int» as if it were a «float»).

Как это утверждение иллюстрируется данным примером?

Я уже не говорю о том, что оптимизировать циклы в memset нет никакой необходимости, потому что программист и сам может это сделать, сократив не только получившийся бинарник, но и исходник. А если программисту до этого нет дела, то почему компилятору должно быть дело? Тем более, если программист сделал цикл намеренно, то компилятору совсем незачем это исправлять. Думаю, именно поэтому gcc и не сворачивает циклы в memset. Я уже не говорю о том, что если уж вы сворачиваете их в memset, то будьте последовательны. Почему при заполнении массива константой 0 вместо цикла clang вызывает memset, а при заполнении того же массива одной не меняющейся переменной длиной в 4 байта оставляет цикл? Грош цена такой оптимизации.

Вот заменить вызов memset на ассемблерную команду rep stos действительно было бы полезно, но почему-то ни clang, ни gcc этого не делают.

2. Во втором примере автор цикла показывает, как смертельный указатель может запутать оптимизатор clang так, что тот сгенерит очередную фигню вместо исполняемого кода. Вот пример смертельного кода из 2-й статьи:

void contains_null_check(int *P) {
  int dead = *P;
  if (P == 0)
    return;
  *P = 4;
}

Очевидно, что если передать функции contains_null_check() NULL, то код будет непереносимым (undefined behavior). В защищённом режиме при попытке разыменования такого указателя произойдёт сегфолт. (UPD: практически аналогичная ошибка в ядре Linux 2.6.30 и 2.6.18 для Red Hat привела к серьёзной уязвимости, причём при разыменовании указателя система не падала.) Однако в реальном режиме такой код вполне законный. Более того, если мы рассматриваем язык си как системный язык, то в некоторых случаях без подобного кода в реальном режиме не обойтись. Что у нас лежит по адресу 0 в реальном режиме? — Указатель на обработчик 0-ого прерывания (деление на 0). А что если я хочу зарегистрировать свой обработчик? Для этого и существует неопределённое поведение: в одних системах оно работает так, а в других иначе. Но разработчики clang'а считают, что «неопределённое поведение» — это индульгенция на генерацию разного бреда вместо нормального кода.

Но вернёмся к статье. Автор описывает 2 варианта поведения оптимизатора.

  1. В первом варианте сначала проверяется избыточный код, а затем избыточные проверки. Выглядит это примерно так:
    void contains_null_check_after_DCE(int *P) {
      //int dead = *P;     // deleted by the optimizer.
      if (P == 0)
        return;
      *P = 4;
    }
    

    На этом этапе совершенно справедливо выпилили переменную dead, т. к. она нигде не используется.

    Далее идёт проверка избыточности проверок и делается правильный вывод о том, что проверка P на равенство 0 нужна. Она остаётся. Всё работает, как и задумывалось (и даже не падает в защищённом режиме на радость быдлокодерам).

  2. Во втором варианте оптимизатор сначала проверяет проверки программиста на избыточность, а затем выпиливает ненужные переменные:
    void contains_null_check_after_RNCE(int *P) {
      int dead = *P;
      if (false)  // P was dereferenced by this point, so it can't be null 
        return;
      *P = 4;
    }
    

    Здесь оптимизатор почему-то решил, что раз *P разыменовывается без проверки, то он априори 0 быть не может и проверять его необходимости нет. А то, что программист мог ошибиться, разработчикам оптимизатора даже в голову не приходит. Как и то, что помимо защищённого режима есть ещё и реальный. А бывают ещё компиляторы для разных контроллеров и встроенных специализированных систем, где разыменовывать 0 указатели бывает нужно и иногда даже необходимо. Или clang такие системы не поддерживает? И никогда не сможет поддержать с подобным подходом, ориентированным на работу только защищённых многозадачных ОС.

    Но вернёмся к статье. На следующем этапе выпиливается переменная dead и проверка на 0 и остаётся:

    void contains_null_check_after_RNCE_and_DCE(int *P) {
      *P = 4;
    }
    

    Если раньше программа корректно работала в реальном режиме, а в защищённом падала, то теперь в реальном режиме вектор 0-ого прерывания перезаписывается адресом 4. В результате при любой ошибке деления компьютер намертво зависает (хотя реальный режим clang, как я понимаю, не поддерживает и никогда не сможет поддержать с таким шикарным легаси).

3. Третий пример я разбирать не буду, т. к. согласен с автором, что оптимизация «x > x+1 всегда false» может быть полезна при использовании макросов. А для проверки переполнения существуют константы MAX_*.

4. Четвёртый пример — почти из поста Вызов никогда не вызываемой функции. Его уже разобрали по полочкам, сломали все копья, какие только можно было сломать, в т. ч. и я, поэтому здесь повторяться не буду. Единственно, скажу, что мне было непонятно, зачем заменять вызов функции по 0-ому адресу с неизбежным сегфолтом на недопустимую инструкцию ud2. Автор поясняет во 2-й статье:

2. Clang has an experimental -fcatch-undefined-behavior mode that inserts runtime checks to find violations like shift amounts out of range, some simple array out of range errors, etc. This is limited because it slows down the application's runtime and it can't help you with random pointer dereferences (like Valgrind can), but it can find other important bugs. Clang also fully supports the -ftrapv flag (not to be confused with -fwrapv) which causes signed integer overflow bugs to trap at runtime (GCC also has this flag, but it is completely unreliable/buggy in my experience). Here is a quick demo of -fcatch-undefined-behavior:

В вольном пересказе: мы всегда так делаем, чтобы показать, что код содержит участки с неопределённым поведением. И плевать, что недопустимая инструкция не указывает на некорректный код. Просто ничего лучшего мы не придумали.

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

И напоследок 2 эпические цитаты. Первая из начала 1-ой статьи. Она очень понравилась dzidzitop:

It turns out that C is not a «high level assembler» like many experienced C programmers (particularly folks with a low-level focus) like to think

Вот оно что оказывается. Си — это та же ява, чуть более быстрая и более опасная. А для написания системных вещей переходите на настоящий ассемблер! Кен Томпсон гомерически хохочет и Деннис Ритчи переворачивается в гробу.

А вторая из 3-ей, заключительной статьи:

Ultimately, undefined behavior is valuable to the optimizer because it is saying «this operation is invalid - you can assume it never happens».

В вольном пересказе это обозначает: «Вау! Неопределённое поведение! Ворочу куда хочу!»

UPD: Вот хочу добавить сюда ещё несколько ответов на вопросы, на которые приходится отвечать по всему треду одно и то же:

1. То, что ub обозначает «делай, что хочешь!», мягко говоря, неправда. Вот, что написано в стандарте C99:

3.4.3

1 undefined behavior

behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements

2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.

Т. е. в стандарте чётко прописаны 3 действия, из которых разработчики компиляторов могут выбрать любое:

1. Игнорировать ситуацию. Смотрим в Ожегове, что обозначает слово «игнорировать»:

Умышленно не заметить, не принять во внимание.

Т. е. «игнорировать» — это сделать вид, что всё нормально и пройти мимо, а не модифицировать или удалять такой код, и уж тем более делать на его основе какие-то бредовые предположения.

2. Компилировать и выполнять такой код в соответствии с документацией, с выводом предупреждающих сообщений или без них. Т. е. напишите явно в документации, что если мы встречаем 0 указатель, то делаем то-то и то-то, и делайте. Но не в тихую.

3. Прерывать компиляцию и/или выполнение с обязательным выводом диагностических сообщений.

И всё. Ни о каком «что хочешь» в стандарте речи не идёт. Вот тут мне в каментах подсказали, что «with unpredictable results» обозначает «что хочешь». Но на самом деле это обозначает лишь то, что результаты могут быть непредсказуемыми, а совсем не то, что компилятор может делать всё, что угодно (хотя разработчикам таких компиляторов подобная трактовка очень удобна).

Ну и тот же человек считает, что «это notes», а значит неважно, что там написано. Но т. н. неопределённое поведение при переполнении целого — вообще example из того же пункта:

EXAMPLE An example of undefined behavior is the behavior on integer overflow.

И больше я нигде никаких упоминаний об ub при арифметическом переполнении не нашёл. Про переполнение при сдвигах — нашёл. А в других случаях — нет. Но все почему-то на этот example ссылаются.

2. Многие говорят, что быдлокодеры должны страдать. Но серьёзные уязвимости, связанные с ub, а точнее с непредсказуемой реакцией компилятора на ub, в разное время обнаруживались в ядре Linux, во FreeBSD и в GDK-Pixbuf, затрагивающая Chromium, Firefox и VLC. Подробнее см. в этом комментарии, чтоб не раздувать и без того длинный верхний пост. Здесь только скажу, что уязвимость в ядре Linux связана с ошибкой, идентичной со 2-м примером из разбираемых статей.

3. Автор статей и многие в этом треде утверждают, что автоматически отыскать такие ошибки очень сложно и дорого, а то и вовсе невозможно. Но это тоже не так. В Интернете я нашёл такой пример си++ программы с ub:

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

Программа из-за переполнения временного результата на 174-й итерации при использовании ключа оптимизации -O2 в g++ попадает в бесконечный цикл.

Запустив компиляцию, я получил следующие предупреждения (причём безо всяких опций -W что-то_там):

$ g++ -o infinity_loop -O2 infinity_loop.cpp
infinity_loop.cpp: В функции «int main()»:
infinity_loop.cpp:5:38: предупреждение: iteration 174u invokes undefined behavior [-Waggressive-loop-optimizations]
         std::cout << i << " " << i * 12345678 << std::endl;
                                      ^
infinity_loop.cpp:4:5: замечание: containing loop
     for (int i = 0; i < 300; i++)
     ^

А ведь здесь случай куда менее очевидный, чем простое разыменование NULL-указателя.

4. Наконец, на Хабре я вычитал, что стандартный макрос

#define offsetof(st, m) ((size_t)(&((st *)0)->m))

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

UPD 2: Вот тут Sorcerer в комментарии кинул ссылку на письмо Линуса Торвальдса в рассылке от 12 января 2009 года, где он пишет о том, что думает о некоторых оптимизациях. Приведу несколько фрагментов этого письма в своём переводе:

Type-based aliasing — это тупость. Это такая невероятная тупость, что даже не смешно. Оно испорчено. И gcc взял испорченную концепцию и настолько её раздул, следуя букве-закона, что получилась бессмысленная вещь.

[skip]

Это НЕНОРМАЛЬНО. Это так невероятно безумно, что люди, которые делают это, просто должны избавиться от своего убожества, прежде чем они смогут восстановить. Но реальные gcc программисты действительно думали, что это имеет смысл, потому что стандарт это позволяет и даёт компилятору максимальную свободу, — потому что он может делать теперь вещи БЕЗУСЛОВНО АБСУРДНЫЕ.

И компиляторщикам абсолютно абсурдные вещи часто кажутся действительно хорошими, потому что им больше не надо беспокоиться о конечном результате: работает оно или нет, — они просто получили добро тупить во имя оптимизации.

[skip] И если кто-то жалуется, что компилятор невменяемый, компиляторщики скажут «ня, ня, разработчики стандарта сказали, что так можно», с абсолютным отсутствием анализа, имеет ли оно СМЫСЛ.

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

[skip]

Угадайте, что произойдёт, если вы имеете такой безумный склад ума и пытаетесь сделать безопасный код без alias'а, — вы займёте лишнее пространство на стеке.

По факту, Linux использует -fno-strict-aliasing из-за чертовски веской причины: потому что в gcc понятие «strict aliasing» является огромной зловонной кучей д-рьма. Linux использует этот флаг не потому, что Linux исполняется быстро и свободно, он использует этот флаг, потому что _не_ использует тот безумный флаг.

Type-based aliasing неприемлемо тупо для начала, и gcc вознёс этот идиотизм до совершенно новых высот, фактически не обращая внимания даже на статически видимый aliasing.

Линус

Оригинал (на английском):

Type-based aliasing is _stupid_. It's so incredibly stupid that it's not even funny. It's broken. And gcc took the broken notion, and made it more so by making it a «by-the-letter-of-the-law» thing that makes no sense.

[skip]

That's INSANE. It's so incredibly insane that people who do that should just be put out of their misery before they can reproduce. But real gcc developers really thought that it makes sense, because the standard allows it, and it gives the compiler the maximal freedom - because it can now do things that are CLEARLY NONSENSICAL.

And to compiler people, being able to do things that are clearly nonsensical seems to often be seen as a really good thing, because it means that they no longer have to worry about whether the end result works or not - they just got permission to do stupid things in the name of optimization.

[skip] And if somebody complains that the compiler is insane, the compiler people would say «nyaah, nyaah, the standards people said we can do this», with absolutely no introspection to ask whether it made any SENSE.

Anyway, once you start doing stupid things like that, and once you start thinking that the standard makes more sense than a human being using his brain for 5 seconds, suddenly you end up in a situation where you can move stores around wildly, and it's all 'correct'.

[skip]

Guess what happens if you have that kind of insane mentality, and you then try to make sure that they really don't alias, so you allocate extra stack space.

The fact is, Linux uses -fno-strict-aliasing for a damn good reason: because the gcc notion of «strict aliasing» is one huge stinking pile of sh*t. Linux doesn't use that flag because Linux is playing fast and loose, it uses that flag because _not_ using that flag is insane.

Type-based aliasing is unacceptably stupid to begin with, and gcc took that stupidity to totally new heights by making it actually more important than even statically visible aliasing.

Linus

И ещё спасибо anonymous'у за камент с ещё одним сообщением на ту же тему того же автора от 26 февраля 2003 года.

Ну и от себя добавлю, что не только Линусу не нравится aliasing. Microsoft тоже не спешит реализовывать его в своём Visual C++. Т. е. не нравится это тем, кто помимо разработки компиляторов создаёт и другой софт с использованием этого компилятора, например ОС. А те, кто создают только компиляторы для сферических программистов в вакууме, рьяно эту фичу реализуют, хоть их и никто не заставляет.

Ну и напоследок оставлю несколько полезных ссылок на память:

Стандарт C11 (последний) (pdf), Стандарт C99 (pdf),

http: //read.pudn.com/downloads133/doc/565041/ANSI_ISO%2B9899-1990%2B%5B1%5D.pdf (Стандарт C89) (pdf),

http: //web.archive.org/web/20030222051144/http: //home.earthlink.net/~bobbitts/c89.txt (Стандарт C89) (txt),

https: //web.archive.org/web/20170325025026/http: // www .open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4660.pdf (Стандарт C++17) (последний) (pdf),

Стандарт C++14 (pdf), Стандарт C++11 (pdf),

бумажный перевод стандарта C++17, выполненный Зуевым и Чуприновым, Москва, 2016, на основе Working Draft, Standard for Programming Language C++ от 22 мая 2015 года (номер документа n4527) за 4945 руб. (надеюсь, что эту ссылку не сочтут за рекламу, т. к. к авторам я никакого отношения не имею), а здесь можно скачать начало перевода (предисловие и содержание), ну и ещё торрент-ссылку видел на эту книгу, но здесь её публиковать не буду,

статья на Хабре (из песочницы) от 2014 г. Неопределенное поведение в C++, ещё одна статья там же от 2016 года Находим ошибки в коде компилятора GCC с помощью анализатора PVS-Studio, Разыменовывание нулевого указателя приводит к неопределённому поведению и Про C++ алиасинг, ловкие оптимизации и подлые баги. Это так, ссылки на заметку.

Некоторые ссылки парсер ЛОР'а не принял, поэтому мне пришлось разделить их пробелами, превратив в текст, который можно скопировать в адресную строку браузера, удалив пробелы. Там, где http встречается дважды в 1 строке — не ошибка, а именно такие ссылки.

★★

Последнее исправление: aureliano15 (всего исправлений: 2)
Ответ на: комментарий от Sorcerer

предлагаешь возле каждой переменной писать restrict чтобы оптимизатор заработал?

лучше вы к нам те, кого это не устраивает, напишут -O0

anonymous
()
Ответ на: комментарий от anonymous

предлагаешь возле каждой переменной писать restrict чтобы оптимизатор заработал?

Почему-то если создавать указатели одинаковых типов на разные объекты (на локальные, например), то оптимизатор и без restrict оптимизирует работу с ними.

А так - да.

Sorcerer ★★★★★
()
Ответ на: комментарий от aureliano15

Но я-то спрашивал про реальный режим x86, а не про защищённый pdp-11.

Вы не сколько спрашивали, сколько намекали на очень узкую задачу, я же намекал, что нуль он и в Африке нуль. Например исходный топик с call [0] у авторов Си в пользовательском Unix-процессе не то что падал, а циклился, то есть бесконечно рестартовал и, если и падал, то по исчерпания стека или кучи.

vodz ★★★★★
()
Ответ на: комментарий от Sorcerer

Почему-то если создавать указатели одинаковых типов на разные объекты (на локальные, например), то оптимизатор и без restrict оптимизирует работу с ними.

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

А так - да.

Нет, спасибо. Даже сейчас когда restrict скорее редкость постоянно натыкаюсь на некорректную работу с ним. Если его везде где ни попадя пихать будут, то вообще ничего не заработает. А обвинят во всём компилятор. Ну не пользователь же криворукий, ей-богу.

alexanius ★★
()
Ответ на: комментарий от alexanius

Потому что проследить локальные объекты просто.

Ну вот и хорошо. На самом деле, мало кто возмущался бы, если б компилятор со strict aliasing'ом прослеживал локальные объекты для несовместимых указателей, но он встаёт в позу, UB дескать, так что поломаю вам тут всё назло.

Нет, спасибо. Даже сейчас когда restrict скорее редкость постоянно натыкаюсь на некорректную работу с ним.

Потому и натыкаетесь, что редкость. Когда перестанет быть редкостью, то и ошибок его использования будет меньше (в процентном отношении).

Вообще говоря, restrict помогает компилятору оптимизировать и сейчас, так что быть противником restrict как-то странно.

А обвинят во всём компилятор.

Так его и сейчас обвиняют. Без strict aliasing'а всё работало, а тут вдруг с ним перестало. Из-за чего? Просто компилятор решил в одностороннем порядке указать «слабые» restrict для всех несовместимых указателей. Разница в том, что если б разработчик сам неправильно использовал restrict, то вина была бы на нём. Компилятор, конечно, и сейчас считает, что при strict aliasing'е вина на разработчике, и всё было бы ничего, если бы существовала альтернатива, а об этом я уже написал.

Sorcerer ★★★★★
()
Ответ на: комментарий от Sorcerer

Просто чтобы была понятна сложность разбора ошибок на restrict - пока не продрался через компиляторный inline даже не подозреваешь об этом. Там хотя бы автор нормальный и сказал что поправит. А ведь остальным и стандарт не указ ;)

Ну вот и хорошо. На самом деле, мало кто возмущался бы, если б компилятор со strict aliasing'ом прослеживал локальные объекты для несовместимых указателей, но он встаёт в позу, UB дескать, так что поломаю вам тут всё назло.

На самом деле компиляторы учатся. По крайней мере где-то с 5-х версий gcc канонические примеры UB со strict-aliasing'ом не работают (в смысле он зависимости не рвёт). Мне вообще пришлось писать дико сложный анализ чтобы такие вещи отслеживать, но в общем случае это невозможно. Конкретно со strict-aliasing'ом сложность ещё в том что strict-aliasing это чисто runtime явление, а значит compile-time анализ будет работать либо очень долго и пропускать какие-то вещи (как у меня) либо генерить 100500 false-positive варнингов, которые пользователь даже разбирать не будет и тупо их отключит (как в gcc).

alexanius ★★
()
Ответ на: комментарий от aureliano15

Ну да. И вообще все программы могут постоянно падать, а ещё лучше вообще не загружаться. И молотки могут при каждом ударе по гвоздю ломаться, отлетая в голову.

Почувствуй разницу между «должен» и «может». И потом приходи.

maverik ★★
()
Ответ на: комментарий от alexanius

Просто чтобы была понятна сложность разбора ошибок на restrict - пока не продрался через компиляторный inline даже не подозреваешь об этом.

Ну в данном случае некорректное использование объекта видно компилятору, он мог бы и warning бросить.

На самом деле компиляторы учатся.

Сначала всё сломали, потом, когда уже бесполезно, учатся. С другой стороны, значит, не зря их пинают. :)

Конкретно со strict-aliasing'ом сложность ещё в том что strict-aliasing это чисто runtime явление

Ну так потому что не надо было заниматься извращениями со strict aliasing'ом, а идти в сторону перекладывания на разработчика оптимизационных предложений. Тем более, что выигрыш от оптимизаций со strict aliasing'ом не всегда существенен, а там где существенен, разработчик может restrict задействовать. А так получается, что сами себе создали проблему, и теперь героически её преодолевают.

Sorcerer ★★★★★
()
Ответ на: комментарий от Sorcerer

Ну в данном случае некорректное использование объекта видно компилятору, он мог бы и warning бросить.

Не мог бы. После inline там такая каша что вообще нереально что-либо человекопонятное выдать. Более того, сам по себе анализ предупреждений также хрен напишешь. Он сможет только самые тривиальные случаи выявлять типа тех, которые в этом треде приводят и думают что всё так легко и просто. Даже в приведённом случае скорей всего не получилось бы.

Тем более, что выигрыш от оптимизаций со strict aliasing'ом не всегда существенен, а там где существенен, разработчик может restrict задействовать.

Вот не может. restrict - довольно сложная штука, в которой ошибаются чаще чем в strict-aliasing. И это не эквивалентные вещи, они используются по-разному и разрывают разные классы зависимостей.

alexanius ★★
()
Ответ на: комментарий от aureliano15

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

Те, кто пишут драйвер, могут почитать документацию по своей платформе, компилятору и его флагам и добиться нужного поведения.

Во-вторых, что мешало сделать переполнение со знаком не ub, а implemented behavior? Не так уж много существует вариантов поведения.

Термина «implemented behavior» не бывает. Если Вы говорите о implementation defined, то это не позволило бы иметь что-то вроде -ftrapv.

На деле оба компилятора умеют в -fwrapv, который делает поведение вполне определённым. Думаю, у вижака что-то такое же есть.

В-третьих, даже если ub. Ну и пусть этот код корректно выполняется на большинстве платформ. А на Itanium'е при первой же отладке громко упадёт, а не будет тихо «форматировать диск».

Не на первой отладке, а когда в регистре окажется значение с этим испорченным битом.

Ну и в-четвёртых, при использовании intN_t проблемы вообще не стоит. См. п. 7.20.1.1 стандарта и другой мой камент по этому поводу.

Я бы не сказал, что из использования доп. кода логически следуют определённые правила переполнения.

vzzo ★★★
()
Ответ на: комментарий от aureliano15

Ну так и форкните GCC и сделайте там определённое поведение при обращении к нулевому адресу.

dzidzitop ★★
()
Ответ на: комментарий от aureliano15

Мало кому интересно разгребать сотни false positive предупреждений. Но можете создать тикет в трекере ГЦЦ. Вдруг вас поддержат.

dzidzitop ★★
()
Ответ на: комментарий от alexanius

Вот не может. restrict - довольно сложная штука, в которой ошибаются чаще чем в strict-aliasing. И это не эквивалентные вещи, они используются по-разному и разрывают разные классы зависимостей.

Это как бы вообще совсем разные вещи.

dzidzitop ★★
()
Ответ на: комментарий от alexanius

И это не эквивалентные вещи, они используются по-разному и разрывают разные классы зависимостей.

Согласен, и тогда нужен механизм более гибкого указания хинтов компилятору, чем простой restrict. А один strict-aliasing - всё равно не выход.

Sorcerer ★★★★★
()
Ответ на: комментарий от Sorcerer

Типа такого?

[[noalias(a, b)]]
int sum(int *a, int *b, int *c, int size);
anonymous
()
Ответ на: комментарий от Sorcerer

Согласен, и тогда нужен механизм более гибкого указания хинтов компилятору, чем простой restrict. А один strict-aliasing - всё равно не выход.

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

alexanius ★★
()
Ответ на: комментарий от aureliano15

Думаю, ты путаешь компилятор и статический анализатор.

Я вижу три способа борьбы с сабжем:

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

2. Выдавать предупреждения на рискованные оптимизации. Реально не сработает, потому что в общем случае этого при компиляции не видно. Компиляторы уже сложные, а их придется еще офигенно усложнить и замедлить. Либо они будут выдавать огромный лог, что равносильно его отсутствию.

3. Наконец, использовать подходящий для этого инструмент - статический анализатор. Они в этом уже умнее компиляторов, и дальше они будут расходиться всё больше, каждый в свою сторону.

anonymous
()
Ответ на: комментарий от aureliano15

Вот тут мне в каментах подсказали, что «with unpredictable results» обозначает «что хочешь». Но на самом деле это обозначает лишь то, что результаты могут быть непредсказуемыми, а совсем не то, что компилятор может делать всё, что угодно

Ты и получил непредсказуемый результат. И что значит «делать всё, что угодно»? Хороший компилятор делает массу нетривиальных преобразований, если думаешь что это плохо - посиди на генте собранной с -O0, расскажешь о впечатлениях.

Пока что ты говоришь «хочу чтобы мне было хорошо», никак это не формализуя.

И больше я нигде никаких упоминаний об ub при арифметическом переполнении не нашёл

Афаик, там вовсе нет указаний на поведение при переполнении знаковых, что и означает UB. Поведение не определено -> неопределенное поведение, смекаешь?

anonymous
()
Ответ на: комментарий от anonymous

Поправка: это скорее в тему restrict. Предложение было мощнее чем он, но оказалось противоречивым.

anonymous
()
Ответ на: комментарий от aureliano15

Однако они тоже не стали реализовывать у себя этот strict aliasing.

Не показатель. Любой может реализовывать, а может не реализовывать. Тем более, в GCC можно отключить, это не принудиловка всем вообще.

трюк с несуществующей функцией __this_fixmap_does_not_exist()

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

— That's UI. It doesn't matter that it takes 200 nanoseconds more...

В user interface — обычно да. А в каком-нибудь чтении/записи в длинном цикле какого-то важного фонового процесса — может быть важным.

Там было именно UI, в котором понятный код важнее экономии в 200 наносекунд.

А C99, в свою очередь, не требует от компилятора портить такие указатели.

Компилируй c -O0. Оптимизаций захотел? Иж чего удумал? Ещё, небось, хочешь, чтобы код побыстрее работал? :-D

Но такую функцию (взято из того же письма Торвальдса) можно было бы догадаться не трогать:

Алгоритм можешь написать, по которому компилятор должен догадаться? Желательно в виде патча к GCC, чтобы другие согласные с тобой могли воспользоваться наработками.

И в такой функции (уязвимость в ядре Линукс 2009 года) предупреждение напрашивается само собой:

Clang static analyzer предупреждает. Но он работает чуть ли не в десяток раз медленнее в этом режиме.

Однако оптимизирующий компилятор тихо выбирает 2-й вариант (что проверка лишняя), вместо предупреждения.

Ты ведь осознаёшь, что текст не напрямую преобразуется в код, а используются проходы? Уверен, что в решателе сможешь отделить «очевидно правильный вариант» генерации кода?

Т. е. речь о C вообще, но с упором на clang и llvm.

Сегодня текущий Clang генерирует так, завтра сяк. UB на то и undefined, что поведение не определено. Заморачиваться, доводя пример до компилируемого состояния мало того, что бессмысленно, так ещё и вредно. Кто-то запустит у себя, описанного в статье не словит, и долго будет везде вещать, что в статье написан бред, и что у него, дескать, всё работает нормально. Такие ошибки как раз и опасны тем, что не воспроизводятся всегда и везде.

Я рад, что автор сделал нерабочие примеры.

i-rinat ★★★★★
()
Ответ на: комментарий от aureliano15

ну, ядро тут ни при чём. соглашусь с Торвальдсом, что выравнивание - матёрый маразм. но он не относится к ядру. это всего лишь опция компилятора. и, конечно, в микроконтроллерах ни о каком выравнивании не идёт речи: излишка ресурсов там нет.

контроллеры 8086 используются в основном для таймеров. но там нет никаких толп говнокодеров. а у воендосов время вообще остановилось в прошлом веке ещё. они используют какие-то монстрозные контроллеры, которые уже давно вышли из употребления.

Iron_Bug ★★★★★
()
Ответ на: комментарий от anonymous

выравнивание тут тоже при чём. так как компилятор пытается его присунуть в структуры. якобы для «улучшения» быстродействия, хотя это полная фигня и не критичная оптимизация. алиасинг - это просто наложение разных структур друг на друга. и, в принципе, это должно работать, без всякого выпендрёжа. вообще, в этом плане лучше не доверять компилятору и использовать просто массивы однобайтовых полей. чтобы компилятор не делал умный вид и не занимался ненужной фигнёй по «оптимизации» того, что оптимизировать не нужно. ну или использовать этот флаг, чтобы принудительно запретить компилятору заниматься тем, чем он заниматься не должен.

Iron_Bug ★★★★★
()
Ответ на: комментарий от alexanius

Просто чтобы была понятна сложность разбора ошибок на restrict - пока не продрался через компиляторный inline даже не подозреваешь об этом. Там хотя бы автор нормальный и сказал что поправит. А ведь остальным и стандарт не указ ;)

Посмотрел этот случай внимательнее. Вообще там непонятно, что делает конструкция «data[0] = left_;», где data имеет тип (void *). Но допустим, что это какая-то опечатка. Вот что говорит стандарт об UB для restricted:

— An object which has been modified is accessed through a restrict-qualified pointer to a const-qualified type, or through a restrict-qualified pointer and another pointer that are not both based on the same object (6.7.3.1).
— A restrict-qualified pointer is assigned a value based on another restricted pointer whose associated block neither began execution before the block associated with this pointer, nor ended before the assignment (6.7.3.1).

Таким образом, стандарт не запрещает определять другие не-restrict-указатели на тот же объект, но они должны зависеть от restrict-указателя.

В нашем случае с зависимостью указателей всё нормально, за исключением того, что restrict-указатель имеет тип (void *), а не-restrict - (uint64_t *). То есть это опять проблема упоротого strict aliasing'а, но не использования restrict.

Sorcerer ★★★★★
()
Ответ на: комментарий от anonymous

я не могу назвать раст нормальным. мне не нравится его синтаксис и отсутсвие многих фич, которые есть в С++. причем это не какие-то навороченные космические фичи, а совершенно обычные. вроде перегрузки операторов

ckotinko ☆☆☆
()
Ответ на: Лентяи от Deleted

Скорее

float Q_rsqrt( float number ) {
        union {
	     long i; float y;
        };
	float x2;
	const float threehalfs = 1.5F;

	x2 = number * 0.5F;
	y  = number;
	i  = 0x5f3759df - ( i >> 1 );
	y  = y * ( threehalfs - ( x2 * y * y ) );

	return y;
}

anonymous
()
Ответ на: комментарий от anonymous

печалеязык, чо. «operator +» это понятно, очевидно, и самое главное - не сильно усложнит парсер, если договориться что operator - keyword, и после него должен идти знак операции.

а тут пишут «add». конечно, хозяин барин, но это некрасиво а потому летать не будет.

ckotinko ☆☆☆
()
Ответ на: комментарий от ckotinko

печалеязык, чо. «operator +» это понятно, очевидно, и самое главное - не сильно усложнит парсер, если договориться что operator - keyword, и после него должен идти знак операции.

а тут пишут «add». конечно, хозяин барин, но это некрасиво а потому летать не будет.

«Очевидно» для C++, в Rust «очевидно» через типажи. Дальше эти типажи можно указывать в шаблонах.

fn fma<T>(a: T, b: T, c: T) -> T
    where T: Add<Output=T> + Mul<Output=T>
{
    a * b + c
}

Ты же понимаешь, что ты очень мало знаешь про Rust, по-этому многие вещи кажутся «не пришей кобыле хвост». Если бы ты удосужился, прежде чем выражать своё недовольство, изучить его... Слышал про «Парадокс Блаба»? Ты демонстрируешь его во всей красе.

anonymous
()
Ответ на: комментарий от ckotinko

Фича то есть, выглядит не так, но работает же одинаково. А к синтаксису привыкнуть можно.

pftBest ★★★★
()
16 апреля 2018 г.

Т. е. в стандарте чётко прописаны 3 действия, из которых разработчики компиляторов могут выбрать любое:

1. Игнорировать ситуацию. Смотрим в Ожегове, что обозначает слово «игнорировать»:

Умышленно не заметить, не принять во внимание.

Т. е. «игнорировать» — это сделать вид, что всё нормально и пройти мимо, а не модифицировать или удалять такой код, и уж тем более делать на его основе какие-то бредовые предположения.

Определение у Ожигова хорошее. А дальнейшая интерпретация у автора — неверная. Интепретация больше про вытеснение или забывчивость, а не игнорирование.

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

Так, в примере с указателями, видя indirection указателя, компилятор умышленно с этих пор не принимает во внимание значение указателя, равное нулю, как приводящее к неопределённому поведению. Всё в соответствии с Ожиговым и стандартом.

anonymous
()
Ответ на: комментарий от anonymous

Ба! Старая тема опять всплыла из небытия. :-)

Ожигова

Ожегова.

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

Так, в примере с указателями, видя indirection указателя, компилятор умышленно с этих пор не принимает во внимание значение указателя, равное нулю, как приводящее к неопределённому поведению.

Скорее, компилятор считает, что указатель ни при каких обстоятельствах не может быть равным 0, даже если ему очевидно, что он равен 0, т. к. если бы он просто игнорировал, то допустил бы сегфолт, — и всё.

В качестве иллюстрации можно привести пример из форумной жизни. Я могу заигнорить в настройках пользователя anonymous, и тогда я не увижу никаких сообщений анонимусов. Для меня их просто не будет существовать. Что бы ни написал анонимус, что-то дельное или глупость, я просто об этом не узнаю и пройду мимо. Но если я отвечаю анонимусу, доводя до абсурда каждый его тезис, то это уже не игнор, а тролинг. То же и с компиляторами. Их создатели тролят пользователей, доводя до абсурда положения стандарта и не объясняя причин этого (ну кроме разве что «это очень сложно, и иначе мы не умеем»), возможно, находя такое поведение забавным, и называют свой тролинг игнором, якобы в соответствии со стандартом. Именно об этом писал Линус Торвальдс в частично процитированном в верхнем посту письме. И именно поэтому использование стандартного макроса #define offsetof(st, m) ((size_t)(&((st *)0)->m)) в твоём коде потенциально может привести к форматированию диска, а компиляторописатели скажут на твои недоумённые вопросы: «кто не спрятался, — мы не виноваты».

aureliano15 ★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.