Обработка вызовов (потенциально) заблаговременно скомпилированных функций из кода JITed

Этот вопрос был отложен как слишком широкий, по-видимому, из-за исследования, которое я включил, чтобы "показать свою работу" вместо того, чтобы задавать вопрос с минимальными усилиями. Чтобы исправить это, позвольте мне суммировать весь вопрос в одном предложении (спасибо @PeterCordes за эту фразу):

Как эффективно вызвать (x86-64) заранее скомпилированные функции (которые я контролирую, может быть дальше, чем 2 ГБ) из кода JITed (который я генерирую)?

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

Обратите внимание, что ни один из вопросов, поставленных ниже, не является ответом на мои вопросы; они более риторически. Их цель - продемонстрировать, почему я не могу ответить на вышеуказанный вопрос (несмотря на мои исследования, мне не хватает опыта в этой области, чтобы делать определенные утверждения, такие как @PeterCordes), прогнозирование ветвей скрывает задержку выборки и проверки указателя функции из памяти, при условии, что это хорошо предсказывает. ") Также обратите внимание, что компонент Rust здесь в значительной степени не имеет значения, так как это проблема сборки. Мои соображения по поводу включения этого были в том, что заранее скомпилированные функции написаны на Rust, поэтому я не был уверен, что есть что-то, что Rust сделал (или проинструктировал LLVM), что может быть выгодно в этой ситуации. Для ответа вполне приемлемо вообще не учитывать Rust; на самом деле, я ожидаю, что это будет так.

Думайте о следующем, как о работе с царапинами на обратной стороне экзамена по математике:

Примечание: я запутал термин "внутренние" здесь. Как отмечается в комментариях, "заранее скомпилированные функции" - лучшее описание. Ниже я сокращу, что функции AOTC.

Я пишу JIT в Rust (хотя Rust имеет отношение только к части моего вопроса, основная часть этого относится к соглашениям JIT). У меня есть функции AOTC, которые я реализовал в Rust и которые мне нужно call из кода, генерируемого моим JIT. Мой JIT mmap(_, _, PROT_EXEC, MAP_ANONYMOUS | MAP_SHARED) несколько страниц для объединенного кода. У меня есть адреса моих функций AOTC, но, к сожалению, они намного дальше, чем 32-битное смещение. Я пытаюсь решить, как отправлять вызовы этих функций AOTC. Я рассмотрел следующие варианты (это не вопросы, на которые нужно отвечать, просто демонстрирую, почему я не могу ответить на основной вопрос этой SO-темы):

(Специфично для Rust) Каким-то образом заставьте Rust разместить функции AOTC близко (возможно, к?) Кучи, чтобы call находился в пределах 32-битного смещения. Непонятно, что это возможно с Rust (есть способ указать собственные аргументы компоновщика, но я не могу сказать, к чему они применяются, и могу ли я указать одну функцию для перемещения. И даже если бы я мог, куда я могу поместить Это?). Также кажется, что это может потерпеть неудачу, если куча достаточно велика.
(Специфично для ржавчины) Распределите мои страницы JIT ближе к функциям AOTC. Это может быть достигнуто с помощью mmap(_, _, PROT_EXEC, MAP_FIXED), но я не уверен, как выбрать адрес, который не загромождает существующий код Rust (и соблюдает ограничения арки - есть ли разумный способ получить те ограничения?).
Создайте заглушки на страницах JIT, которые обрабатывают абсолютный переход (код ниже), а затем call заглушки. Это имеет то преимущество, что (исходный) сайт вызова в коде JITted является хорошим небольшим относительным вызовом. Но неправильно прыгать через что-то. Похоже, что это отрицательно сказывается на производительности (возможно, мешает прогнозированию RAS/адреса перехода). Кроме того, кажется, что этот переход будет медленнее, так как его адрес является косвенным, и это зависит от mov для этого адреса.

mov rax, {ABSOLUTE_AOTC_FUNCTION_ADDRESS}
jmp rax

Реверс (3), просто вставка вышеупомянутого на каждом внутреннем сайте вызова в коде JITed. Это решает проблему косвенного обращения, но увеличивает код JITted (возможно, это приводит к кешу команд и последствиям декодирования). Он по- прежнему имеет вопрос о том, что переход является непрямым и зависит от mov.
Разместите адреса функций AOTC на странице PROT_READ (только) рядом со страницами JIT. Сделайте все сайты вызовов рядом, абсолютно косвенные вызовы (код ниже). Это удаляет второй уровень косвенности из (2). Но код этой инструкции, к сожалению, большой (6 байт), поэтому он имеет те же проблемы, что и (4). Кроме того, теперь вместо зависимости от регистра переходы без необходимости (поскольку адрес известен во время JIT) зависят от памяти, что, безусловно, влияет на производительность (несмотря на то, что эта страница кэшируется?).

aotc_function_address:
    .quad 0xDEADBEEF

# Then at the call site
call qword ptr [rip+aotc_function_address]

Futz с регистром сегмента, чтобы разместить его ближе к функциям AOTC, чтобы можно было выполнять вызовы относительно этого регистра сегмента. Кодирование такого вызова является длинным (поэтому, возможно, у него есть проблемы с конвейерным декодированием), но кроме этого это в значительной степени позволяет избежать множества хитрых битов всего, что было до него. ~~Но, возможно, вызов относительно сегмента non- cs работает плохо.~~ ~~Или, может быть, такое размышление не является разумным (например, портит среду выполнения Rust).~~ (как отмечает @prl, это не работает без дальнего вызова, что ужасно для производительности)
Не совсем решение, но я мог бы сделать компилятор 32-битным и вообще не иметь этой проблемы. Это не очень хорошее решение, и оно также помешало бы мне использовать расширенные регистры общего назначения (из которых я использую все).

Все представленные варианты имеют недостатки. Вкратце, 1 и 2 - единственные, которые, похоже, не влияют на производительность, но неясно, есть ли non- хакерский способ их достижения (или вообще какой-либо способ в этом отношении). 3-5 не зависят от Rust, но имеют очевидные недостатки производительности.

Учитывая этот поток сознания, я пришел к следующему риторическому вопросу (который не нуждается в явных ответах), чтобы продемонстрировать, что мне не хватает знаний, чтобы самостоятельно ответить на основной вопрос этой SO-темы. Я ударил их, чтобы было совершенно ясно, что я не излагаю все это - часть моего вопроса.

Для подхода (1), возможно ли заставить Rust связать определенные extern "C" по определенному адресу (около кучи)? Как выбрать такой адрес (во время компиляции)? Безопасно ли предполагать, что любой адрес, возвращаемый mmap (или выделяемый Rust), будет в пределах 32-битного смещения от этого местоположения?
Для подхода (2), как я могу найти подходящее место для размещения JIT-страниц (так, чтобы оно не затирало существующий код Rust)?

И некоторые JIT (non- Rust) конкретные вопросы:

Для подхода (3), заглушки будут препятствовать производительности достаточно, чтобы я заботился? Как насчет косвенного jmp? Я знаю, что это несколько напоминает заглушки компоновщика, за исключением того, что, как я понимаю, заглушки компоновщика разрешаются, по крайней мере, только один раз (поэтому они не должны быть косвенными?). Используют ли какие-нибудь JIT эту технику?
Для подхода (4), если косвенный вызов в 3 в порядке, стоит ли встраивать вызовы? Если в JIT обычно используется подход (3/4), лучше ли этот вариант?
Для подхода (5) плохая зависимость скачка от памяти (учитывая, что адрес известен во время компиляции)? Это сделает это менее производительным, чем (3) или (4)? Используют ли какие-нибудь JIT эту технику?
Для подхода (6) такое фьюзинг неразумно? (Специфично для Rust) Имеется ли сегментный регистр (не используемый средой выполнения или ABI) для этой цели? Будут ли вызовы относительно сегмента non- cs такими же производительными, как и вызовы относительно cs?
И, наконец (и самое главное), есть ли лучший подход (возможно, более часто используемый JIT), который я здесь упускаю?

Я не могу реализовать (1) или (2) без ответов на мои вопросы Rust. Я мог бы, конечно, реализовать и протестировать 3-5 (возможно, 6, хотя было бы неплохо знать о смещении регистра сегментов заранее), но, учитывая, что это очень разные подходы, я надеялся, что существует литература по этому вопросу, которая Я не мог найти, потому что я не знал правильных терминов для Google (я также в настоящее время работаю над этими тестами). Или, может быть, кто-то, кто вникает во внутреннее устройство JIT, может поделиться своим опытом или тем, что он обычно видел?

Мне известен этот вопрос: переходы на JIT (x86_64). Он отличается от моего, потому что речь идет о соединении базовых блоков (и принятым решением является слишком много инструкций для часто называемого встроенного). Мне также известно о вызове абсолютного указателя в машинном коде x86, который, хотя и обсуждает схожие темы с моим, отличается, потому что я не предполагаю, что абсолютные переходы необходимы (например, подходы 1-2 позволят избежать их).

Ответ 1

Резюме: попробуйте выделить память возле вашего статического кода. Но для вызовов, которые не могут связаться с rel32, вернитесь к call qword [rel pointer] или встроенному mov r64,imm64/call r64.

Ваш механизм 5., вероятно, лучше всего подходит для производительности, если вы не можете 2. работать, но 4. он прост и должен быть в порядке. Прямой call rel32 требует некоторого предсказания ветвлений, но он определенно все же лучше.

Терминология: "внутренние функции", вероятно, должны быть "вспомогательными" функциями. "Внутренний" обычно означает либо встроенный язык (например, значение на Фортране), либо "не настоящая функция, просто что-то, что указывает на машинную инструкцию" (C/C++/значение Rust, как для SIMD, или что-то вроде _mm_popcnt_u32(), _pdep_u32() или _mm_mfence()). Ваши функции Rust собираются для компиляции с реальными функциями, которые существуют в машинном коде, который вы собираетесь вызывать с call инструкций call.

Да, распределение буферов JIT в пределах +-2GiB ваших целевых функций, очевидно, идеально, позволяя выполнять прямые вызовы rel32.

Наиболее простым было бы использовать большой статический массив в BSS (который компоновщик поместит в пределах 2 ГБ вашего кода) и выделить из этого ваши выделения. (Используйте mprotect (POSIX) или VirtualProtect (Windows), чтобы сделать его исполняемым).

Большинство ОС (включая Linux) выполняют ленивое выделение для BSS (отображение COW на нулевой странице, выделяя только физические фреймы страницы, чтобы поддержать это выделение, когда оно записано, точно так же, как mmap без MAP_POPULATE), поэтому он тратит только виртуальное адресное пространство, чтобы иметь 512MiB массив в BSS, который вы используете только нижние 10kB.

Не делайте его больше или близким к 2 ГБ, тем не менее, потому что это отодвинет другие вещи в BSS слишком далеко. Модель "маленького" кода по умолчанию (как описано в x86-64 System V ABI) помещает все статические адреса в пределах 2 ГБ друг от друга для адресации данных, относящихся к RIP, и вызова rel32/jmp.

Недостаток: вам придется написать хотя бы простой распределитель памяти самостоятельно, вместо того, чтобы работать с целыми страницами с помощью mmap/munmap. Но это легко, если вам не нужно ничего освобождать. Возможно, просто сгенерируйте код, начинающийся с адреса, и обновите указатель, как только вы дойдете до конца, и выясните, как долго ваш блок кода. (Но это не многопоточность...) В целях безопасности не забудьте проверить, когда вы доберетесь до конца этого буфера и прервитесь или вернетесь к mmap.

Если ваши абсолютные целевые адреса находятся на низком 2 ГБ виртуального адресного пространства, используйте mmap(MAP_32BIT) в Linux. (Например, если ваш код Rust скомпилирован в исполняемый файл не-PIE для Linux x86-64. Но это не относится к исполняемым файлам PIE (обычно в наши дни) или к целям в общих библиотеках. Это можно обнаружить при запуске время, проверив адрес одной из ваших вспомогательных функций.)

В целом (если MAP_32BIT не полезен/недоступен), лучше всего делать ставку на mmap без MAP_FIXED, но с ненулевым адресом подсказки, который, по вашему мнению, является бесплатным.

В Linux 4.17 появился MAP_FIXED_NOREPLACE который позволял бы вам легко искать ближайший неиспользуемый регион (например, шаг по 64 МБ и повторить попытку, если вы получили EEXIST, затем запомните этот адрес, чтобы избежать поиска в следующий раз). В противном случае вы можете проанализировать /proc/self/maps один раз при запуске, чтобы найти не отображенное пространство рядом с отображением, которое содержит адрес одной из ваших вспомогательных функций. Будет близко друг к другу.

Обратите внимание, что более старые ядра, которые не распознают флаг MAP_FIXED_NOREPLACE, обычно (после обнаружения коллизии с существующим отображением) возвращаются к типу поведения "не MAP_FIXED": они будут возвращать адрес, отличный от запрошенного адреса.

На следующей более высокой или более низкой свободной странице (страницах) было бы идеально иметь неразреженную карту памяти, чтобы таблице страниц не требовалось слишком много различных каталогов страниц верхнего уровня. (Таблицы страниц HW представляют собой основополагающее дерево.) И как только вы найдете место, которое работает, сделайте будущие распределения непрерывными с этим. Если вы в конечном итоге используете там много места, ядро может оппортунистически использовать огромную страницу размером 2 МБ, и если ваши страницы снова будут смежными, это означает, что они совместно используют один и тот же каталог родительских страниц в таблицах страниц HW, поэтому iTLB пропускает запуск просмотра страниц может быть немного дешевле ( если эти верхние уровни остаются горячими в кэшах данных или даже кешируются внутри самого оборудования Pagewalk). И для эффективного для ядра, чтобы отслеживать как одно большее отображение. Конечно, использование большего количества уже выделенной страницы еще лучше, если есть место. Лучшая плотность кода на уровне страницы помогает инструкции TLB, и, возможно, также на странице DRAM (но это не обязательно тот же размер, что и страница виртуальной памяти).

Затем, когда вы делаете code-gen для каждого вызова, просто проверьте, находится ли цель в диапазоне для call rel32 с off == (off as i32) as i64
иначе вернемся к 10- mov r64,imm64/call r64. (rustcc скомпилирует это в movsxd/cmp, поэтому проверка каждый раз имеет только тривиальные затраты для JIT-компиляции.)

(Или 5-байтовый mov r32,imm32 если возможно mov r32,imm32 системы, которые не поддерживают MAP_32BIT могут все еще иметь целевые адреса внизу. Проверьте это с target == (target as u32) as u64. Третье кодирование mov -immediate, 7-байтовый mov r/m64, sign_extended_imm32, вероятно, не интересен, если вы не JITing код ядра для ядра, отображенного в высокий 2 ГБ виртуального адресного пространства.)

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

Альтернативы mov-imm/call reg

mov r64,imm64 - это 10-байтовая инструкция, которая немного велика для извлечения/декодирования и для хранения uop-кэша. И может потребоваться дополнительный цикл для чтения из кэша UOP в семействе SnB в соответствии с микроархом Agner Fog pdf (https://agner.org/optimize). Но современные процессоры имеют довольно хорошую пропускную способность для выборки кода и надежные внешние интерфейсы.

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

Кстати, если какая-либо из ваших функций является переменной, x86-64 System V требует, чтобы вы передали AL = количество аргументов XMM, вы можете использовать r11 для указателя функции. Это call-clobbered и не используется для передачи аргументов. Но RAX (или другой "устаревший" регистр) сохранит префикс REX при call.

Распределить функции Rust рядом с mmap где будет mmap

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

mmap имеет более 4 ГБ свободного виртуального адресного пространства на выбор. Вы не знаете заранее, где он будет выделяться. (Хотя я думаю, что Linux, по крайней мере, сохраняет некоторую локальность, чтобы оптимизировать таблицы страниц HW.)

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

call rel32 для заглушек, которые используют mov/jmp reg
Похоже, что это отрицательно сказывается на производительности (возможно, мешает прогнозированию RAS/адреса перехода).

Недостатком "перфект" является только наличие 2 общих инструкций по вызову/прыжку для внешнего интерфейса, прежде чем он сможет передать фону полезные инструкции. Это не здорово; 5. намного лучше

Это в основном то, как PLT работает для вызовов функций разделяемой библиотеки в Unix/Linux, и будет выполнять то же самое. Вызов через функцию-заглушку PLT (Table Linking Table) почти такой же. Таким образом, влияние на производительность было хорошо изучено и сопоставлено с другими способами работы. Мы знаем, что динамические вызовы библиотек не являются проблемой производительности.

Звездочка перед адресом и инструкциями push, куда ее подталкивают? показывает разборку AT & T одной или одношаговой C-программы, такой как main(){puts("hello"); puts("world");} main(){puts("hello"); puts("world");} если вам интересно. (При первом вызове он помещает аргумент arg и переходит к функции отложенного динамического компоновщика; при последующих вызовах целью косвенного перехода является адрес функции в общей библиотеке.)

Почему PLT существует в дополнение к GOT, а не просто к использованию GOT? объясняет больше. jmp, адрес которого обновляется путем ленивых ссылок, является jmp qword [[email protected]]. (И да, PLT здесь действительно использует jmp косвенной памятью, даже на i386, где будет работать перезаписанный jmp rel32. IDK, если GNU/Linux когда-либо исторически использовался для перезаписи смещения в jmp rel32.)

jmp - это просто стандартный хвостовой вызов, и он не разбалансирует стек предикторов обратных адресов. ret в целевой функции вернется к инструкции после исходного call, то есть к адресу, который call помещен в стек вызовов и в микроархитектурный RAS. Только если вы использовали push/ret (например, "retpoline" для смягчения Spectre), вы бы разбалансировали RAS.

Но код в Jumps для JIT (x86_64), который вы связали, к сожалению, ужасен (см. Мой комментарий под ним). Это сломает RAS для будущих возвратов. Вы могли бы подумать, что он сломает его только для этого вызова (чтобы получить адрес возврата, который нужно скорректировать), если балансировать push/ret, но на самом деле call +0 - это особый случай, который не идет на RAS в большинстве процессоров: http://blog.stuffedcow.net/2018/04/ras-microbenchmarks. (вызов nop может измениться, я думаю, но все это совершенно безумие против call rax если только он не пытается защититься от эксплойтов Spectre.) Обычно на x86-64 вы используете REA-относительный LEA для получения соседнего адреса в регистр, а не call/pop.

встроенный mov r64, imm64/call reg

Это, вероятно, лучше, чем 3; Стоимость внешнего кода с большим размером кода, вероятно, ниже, чем стоимость вызова через заглушку, использующую jmp.

Но это также, вероятно, достаточно хорошо, особенно если ваши методы alloc-inside-2GiB работают достаточно хорошо большую часть времени на большинстве целей, которые вас интересуют.

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

call qword [rel nearby_func_ptr]

Вот как gcc -fno-plt компилирует вызовы функций совместно используемой библиотеки в Linux (call [rip + [email protected]]) и как обычно выполняются вызовы функций Windows DLL. (Это похоже на одно из предложений http://www.macieira.org/blog/2012/01/sorry-state-of-dynamic-libraries-on-linux/)

call [RIP-relative] составляет 6 байтов, всего на 1 байт больше, чем call rel32, поэтому он оказывает незначительное влияние на размер кода по сравнению с вызовом заглушки. addr32 call rel32 факт: иногда вы видите addr32 call rel32 в машинном коде (префикс размера адреса не имеет никакого эффекта, кроме заполнения). Это происходит из-за того, что компоновщик call [RIP + [email protected]] для call rel32 если во время компоновки был обнаружен символ с call rel32 видимостью ELF в другом .o, а не в другом общем объекте.

Для вызовов из общей библиотеки это обычно лучше, чем заглушки PLT, с единственным недостатком - более медленный запуск программы, поскольку она требует раннего связывания (не ленивое динамическое связывание). Это не проблема для вас; целевой адрес известен раньше времени генерации кода.

Автор патча проверил его производительность по сравнению с традиционным PLT на неизвестном оборудовании x86-64. Clang, возможно, является наихудшим сценарием для вызовов совместно используемой библиотеки, поскольку он выполняет много вызовов небольших функций LLVM, которые не занимают много времени, и он долго выполняется, поэтому затраты на раннее связывание при запуске незначительны. После использования gcc и gcc -fno-plt для компиляции clang время для clang -O2 -g для компиляции tramp3d увеличивается с 41.6 с (PLT) до 36.8 с (-fno-plt). clang --help становится немного медленнее.

(x86-64 PLT окурки использовать jmp qword [[email protected]], не mov r64,imm64/jmp, хотя. Память косвенную jmp только один моп на современных процессорах Intel, так что дешевле на правильный прогноз, но, может быть, медленнее при неправильном прогнозировании, особенно если запись GOTPLT отсутствует в кэше. Если она часто используется, она обычно будет правильно предсказывать, хотя. Но в любом случае 10-байтовые movabs и 2-байтовый jmp могут быть извлечены как блок (если он подходит 16-байтовый блок выборки) и декодирование за один цикл, поэтому 3. не является абсолютно необоснованным. Но это лучше.)

При выделении места для ваших указателей помните, что они извлекаются как данные, в кэш L1d, и с записью dTLB, а не iTLB. Не чередуйте их с кодом, который будет тратить пространство в I-кэше на эти данные, и тратить пространство в D-кэше на строки, содержащие один указатель и в основном код. Сгруппируйте ваши указатели вместе в отдельном 64-байтовом фрагменте из кода, чтобы строка не обязательно находилась как в L1I, так и в L1D. Хорошо, если они находятся на той же странице, что и некоторый код; они доступны только для чтения, поэтому не будут вызывать нюки конвейера с самоизменяющимся кодом.