Безопасно ли читать конец конца буфера на одной странице на 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 в противном случае.

Во-первых, случаи с размером & lt; 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, и высокоуровневые вещи, такие как & lt; все остальное & gt;. По крайней мере, за пределами жесткой цифровой ниши, где Фортран все еще играет в мяч. Поэтому меня интересует представление вопроса на языке C-compiler-and-under, поэтому я не сформулировал его как вопрос о чистой сборке x86.

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

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

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

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

Ответы

Ответ 1

Да, это безопасно в x86 asm, и существующие реализации libc strlen(3) используют это в рукописном asm. И даже glibc fallback C, но он компилируется без LTO, поэтому он никогда не может быть встроенным. Это в основном использование C в качестве переносимого ассемблера для создания машинного кода для одной функции, а не как часть большой программы на C с встраиванием. Но это главным образом потому, что он также имеет потенциальный UB со строгим псевдонимом, см. мой ответ на связанной Q & A. Возможно, вы также захотите использовать GNU C __attribute__((may_alias)) typedef вместо обычного unsigned long, поскольку ваш более широкий тип, такой как __m128i и т.д., Уже используется.

Это безопасно, потому что выровненная нагрузка никогда не пересечет более высокую границу выравнивания, и защита памяти происходит с выровненными страницами, поэтому, по крайней мере, 4 тыс. Границ 1 Не может произойти сбой любой естественно выровненной нагрузки, которая касается хотя бы одного действительного байта.

В некоторых случаях может быть полезно просто проверить, что адрес находится достаточно далеко от границы следующей страницы 4k; это также безопасно. например отметьте ((p + 15) ^ p) & 0xFFF...F000 == 0 (LEA/XOR/TEST), который сообщает, что последний байт 16-байтовой загрузки имеет те же биты адреса страницы, что и первый байт. Или p+15 <= p|0xFFF (LEA/OR/CMP с лучшим ILP) проверяет, что последний байт-адрес загрузки & lt; = последний байт страницы, содержащей первый байт.

Насколько я знаю, он также безопасен на C, скомпилированном для x86. Чтение вне объекта, конечно, является неопределенным поведением в C, но работает в C-target-x86. Я не думаю, что компиляторы явно/специально определяют поведение, но на практике это работает таким образом.

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

Это требуется в asm, чтобы быстрее, чем 1 байт, обрабатывать строку неявной длины. В C теоретически компилятор может знать, как оптимизировать такой цикл, но на практике это не так, поэтому приходится делать подобные хаки. До тех пор, пока это не изменится, я подозреваю, что люди, заботящиеся о компиляторах, обычно избегают взлома кода, содержащего этот потенциальный UB.

Там нет никакой опасности, когда перечитывание не видно для кода, который знает, как долго объект. Компилятор должен создать asm, который работает для случая, когда есть элементы массива, насколько мы на самом деле читаем. Вероятная опасность, которую я вижу с возможными будущими компиляторами, заключается в следующем: после встраивания компилятор может увидеть UB и решить, что этот путь выполнения никогда не следует выбирать. Или, что условие завершения должно быть найдено перед последним неполным вектором и пропустить его при полной развертке.

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

Необычные ситуации, когда это не безопасно в x86 asm

  • Точки останова аппаратных данных (точки наблюдения), которые запускаются при загрузке с заданного адреса. Если есть переменная, которую вы отслеживаете сразу после массива, вы можете получить ложный удар. Это может быть небольшим раздражением для того, кто отлаживает обычную программу. Если ваша функция будет частью программы, которая использует отладочные регистры x86 D0-D3 и возникающие исключения для чего-то, что может повлиять на корректность, то будьте осторожны с этим.

  • В гипотетической 16 или 32-битной ОС, которая использует сегментацию: ограничение сегмента может использовать 4-килобайтную или 1-байтовую гранулярность, поэтому можно создать сегмент с первым ошибочным смещением странный. (Выравнивание базы сегмента по строке или странице кэша не имеет значения, за исключением производительности). Все основные операционные системы x86 используют модели с плоской памятью, а x86-64 убирает поддержку ограничений сегментов для 64-битного режима.

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

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

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

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

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

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

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

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

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

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

Но даже если он виден во время компиляции, он обычно не мешает текущим компиляторам.

PS: в предыдущей версии этого ответа утверждалось, что не выровненное значение int * было также безопасно в C, скомпилированном для x86. Это не так. Я был слишком кавалером 3 года назад, когда писал эту часть. Вам нужен typedef __attribute__((aligned(1))) или memcpy, чтобы сделать это безопасным.

Набор вещей, который ISO C оставляет неопределенным, но то, что для встроенных функций Intel требуются компиляторы, определяет создание не выровненных указателей (по крайней мере, с такими типами, как __m128i*), но не разыменовывает их напрямую. Является ли reinterpret_cast между аппаратным указателем вектора и соответствующим типом неопределенным поведением?

Ответ 2

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