Безопасно ли читать за пределами буфера на одной и той же странице на x86 и x64?
Многие методы, которые можно найти в высокопроизводительных алгоритмах, можно (и) упростить, если им разрешено считывать небольшое количество после окончания входных буферов. Здесь "небольшое количество" обычно означает до W - 1 байтов за конец, где W это размер слова в байтах алгоритма (например, до 7 байтов для алгоритма, обрабатывающего ввод в 64-битных блоках).
Понятно, что запись после конца входного буфера, как правило, небезопасна, так как вы можете забить данные за пределы буфера 1. Также ясно, что чтение после окончания буфера на другую страницу может вызвать ошибку сегментации / нарушение доступа, поскольку следующая страница может быть недоступна для чтения.
Однако в особом случае чтения выровненных значений сбой страницы кажется невозможным, по крайней мере, в x86. На этой платформе страницы (и, следовательно, флаги защиты памяти) имеют гранулярность 4 КБ (возможны большие страницы, например, 2 МБ или 1 ГБ, но они кратны 4 КБ), поэтому выровненные операции чтения будут иметь доступ только к байтам на той же странице, что и действительные часть буфера.
Вот канонический пример некоторого цикла, который выравнивает свои входные данные и читает до 7 байтов после конца буфера:
int processBytes(uint8_t *input, size_t size) {
uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
int res;
if (size < 8) {
// special case for short inputs that we aren't concerned with here
return shortMethod();
}
// check the first 8 bytes
if ((res = match(*input)) >= 0) {
return input + res;
}
// align pointer to the next 8-byte boundary
input64 = (ptrdiff_t)(input64 + 1) & ~0x7;
for (; input64 < end64; input64++) {
if ((res = match(*input64)) > 0) {
return input + res < input + size ? input + res : -1;
}
}
return -1;
}
Внутренняя функция int match(uint64_t bytes) не отображается, но это то, что ищет байт, соответствующий определенному шаблону, и возвращает самую низкую позицию (0-7), если найдена, или -1 в противном случае.
Во-первых, случаи с размером < 8 закладываются в другую функцию для простоты изложения. Затем выполняется одна проверка для первых 8 (не выровненных байтов). Затем делается цикл для оставшихся floor((size - 7) / 8) куски 8 байтов 2. Этот цикл может считывать до 7 байтов после конца буфера (7-байтовый случай возникает, когда input & 0xF == 1). Однако обратный вызов имеет проверку, которая исключает любые ложные совпадения, которые происходят за пределами конца буфера.
Практически говоря, безопасна ли такая функция на x86 и x86-64?
Эти типы переопределений распространены в высокопроизводительном коде. Специальный хвостовой код, чтобы избежать таких перегибов, также распространен. Иногда вы видите, как последний тип заменяет первый, чтобы заставить замолчать такие инструменты, как valgrind. Иногда вы видите предложение сделать такую замену, которое отклоняется на том основании, что идиома безопасна, а инструмент ошибочен (или просто слишком консервативен) 3.
Примечание для языковых юристов:
Чтение из указателя сверх его выделенного размера определенно не разрешено в стандарте. Я ценю ответы юристов, и даже иногда пишу их сам, и я даже буду рад, если кто-то выкопает главу и стих, в которых показано, что приведенный выше код является неопределенным поведением и, следовательно, небезопасным в самом строгом смысле (и я скопирую подробности здесь). В конечном счете, это не то, что я ищу. На практике многие распространенные идиомы, включающие преобразование указателя, доступ к структуре через такие указатели и т. Д., Технически не определены, но широко распространены в высококачественном и высокопроизводительном коде. Часто нет альтернативы, или альтернатива работает на половине скорости или меньше.
Если вы хотите, рассмотрите измененную версию этого вопроса, а именно:
После того, как приведенный выше код был скомпилирован в сборку x86/x86-64, и пользователь проверил, что он скомпилирован ожидаемым образом (т. Е. Компилятор не использовал доказуемый частично за пределами доступа, чтобы сделать что-то действительно умно, безопасно ли выполнять скомпилированную программу?
В этом отношении этот вопрос является одновременно вопросом C и вопросом сборки x86. Большая часть кода, использующего этот трюк, который я видел, написана на C, и C по-прежнему является доминирующим языком для высокопроизводительных библиотек, легко затмевая низкоуровневые вещи, такие как asm, и высокоуровневые вещи, такие как <все остальное>. По крайней мере, за пределами жесткой числовой ниши, где Фортран все еще играет в мяч. Так что меня интересует представление вопроса на языке C-compiler-and-under, поэтому я не сформулировал его как вопрос о чисто x86-сборке.
Все это говорит о том, что, хотя мне лишь умеренно интересна ссылка на стандарт, показывающий, что это UD, я очень заинтересован в любых деталях реальных реализаций, которые могут использовать этот конкретный UD для создания неожиданного кода. Теперь я не думаю, что это может произойти без какого-либо глубокого, довольно глубокого анализа кросс-процедур, но переполнение gcc удивило многих людей тоже...
1 Даже в явно безвредных случаях, например, когда записывается одно и то же значение, это может нарушить параллельный код.
2 Примечание для этого перекрытия для работы требует, чтобы эта функция и match() Функция должна вести себя определенным идемпотентным образом - в частности, что возвращаемое значение поддерживает перекрывающиеся проверки. Таким образом, "найти первый шаблон сопоставления байтов" работает, так как все match() звонки все еще в порядке. Однако метод "счетчик байтов соответствует шаблону" не сработает, поскольку некоторые байты могут быть подсчитаны дважды. В качестве отступления: некоторые функции, такие как вызов "вернуть минимальный байт", будут работать даже без ограничения по порядку, но должны проверять все байты.
3 Стоит отметить, что для Memcheck Вальгринда есть флаг, --partial-loads-ok который контролирует, будут ли такие чтения фактически сообщаться как ошибка. По умолчанию да, это означает, что в целом такие загрузки не рассматриваются как непосредственные ошибки, но что предпринимаются усилия для отслеживания последующего использования загруженных байтов, некоторые из которых являются действительными, а некоторые нет, с пометкой ошибки. если используются байты вне диапазона. В случаях, таких как пример выше, в котором все слово доступно в match() такой анализ сделает вывод, что байты доступны, хотя результаты в конечном итоге отбрасываются. В общем, Valgrind не может определить, действительно ли используются недопустимые байты из частичной загрузки (и обнаружение в целом, вероятно, очень сложно).
2 ответа
Да, это безопасно в x86 asm и существующей libc strlen(3) реализации используют в своих интересах это.
Насколько я знаю, это безопасно в C, скомпилированном для x86. Чтение вне объекта - это, конечно, неопределенное поведение в C, но оно хорошо определено для C-targetting-x86. Я думаю, что это не тот тип UB, который агрессивные компиляторы могут предположить, что он не может произойти во время оптимизации, но подтверждение от автора компилятора по этому вопросу было бы хорошо, особенно в тех случаях, когда во время компиляции можно легко доказать, что доступ выходит из строя. прошлого конца объекта. (См. Обсуждение в комментариях с @RossRidge: предыдущая версия этого ответа утверждала, что это было абсолютно безопасно, но что сообщение в блоге LLVM на самом деле не читается так).
Получаемые вами данные являются непредсказуемым мусором, но других побочных эффектов не будет. Пока на вашу программу не влияют байты мусора, это нормально. (например, используйте битхаки, чтобы найти один из байтов uint64_t равны нулю, затем цикл байтов, чтобы найти первый нулевой байт, независимо от того, какой мусор находится за его пределами.)
Точно так же создание не выровненных указателей с помощью приведения является стандартом C в стандарте C (даже если вы не разыменовываете их). Это хорошо определено во всех известных компиляторах Си при нацеливании на x86. Встроенные в Intel SSE даже требуют этого; например __m128i _mm_loadu_si128 (__m128i const* mem_addr) принимает указатель на невыровненный 16-байтовый __m128i,
(Для AVX512 они наконец-то изменили этот неудобный выбор дизайна на void* для новых внутренностей, таких как __m512i _mm512_loadu_si512 (void const* mem_addr)).
Даже разыменование неприсоединенного uint64_t* или же int* является безопасным (и имеет четко определенное поведение) в C, скомпилированном для x86. Однако разыменование __m128i* напрямую (вместо использования встроенных функций load/store) movdqa, который неисправен на невыровненных указателях.
Обычно такие циклы избегают касания каких-либо дополнительных строк кэша, которые им не нужны, не только страниц, из соображений производительности.
Крайне маловероятно, чтобы отображаемые в памяти регистры ввода-вывода находились на той же странице, что и буфер, который вы хотите зациклить при больших нагрузках, или, особенно, в той же строке кэша 64 ББ, даже если вы вызываете такие функции из драйвер устройства (или программа пользовательского пространства, такая как X-сервер, которая сопоставила пространство MMIO).
Если вы обрабатываете 60-байтовый буфер и вам нужно избегать чтения из 4-байтового регистра MMIO, вы будете знать об этом. Такая ситуация не бывает для нормального кода.
strlen является каноническим примером цикла, который обрабатывает буфер неявной длины и, таким образом, не может векторизоваться без чтения за концом буфера. Если вам нужно избежать чтения после окончания 0 байт, вы можете прочитать только один байт за раз.
Например, реализация glibc использует пролог для обработки данных вплоть до первой границы выравнивания 64B. Затем в основном цикле (ссылка gitweb на источник asm) он загружает целую строку кэша 64B, используя четыре выравниваемых загрузки SSE2. Он объединяет их в один вектор с pminub(мин. беззнаковых байтов), поэтому конечный вектор будет иметь нулевой элемент, только если любой из четырех векторов имеет ноль. Обнаружив, что конец строки находится где-то в этой строке кэша, он перепроверяет каждый из четырех векторов отдельно, чтобы увидеть, где. (Используя типичный pcmpeqb против вектора все-ноль, и pmovmskb / bsf чтобы найти положение в векторе.) glibc имел обыкновение выбирать из нескольких разных стратегий strlen, но текущая подходит для всех процессоров x86-64.
Одновременная загрузка 64B, конечно, безопасна только из указателя, выровненного по 64B, так как доступ с естественным выравниванием не может пересекать границы строки кэша или строки страницы.
Если вы заранее знаете длину буфера, вы можете избежать чтения за концом, обрабатывая байты за последним выровненным вектором, используя невыровненную загрузку, которая заканчивается на последнем байте буфера. (Опять же, это работает только с идемпотентными алгоритмами, такими как memcpy, которым все равно, перекрывают ли они хранилища в месте назначения. Алгоритмы модификации на месте часто не могут этого сделать, за исключением чего-то вроде преобразования строки в верхний в случае SSE2, где нормально обрабатывать данные, которые уже были переданы в регистр. Кроме останова пересылки магазина, если вы выполняете невыровненную загрузку, которая перекрывается с вашим последним выровненным хранилищем.)
Если вы разрешите рассмотрение устройств без CPU, то одним из примеров потенциально небезопасной операции является доступ к за пределами областей страниц памяти с отображением PCI. Нет гарантии, что целевое устройство использует тот же размер страницы или выравнивание, что и подсистема основной памяти. Попытка получить доступ, например, к адресу [cpu page base]+0x800 может вызвать сбой страницы устройства, если устройство находится в режиме страницы 2 КБ. Это обычно вызывает системную ошибку.