С неопределенным поведением. Строгое правило наложения или неправильное выравнивание?
Я не могу объяснить поведение выполнения этой программы:
#include <string>
#include <cstdlib>
#include <stdio.h>
typedef char u8;
typedef unsigned short u16;
size_t f(u8 *keyc, size_t len)
{
u16 *key2 = (u16 *) (keyc + 1);
size_t hash = len;
len = len / 2;
for (size_t i = 0; i < len; ++i)
hash += key2[i];
return hash;
}
int main()
{
srand(time(NULL));
size_t len;
scanf("%lu", &len);
u8 x[len];
for (size_t i = 0; i < len; i++)
x[i] = rand();
printf("out %lu\n", f(x, len));
}
Поэтому, когда он компилируется с -O3 с помощью gcc и запускается с аргументом 25, возникает ошибка segfault. Без оптимизаций работает нормально. Я разобрал его: он векторизован, и компилятор предполагает, что key2 массив выровнен на 16 байтов, поэтому он использует movdqa, Очевидно, это UB, хотя я не могу это объяснить. Я знаю о правиле строгого алиасинга, и это не тот случай (я надеюсь), потому что, насколько я знаю, правило строгого алиасинга не работает с chars. Почему gcc предполагает, что этот указатель выровнен? Clang тоже отлично работает, даже с оптимизацией.
РЕДАКТИРОВАТЬ
Я изменился unsigned char в charи удалил const-а это еще сегфо.
EDIT2
Я знаю, что этот код не очень хорош, но он должен работать нормально, насколько я знаю о строгом правиле псевдонимов. Где именно это нарушение?
3 ответа
Код действительно нарушает строгое правило псевдонимов. Однако существует не только нарушение псевдонимов, и сбой не происходит из-за нарушения псевдонимов. Это происходит потому, что unsigned short указатель неправильно выровнен; даже само преобразование указателя не определено, если результат не выровнен соответствующим образом.
C11 (проект №1570) Приложение J.2:
1 Поведение не определено в следующих обстоятельствах:
....
- Преобразование между двумя типами указателей приводит к неправильному выравниванию результата (6.3.2.3).
С поговоркой 6.3.2.3p7
[...] Если результирующий указатель неправильно выровнен [68] для ссылочного типа, поведение не определено. [...]
unsigned short имеет требование выравнивания 2 для вашей реализации (x86-32 и x86-64), которое вы можете протестировать с
_Static_assert(_Alignof(unsigned short) == 2, "alignof(unsigned short) == 2");
Тем не менее, вы заставляете u16 *key2 указать на невыровненный адрес:
u16 *key2 = (u16 *) (keyc + 1); // we've already got undefined behaviour *here*!
Есть бесчисленное множество программистов, которые настаивают на том, что на практике x86-32 и x86-64 гарантированно будут работать без выравнивания доступа, и на практике проблем не будет - ну, все они не правы.
В основном происходит то, что компилятор замечает, что
for (size_t i = 0; i < len; ++i)
hash += key2[i];
может быть выполнено более эффективно с использованием инструкций SIMD, если они соответствующим образом выровнены. Значения загружаются в регистры SSE с помощью MOVDQA, что требует, чтобы аргумент был выровнен до 16 байтов:
Когда операндом источника или назначения является операнд памяти, операнд должен быть выровнен по 16-байтовой границе, иначе будет сгенерировано исключение общей защиты (#GP).
Для случаев, когда указатель не выровнен соответствующим образом при запуске, компилятор сгенерирует код, который будет суммировать первые 1-7 беззнаковых шорт по одному, пока указатель не будет выровнен до 16 байтов.
Конечно, если вы начнете с указателя, который указывает на нечетный адрес, даже если не добавить 7 раз 2, получится один адрес, который выровнен по 16 байтов. Конечно, компилятор даже не сгенерирует код, который обнаружит этот случай, поскольку "поведение не определено, если преобразование между двумя типами указателей приводит к неверно выровненному результату" - и полностью игнорирует ситуацию с непредсказуемыми результатами, что здесь означает, что операнд MOVDQA не будет правильно выровнен, что приведет к сбою программы.
Можно легко доказать, что это может произойти даже без нарушения каких-либо строгих правил наложения имен. Рассмотрим следующую программу, которая состоит из 2-х единиц перевода (если оба f и его вызывающая сторона помещена в один модуль перевода, мой GCC достаточно умен, чтобы заметить, что мы используем здесь упакованную структуру, и не генерирует код с MOVDQA):
Блок перевода 1:
#include <stdlib.h>
#include <stdint.h>
size_t f(uint16_t *keyc, size_t len)
{
size_t hash = len;
len = len / 2;
for (size_t i = 0; i < len; ++i)
hash += keyc[i];
return hash;
}
блок перевода 2
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <inttypes.h>
size_t f(uint16_t *keyc, size_t len);
struct mystruct {
uint8_t padding;
uint16_t contents[100];
} __attribute__ ((packed));
int main(void)
{
struct mystruct s;
size_t len;
srand(time(NULL));
scanf("%zu", &len);
char *initializer = (char *)s.contents;
for (size_t i = 0; i < len; i++)
initializer[i] = rand();
printf("out %zu\n", f(s.contents, len));
}
Теперь скомпилируйте и свяжите их вместе:
% gcc -O3 unit1.c unit2.c
% ./a.out
25
zsh: segmentation fault (core dumped) ./a.out
Обратите внимание, что там нет нарушения псевдонимов. Единственная проблема - это неприсоединение uint16_t *keyc,
С -fsanitize=undefined возникает следующая ошибка:
unit1.c:10:21: runtime error: load of misaligned address 0x7ffefc2d54f1 for type 'uint16_t', which requires 2 byte alignment
0x7ffefc2d54f1: note: pointer points here
00 00 00 01 4e 02 c4 e9 dd b9 00 83 d9 1f 35 0e 46 0f 59 85 9b a4 d7 26 95 94 06 15 bb ca b3 c7
^
Чтобы предоставить дополнительную информацию и распространенные ошибки отличного ответа от @Antti Haapala:
TL; DR: доступ к невыровненным данным - это неопределенное поведение (UB) в C/C++. Невыровненные данные - это данные по адресу (также известному как значение указателя), которые не делятся равномерно на его выравнивание (обычно это его размер). В (псевдо) коде:bool isAligned(T* ptr){ return (ptr % alignof(T)) == 0; }
Эта проблема часто возникает при анализе форматов файлов или данных, отправляемых по сети: у вас есть плотно упакованная структура с разными типами данных. Примером может быть такой протокол:struct Packet{ uint16_t len; int32_t data[]; };(Читается как: длина 16 бит, за которой следует len, умноженное на 32-битное int в качестве значения). Теперь вы могли:
char* raw = receiveData();
int32_t sum = 0;
uint16_t len = *((uint16_t*)raw);
int32_t* data = (int32_t*)(raw2 + 2);
for(size_t i=0; i<len; ++i) sum += data[i];
Это не работает! Если вы предположите, чтоraw выровнен (в уме вы могли бы установить raw = 0 который выравнивается по любому размеру как 0 % n == 0 для всех n) тогда data невозможно выровнять (при условии, что выравнивание == размер типа): len находится по адресу 0, поэтому data находится по адресу 2 и 2 % 4 != 0. Но приведение говорит компилятору: "Эти данные правильно выровнены" ("... потому что иначе это UB, и мы никогда не столкнемся с UB"). Таким образом, во время оптимизации компилятор будет использовать инструкции SIMD/SSE для более быстрого вычисления суммы, и они выйдут из строя при получении невыровненных данных.
Примечание: есть невыровненные инструкции SSE, но они медленнее, и, поскольку компилятор предполагает выравнивание, которое вы обещали, они здесь не используются.
Вы можете увидеть это в примере из @Antti Haapala, который я сократил и поставил на Godbolt, чтобы вы могли поиграть: https://godbolt.org/z/KOfi6V. Смотрите "программа вернула: 255" или "разбилась".
Эта проблема также довольно часто встречается в процедурах десериализации, которые выглядят следующим образом:
char* raw = receiveData();
int32_t foo = readInt(raw); raw+=4;
bool foo = readBool(raw); raw+=1;
int16_t foo = readShort(raw); raw+=2;
...
В read* заботится о порядке байтов и часто реализуется так:
int32_t readInt(char* ptr){
int32_t result = *((int32_t*) ptr);
#if BIG_ENDIAN
result = byteswap(result);
#endif
}
Обратите внимание, как этот код разыменовывает указатель, который указывает на меньший тип, который может иметь другое выравнивание, и вы сталкиваетесь с конкретной проблемой.
Эта проблема настолько распространена, что даже Boost страдает от нее во многих версиях. Существует Boost.Endian, который обеспечивает простые типы байтов. Код C от Godbolt можно легко написать так:
#include <cstdint>
#include <boost/endian/arithmetic.hpp>
__attribute__ ((noinline)) size_t f(boost::endian::little_uint16_t *keyc, size_t len)
{
size_t hash = 0;
for (size_t i = 0; i < len; ++i)
hash += keyc[i];
return hash;
}
struct mystruct {
uint8_t padding;
boost::endian::little_uint16_t contents[100];
};
int main(int argc, char** argv)
{
mystruct s;
size_t len = argc*25;
for (size_t i = 0; i < len; i++)
s.contents[i] = i * argc;
return f(s.contents, len) != 300;
}
Тип little_uint16_t в основном это просто некоторые символы с неявным преобразованием из / в uint16_t с byteswap если текущая машинная последовательность байтов BIG_ENDIAN. Под капотом код, используемый Boost:endian, был похож на этот:
class little_uint16_t{
char buffer[2];
uint16_t value(){
#if IS_x86
uint16_t value = *reinterpret_cast<uint16_t*>(buffer);
#else
...
#endif
#if BIG_ENDIAN
swapbytes(value);
#endif
return value;
};
Он использовал знание того, что на архитектурах x86 возможен невыровненный доступ. Загрузка с невыровненного адреса была немного медленнее, но даже на уровне ассемблера такая же, как загрузка с выровненного адреса.
Однако "возможный" не означает действительный. Если компилятор заменил "стандартную" загрузку инструкцией SSE, то это не сработает, как это видно на Godbolt. Это долгое время оставалось незамеченным, потому что эти инструкции SSE просто используются при обработке больших фрагментов данных одной и той же операцией, например, добавлением массива значений, что я и сделал для этого примера. Это было исправлено в Boost 1.69 с помощьюmemcopyкоторый можно преобразовать в "стандартную" инструкцию загрузки в ASM, которая поддерживает выровненные и невыровненные данные на x86, поэтому нет замедления по сравнению с версией с приведением. Но его нельзя преобразовать в согласованные инструкции SSE без дополнительных проверок.
Вывод: не используйте ярлыки с приведениями. С подозрением относитесь к каждому приведению, особенно при приведении к меньшему типу, и убедитесь, что выравнивание не может быть неправильным, или используйте безопасный memcpy.
Допустимо присвоить псевдониму указатель на объект указателю на символ, а затем выполнить итерацию всех байтов исходного объекта.
Когда указатель на символ на самом деле указывает на объект (был получен с помощью предыдущей операции), законно преобразовать обратно в указатель на исходный тип, и стандарт требует, чтобы вы вернули исходное значение.
Но преобразование произвольного указателя на символ в указатель на объект и разыменование полученного указателя нарушает строгое правило алиасинга и вызывает неопределенное поведение.
Итак, в вашем коде следующая строка UB:
const u16 *key2 = (const u16 *) (keyc + 1);
// keyc + 1 did not originally pointed to a u16: UB
Если код не делает что-то, чтобы гарантировать выравнивание массива символьного типа, он не должен особенно ожидать, что это будет.
Если о выравнивании заботятся, код берет его адрес один раз, преобразует его в указатель другого типа и никогда не получает доступ к хранилищу никакими средствами, не производными от последнего указателя, тогда реализация, предназначенная для низкоуровневого программирования, не должна иметь никакого особого сложность трактовать хранилище как абстрактный буфер. Поскольку такая обработка не будет сложной и потребуется для некоторых видов низкоуровневого программирования (например, реализация пулов памяти в ситуациях, когда malloc() может быть недоступна), реализация, которая не поддерживает такие конструкции, не должна претендовать на пригодность для низкоуровневого программирования.
Следовательно, в реализациях, предназначенных для низкоуровневого программирования, такие конструкции, как вы описали, позволили бы соответствующим образом выровненные массивы рассматривать как нетипизированное хранилище. К сожалению, не существует простого способа распознать такие реализации, так как реализации, которые предназначены в основном для низкоуровневого программирования, часто не в состоянии перечислить все случаи, когда авторы считают очевидным, что такие реализации ведут себя как модная характеристика среды (и где они, следовательно, именно это и делают), в то время как те, чей дизайн ориентирован на другие цели, могут утверждать, что они подходят для низкоуровневого программирования, даже если они ведут себя неподходящим образом для этой цели.
Авторы Стандарта признают, что C является полезным языком для непереносимых программ, и, в частности, заявили, что не хотели исключать его использование в качестве "ассемблера высокого уровня". Однако они ожидали, что реализации, предназначенные для различных целей, будут поддерживать популярные расширения для облегчения этих целей, независимо от того, требует ли от них этого Стандарт, и, следовательно, нет необходимости в том, чтобы Стандарт обращался к таким вещам. Поскольку такое намерение было отнесено к обоснованию, а не к стандарту, некоторые авторы компиляторов рассматривают стандарт как полное описание всего, что программисты могут ожидать от реализации, и поэтому могут не поддерживать низкоуровневые концепции, такие как использование статического - или объекты с автоматической продолжительностью как буферы с нетипизированными данными.