Безопасно ли читать конец конца буфера на одной странице на x86 и x64?

Многие методы, найденные в высокопроизводительных алгоритмах, могут быть упрощены (и), если им разрешено читать небольшую сумму за конец входных буферов. Здесь «небольшое количество» обычно означает до W - 1 байта за конец, где W – это размер слова в байтах алгоритма (например, до 7 байтов для алгоритма, обрабатывающего вход в 64-битных fragmentах).

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

Однако в специальном случае считывания выровненных значений ошибка страницы кажется невозможной, по крайней мере, на x86. На этой платформе страницы (и, следовательно, флаги защиты памяти) имеют размерность 4K (возможны большие страницы, например, 2MiB или 1GiB, но они кратные 4K), и поэтому выровненные чтения будут обращаться только к байтам на той же странице, что и действительные часть буфера.

Вот канонический пример некоторого цикла, который выравнивает его вход и считывает до 7 байтов за конец буфера:

 int processBytes(uint8_t *input, size_t size) { uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size); int res; if (size = 0) { return input + res; } // align pointer to the next 8-byte boundary input64 = (ptrdiff_t)(input64 + 1) & ~0x7; for (; 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, и пользователь проверил, что он скомпилирован ожидаемым способом (т. Е. Компилятор не использовал ansible частично доступ к ограниченному доступу, чтобы сделать что-то действительно умный , выполняет скомпилированную программу в безопасности?

В этом отношении этот вопрос является вопросом C и вопросом сборки x86. Большая часть кода, использующего этот трюк, который я видел, написан на C, а C по-прежнему является доминирующим языком для высокопроизводительных библиотек, легко затмевает материал более низкого уровня, такой как asm, и материал более высокого уровня, такой как . По крайней мере, вне хардкорной числовой ниши, где FORTRAN по-прежнему играет в мяч. Поэтому меня интересует представление C-компилятора и ниже этого вопроса, поэтому я не сформулировал его как вопрос о сборке x86.

Все, что было сказано, пока меня только умеренно интересует ссылка на стандарт, показывающий, что это UD, меня очень интересуют любые детали фактических реализаций, которые могут использовать этот конкретный UD для создания неожиданного кода. Теперь я не думаю, что это может произойти без какого-либо глубокого глубокого кросс-процедурного анализа, но материал переполнения gcc удивил многих людей …


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

2 Примечание для этого перекрытия для работы требуется, чтобы эта функция и функция match() вели себя определенным образом идемпотентным способом – в частности, что возвращаемое значение поддерживает перекрывающиеся проверки. Таким образом, «поиск первого шаблона соответствия байтов» работает, поскольку все вызовы match() все еще находятся в порядке. Однако метод «совпадение байтов байтов» не сработает, так как некоторые байты могут быть подсчитаны в два раза. В стороне: некоторые функции, такие как вызов «вернуть минимальный байт», будут работать даже без ограничения в порядке, но нужно изучить все байты.

3 Здесь стоит отметить, что для Memcheck valgrind существует флаг , --partial-loads-ok который контролирует, действительно ли такие чтения считаются ошибкой. По умолчанию да , означает, что в целом такие нагрузки не рассматриваются как немедленные ошибки, но прилагаются усилия для отслеживания последующего использования загруженных байтов, некоторые из которых действительны, а некоторые из них не являются, при этом ошибка помечена если используются байты вне диапазона. В таких случаях, как приведенный выше пример, в котором доступно полное слово в match() , такой анализ завершит доступ к байтам, хотя результаты в конечном итоге будут отброшены. Valgrind не может вообще определить, действительно ли используются недействительные байты от частичной нагрузки (и обнаружение вообще, вероятно, очень сложно).

Да, это безопасно в x86 asm, и существующие реализации libc strlen(3) используют это.

Насколько я знаю, это также безопасно в C, скомпилированном для x86. Чтение вне объекта – это, конечно, неопределенное поведение на C, но оно хорошо определено для C-targeting-x86. Я думаю, что это не тот тип UB, который агрессивные компиляторы предполагают, не может произойти при оптимизации , но подтверждение от автора-компилятора в этом вопросе было бы хорошим, особенно для случаев, когда во время компиляции легко получить доступ к доступу прошлого конца объекта. (См. Обсуждение в комментариях с @RossRidge: предыдущая версия этого ответа утверждала, что это абсолютно безопасно, но это сообщение блога LLVM на самом деле не читается).

Данные, которые вы получаете, представляют собой непредсказуемый мусор, но никаких других потенциальных побочных эффектов не будет. Пока ваша программа не зависит от байтов мусора, все в порядке. (например, использовать bithacks, чтобы найти, если один из байтов uint64_t равен нулю , а затем байтовый цикл, чтобы найти первый нулевой байт, независимо от того, какой мусор находится за его пределами.)


Точно так же создание невыровненных указателей с аккомпанементом является UB в стандарте C (даже если вы их не разыскиваете). Он хорошо определен во всех известных компиляторах C при ориентации x86. Интеграция Intel SSE даже требует этого; например, __m128i _mm_loadu_si128 (__m128i const* mem_addr) принимает указатель на __m128i 16-байтовый __m128i .

(Для AVX512 они, наконец, изменили этот неудобный выбор дизайна для void* для новых встроенных __m512i _mm512_loadu_si512 (void const* mem_addr) таких как __m512i _mm512_loadu_si512 (void const* mem_addr) ).

Даже разыменование uint64_t* или int* является безопасным (и имеет четко определенное поведение) в C, скомпилированном для x86. Однако разыменование __m128i* напрямую (вместо использования movdqa загрузки / хранения) будет использовать movdqa , которые являются ошибками на невыровненных указателях.


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

Крайне маловероятно, что на той же странице будут отображаться регистры ввода-вывода с памятью, которые вы хотите перебрать с широкими нагрузками или, в особенности, с той же линией кэша 64B, даже если вы вызываете такие функции из драйвер устройства (или программа пространства пользователя, такая как X-сервер, который отображает некоторое пространство MMIO).

Если вы обрабатываете 60-байтовый буфер и вам нужно избегать чтения из 4-байтового регистра MMIO, вы об этом узнаете. Такая ситуация не возникает для обычного кода.


strlen – это канонический пример цикла, который обрабатывает буфер неявной длины и, следовательно, не может векторизоваться без прочтения конца буфера. Если вам нужно избегать чтения за завершающим 0 байтом, вы можете читать только один байт за раз.

Например, реализация glibc использует prolog для обработки данных до первой границы выравнивания 64B. Затем в основном цикле (ссылка gitweb на источник asm) он загружает целую линию кэша 64B, используя четыре выравниваемых нагрузки SSE2. Он объединяет их в один вектор с pminub (min беззнаковых байтов), поэтому конечный вектор будет иметь нулевой элемент, только если у любого из четырех векторов был ноль. Узнав, что конец строки находится где-то в этой строке кэша, он повторно проверяет каждый из четырех векторов отдельно, чтобы увидеть, где. (Используя типичный pcmpeqb для вектора all-zero и pmovmskb / bsf чтобы найти позицию внутри вектора.) Glibc использовал несколько разных страtagsй strlen на выбор , но текущий на всех x86-64 хорош ЦП.


Загрузка 64B за раз, конечно, безопасна только с 64-битного указателя, поскольку естественно выровненные обращения не могут пересекать границы линии кэша или строки страницы .


Если вы заранее знаете длину буфера, вы можете избежать прочтения конца, обработав байты за последним выровненным вектором, используя невыложенную нагрузку, которая заканчивается в последнем байте буфера. (Опять же, это работает только с идемпотентными алгоритмами, такими как memcpy, которые не заботятся о том, перекрывают ли они хранилища в место назначения. Модифицированные локальные алгоритмы часто не могут этого сделать, кроме как с преобразованием строки в верхнюю строку, case с SSE2 , где нормально обрабатывать данные, которые уже были добавлены. Кроме хранилища пересылки, если вы выполняете невыложенную нагрузку, которая перекрывается с вашим последним выровненным хранилищем.)

Если вы разрешаете рассмотрение не-ЦП устройств, то один пример потенциально опасной операции – это доступ к областям вне границ страниц с отображением карты PCI . Нет никакой гарантии, что целевое устройство использует один и тот же размер страницы или выравнивание в качестве основной подсистемы памяти. Попытка доступа, например, к адресу [cpu page base]+0x800 может вызвать ошибку страницы устройства, если устройство находится в режиме страницы 2KiB. Обычно это приводит к ошибке системы.

  • Visual Studio 2010: ссылочные сборки Ориентация на версию с более высокой версией
  • Что регистрирует сохранение в соглашении вызова ARM C?
  • C #: зачем подписывать сборку?
  • Как объединить несколько сборок в один?
  • x86_64 - Условия сборки и выход из строя
  • Как загрузить сборку в AppDomain со всеми ссылками рекурсивно?
  • Как ссылаться на сборки .NET с помощью PowerShell
  • Поиск всех пространств имен в сборке с использованием Reflection (DotNET)
  • использование ILMerge с библиотеками .NET 4
  • Как вы прокручиваете загруженные в настоящее время сборки?
  • Проверьте, равен ли регистр нулю с помощью CMP reg, 0 против OR reg, reg?
  • Давайте будем гением компьютера.