Прогнозирование ветвей и UB (неопределенное поведение)
Я кое-что знаю о предсказании ветвей. Это происходит на процессоре и не имеет ничего общего с компиляцией. Хотя вы можете сообщить компилятору, является ли одна ветвь более вероятной, чем другая, например. в C++20 через [[likely]] и [[unlikely]] (см. cppreference ) это отдельно от прогнозирования ветвей, выполняемых ЦП (см. Могу ли я улучшить прогнозирование ветвей с помощью своего кода?).
Насколько я знаю, когда у меня есть, например. Цикл (с условием выхода) ЦП прогнозирует, что условие выхода не будет выполнено, и пытается выполнить некоторые операции внутри цикла, даже если условие еще не проверено. Если ЦП прогнозирует правильно, это экономит некоторое время, и все в порядке. Однако что произойдет, если он не сможет предсказать это правильно? Я знаю, что это приведет к снижению производительности, но я не знаю, будут ли некоторые уже выполненные операции отменены или отменены, или просто как они с этим справятся.
Теперь я придумал два простых примера. Первый из них (если игнорировать тот факт, что компилятор может просто вычислить сумму во время компиляции, и я предполагаю, что никакой оптимизации не происходит) должен быть очень легко предсказать для ЦП. Условие цикла будет одинаковым все время, а условие в цикле переключается только один раз. Это означает, что прогноз даст нам хороший прирост производительности, и даже если он несколько раз потерпит неудачу, добавление числа можно легко отменить.
Во втором примере условие выхода снова легко предсказать. В теле цикла я выделяю новый массив int с помощью malloc . Обратите внимание, что я не освобождаю его намеренно, так как хочу, чтобы выделение выполнялось успешно в течение длительного времени, чтобы ЦП предсказывал этот успех. В какой-то момент выделение не удастся, если у меня закончится память (я не рассчитал общее потребление памяти и предположу, что память не будет перемещена на диск) или произойдет какая-то другая ошибка. Это значит, что ptr будет NULL и его разыменование — это UB. Неизвестно, что произойдет, это может быть просто сбой, привести к сбою моей программы или к тому, что мой компьютер улетит. Поэтому я делаю вывод, что процессор не может просто отменить это, и мне интересно, что произойдет.
#include <stdlib.h>
#define VERSION 1
#if VERSION == 1
int main() {
size_t sum = 0ull;
for (size_t i = 0ull, max = 1'000ull; i < max; ++i) {
if (i < (max / 2)) {
sum += 2 * i;
}
else {
sum += i;
}
}
return 0;
}
#else
int main() {
int* ptr = NULL;
for (size_t i = 0ull, max = 1'000'000ull; i < max; ++i) {
ptr = (int*)malloc((sizeof * ptr) * 1'000ull);
if (ptr) {
*ptr = 1234;
}
// free(ptr)
}
return 0;
}
#endif
Прогнозирование ветвей — это задача процессоров, и UB, очевидно, существует как в C, так и в C++, поэтому я думаю, что ответ на этот вопрос не требует одного конкретного языка, и мой код должен работать на обоих языках. Однако, если выбранный язык имеет значение, меня больше интересует C++, чем C, но я буду рад любым ответам.
«добавление числа можно легко отменить». На самом деле это работает не так - неверно предсказанное добавление не «исправляется» вычитанием, а скорее не сохраняется результат. На некоторых аппаратных средствах оба пути if-else могут спекулятивно выполняться параллельно, а затем, когда условие определено, используется только один из них.
Здесь вы смешиваете уровни абстракции. UB — это концепция языка C++. UB означает «Стандарт не налагает никаких обязательств на компилятор в отношении такого кода». В вашем коде нет UB, компилятор должен создать из него действительный исполняемый файл, который ведет себя строго так, как его определил стандарт C++. Остается только возможность (очень редко) ошибки в компиляторе или (очень, очень редко) ошибки в процессоре.
На самом деле это вообще не связано с языком, а с базовой ISA. Кэширование инструкций, конвейеризация, промахи в кэше и т. д. обрабатываются исключительно ЦП, а не программным обеспечением. Неопределенное поведение не применяется — ЦП не является языком программирования.
@AhmedAEK Регистры ЦП (доступные пользователю) также не должны быть затронуты. Изменения фактически производятся во внутренних регистрах. Уязвимости обычно возникают из-за спекулятивного чтения (данных, к которым обычно не следует обращаться) + кода, выдающего разные тайминги в зависимости от значения, а не того, что происходит в регистрах.
@vinc17 Регистры ЦП могут быть затронуты и будут затронуты — единственное, что пытается сделать ЦП, — это отменить эти изменения. Это может означать, что он сохраняет состояние регистров при его анализе и последующем восстановлении или просто помечает их как грязные и впоследствии очищает. Это также является источником многих ошибок безопасности, поскольку регистры изменяются и могут оказывать заметное влияние даже на другие запущенные программы.
Во втором примере вы защитили разыменование указателя, так почему вы думаете, что в этом участвует UB? Как только память будет исчерпана, malloc будет неоднократно возвращать ноль, но тело цикла предохраняет от использования нулевого указателя.
@ErikEidt Я думал, что ЦП может выполнить разыменование перед проверкой условия if (ptr) из-за предсказаний ветвей. Когда ptr никогда не было NULL раньше, он предсказывал, что этого не будет NULL. Я знаю, что это глупая идея, потому что кто-то наверняка думал так же, когда придумывал предсказания ветвей, но я просто хотел узнать об этом немного больше.
@Joel ЦП вполне может попытаться получить доступ к памяти, которую программа никогда не запрашивает, он может даже попытаться прочитать или записать в защищенную память, но это часть инструкций ЦП и его спецификации, которые говорят вам, как он будет вести себя, и большая часть они в здравом уме - поэтому, хотя они могут попытаться сделать что-то противозаконное, их выполнение внутренне помечается как спекулятивное, и любые действия, предпринятые в соответствии с неверными прогнозами, будут отменены. Используемый язык программирования НИКАКОГО влияния не имеет, поскольку ЦП НИКОГДА ЭТОГО НЕ ВИДИТ. Ваш компилятор преобразует ваш код во что-то, что может использовать аппаратное обеспечение, и это не C++.
Ответы 4
Идея спекулятивного выполнения заключается в том, что оно скрыто от вас как программиста. Если вы хотите получить представление о возможных способах реализации этого, вы можете, например, посмотреть, как они выполняют спекулятивное исполнение в BOOM.
Действие C++ по доступу к нулевому указателю, вероятно, будет соответствовать чему-то вроде попытки доступа к памяти по недопустимому адресу в машинном коде. Если бы это произошло, произошла бы TRAP, но если это произойдет спекулятивно, я подозреваю, что спекулятивное выполнение будет ждать подтверждения ветки, прежде чем выдавать ловушку.
Документы Boom говорят следующее о заблуждениях:
Если ветвь (или переход) ошибочно определена, модуль филиала должен перенаправить ПК к правильной цели, уничтожить интерфейсный буфер и буфер выборки и передать ошибочно указанный тег ветвления, чтобы все зависимые находящиеся в полете UOP<Micro-Op (UOP) ) можно убить. Сигнал перенаправления ПК немедленно отключается, чтобы уменьшить штраф за неправильное предсказание. Однако сигнал уничтожения задерживается на цикл по причинам критического пути.
именно так работает RISC-V.
Это верно, ЦП на самом деле не вызывает исключение из деления на 0 или загрузки/сохранения ошибки страницы до тех пор, пока эта инструкция не станет неспекулятивной при выходе на пенсию. В процессорах Intel некоторые загрузки с ошибкой страницы предположительно создавали значение (при попадании TLB на страницу ядра, даже в пользовательском пространстве), которое могли использовать более поздние спекулятивные инструкции; в сочетании с побочным каналом для чтения состояния микроархитектуры (содержимого кэша) в состояние архитектуры (значения регистров) это уязвимость Meltdown.
Также по теме: Может ли спекулятивно выполняемая ветвь ЦП содержать коды операций, обращающиеся к ОЗУ? о том, как буфер хранилища позволяет откатить ошибочно заданные хранилища (что не привело бы к сбою), не загрязняя кеш неправильно заданным состоянием. Потому что мы не должны позволять другим ядрам видеть результаты ошибочных спекуляций.
Предсказание ветвей не имеет ничего общего с UB.
UB — это концепция языка C или C++, абстрагированная от фактической реализации. Его можно анализировать только на уровне исходного кода. Если в вашем коде есть UB, то компилятор в принципе волен делать то, что хочет, поскольку стандарт не определяет, что должно произойти в этом случае.
Если ваш исходный код не вызывает UB, то компилятор должен выдать код, который (при выполнении) будет иметь одинаковое наблюдаемое поведение на всех платформах.
в C++20 через [[вероятно]] и [[маловероятно]] (см. предпочтения) это отдельно от прогнозирования ветвления, которое выполняет ЦП
Он существовал задолго до C++20 в виде расширений компилятора (например, GCC __builtin_expect) и является лишь подсказкой для компилятора, которая поможет ему лучше понять ход вашей программы. В «обычном» программировании это очень редко используемая функция, и вам следует использовать ее только в очень специфических случаях, когда она может значительно улучшить производительность (например, написание низкоуровневых частей ядра ОС или быстрых драйверов устройств).
Я бы предпочел сосредоточиться на самом языке (понимании концепций), а не на эзотерических деталях реализации.
Я бы не сказал, что UB находится на уровне «исходного кода», а скорее на уровне выполнения кода на «абстрактной машине», определенной стандартом C.
@MarekR: «Обязательная обратная связь для [противников] серьезно затруднила бы нынешнюю работу Stack Exchange» . Спрашивать причины отрицательных голосов в комментариях не рекомендуется. (Я еще не голосовал за этот ответ.)
@tstanisl, когда он компилируется и выполняется, обычно довольно четко определен. Он не определен на уровне абстрактной машины.
Если ваш исходный код не вызывает UB. Точнее, компилятор должен создать asm, который работает правильно для всех входных данных, которые не заставляют абстрактную машину встречать UB, как сказал @tstanisl. Например, ++x; может иметь знак переполнения UB, но только для одного значения x; поведение четко определено для всех остальных. Таким образом, компилятор должен создать asm, который работает как минимум для этих значений, но ему разрешено делать что-то странное, если x было INT_MIN. Вот почему gcc -fsanitize=undefined может привести к сбою в этом случае, но другие случаи будут выполняться нормально и при этом оставаться совместимой реализацией C++.
@PeterCordes Это было слишком подробно, чтобы включать в этот ответ, и это не изменило бы его логику.
Неопределенное поведение — это концепция только языка программирования. ЦП должен выполнить программу, написанную на ассемблере (например, сгенерированную компилятором). Однако полное определение ожидаемого поведения совершенно не ясно. Например, из-за спекулятивного выполнения и неправильного прогнозирования ветвей ЦП может делать вещи, которые не выражены в ассемблерном коде, которые не видны в результатах, но последствия которых можно наблюдать через тайминги. Именно это привело к появлению таких уязвимостей, как Spectre.
Однако что произойдет, если он не сможет предсказать это правильно?
Вы тратите время и энергию на работу, которую приходится выбрасывать.
Это означает, что ptr будет NULL и его разыменование будет UB.
Нет, язык так не работает. Компилятор должен соблюдать защиту (оператор if) вокруг этого разыменования.
Компилятор должен соблюдать язык C++, точка! Если компилятор генерирует спекулятивную загрузку нулевого указателя (возможно на некоторых ISA, таких как Itanium), это должно быть условным и игнорируемым, поскольку программа явно сказала не делать этого.
Между тем, оборудование должно поддерживать ISA, и точка! Если аппаратное обеспечение генерирует спекулятивную загрузку нулевого указателя, это также должно быть условным и игнорироваться, поскольку программа в машинном коде явно сказала не делать этого.
через [[вероятно]] и [[маловероятно]] … это отдельно от прогнозирования ветвления, которое выполняет ЦП
Подсказки пути кода на языке C++ не обязательно преобразуются в подсказки предсказания ветвления в машинном коде.
Многие ISA не имеют (или их реализации не используют) подсказок направления ветвления машинного кода. Это связано с тем, что предсказание аппаратных ветвей стало настолько хорошим, что оно выполняется очень рано и не требует подсказок. Чтобы использовать подсказку, инструкция должна быть декодирована, что происходит позже, чем хотелось бы на этапах процессора для прогнозирования.
Что компилятор C++ может сделать с этими подсказками, так это перестроить машинный код так, чтобы вероятный путь был прямым и непрерывным, а маловероятные пути были перемещены в другое место, в сторону от прямого пути.
ЦП не выдает никаких ошибок до тех пор, пока не определит, что ветвь занята, т. е. записи в память не произойдет до тех пор, пока ветвь не будет разрешена, поэтому все, что происходит, пока ветвь еще не выбрана, не имеет побочных эффектов, за исключением регистрируется процессор, что является корнем многих уязвимостей безопасности.