Байт-кодовые VM в неожиданных местах

Отвечая на вопрос в Twitter, Ричард Хипп написал, почему SQLite использует байт-кодовую VM для исполнения операторов SQL.

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

▍ eBPF

Знали ли вы, что внутри ядра Linux есть механизм расширения, включающий в себя интерпретатор байт-кода и JIT-компилятор?

Я понятия не имел. Он называется eBPF, и это довольно интересная вещь: регистровая VM с десятью регистрами общего назначения и более чем сотней опкодов.

BPF в аббревиатуре eBPF расшифровывается как Berkeley packet filter, основная идея этого фильтра описана в статье USENIX 1993 года:

Во многих версиях Unix есть механизмы для перехвата пакетов пользовательского уровня, позволяющие использовать рабочие станции общего назначения для сетевого мониторинга. Так как сетевые мониторы исполняются как процессы пользовательского уровня, пакеты необходимо копировать через границу защиты между ядром и пользовательским пространством. Это копирование можно минимизировать, реализовав агент ядра под названием packet filter, который отклоняет нежелательные пакеты на максимально раннем этапе. Изначальный фильтр пакетов Unix был спроектирован на основе стекового анализатора фильтров, работающего неоптимально на текущем поколении RISC CPU. В BSD Packet Filter (BPF) используется новый регистровый анализатор фильтров, который может быть до двадцати раз быстрее, чем исходный.

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

В патче 2011 года был добавлен JIT-компилятор для x86-64. В 2012-м появился первый несетевой сценарий использования. В 2014 году реализация BPF существенно расширилась в сторону превращения в универсальную виртуальную машину внутри ядра:

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

▍ Выражения DWARF

DWARF — это формат файлов, используемый компиляторами наподобие GCC и LLVM для включения в скомпилированные двоичные файлы отладочной информации. Допустим, вы хотите отладить следующий код на C++:

void add_two(int x)
{
    int ans = x + 2;
    return ans + 2; // Oops!
}

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

Решение заключается в том, чтобы позволить компилятору указать выражение, вычисляющее значение локальной переменной. Поэтому в спецификацию DWARF добавили язык выражений:

2.5 Выражения DWARF

Выражения DWARF описывают способ вычисления значения или указания места. Они задаются операциями DWARF, работающими со стеком значений.

Выражение DWARF кодируется как поток операций, каждая из которых состоит из опкода с последующим нулём или более литеральных операндов. Количество операндов определяется в зависимости от опкода.

Вычислением выражений занимается отладчик. В GDB и LLDB есть интерпретатор на основе switch для выражений DWARF. [Подробности по LLDB см. в lldb/source/Expression/DWARFExpression.cpp. Подробности по GDB см. в gdb/dwarf2/expr.c.]

▍ Выражения агентов GDB

Но оказывается, что в GDB тоже есть ещё один интерпретатор байт-кода!

При помощи команд GDB trace и collect пользователь может указывать места в программе и произвольные выражения, которые вычисляются при достижении этих мест.

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

Байт-кодовый язык прост: в нём около сорока с лишним опкодов, большинство из которых представляет собой обычный список операндов C (сложение, вычитание, сдвиги и так далее), операции с различными размерами литералов и обращением к памяти. Интерпретатор байт-кода работает строго со значениями на машинном уровне (с integer и float разного размера) и не требует никакой информации о типах или символах; то есть внутренние структуры данных интерпретатора просты, а для реализации каждого байт-кода требуется лишь несколько нативных машинных команд. Интерпретатор мал, а строгие ограничения на память и время, необходимые для вычисления выражения, легко определить, благодаря чему он подходит для применения агентом отладки в приложениях реального времени.

(Из Debugging with GDB, Appendix F: The GDB Agent Expression Mechanism)

▍ WinRAR

WinRAR — это Windows-утилита для сжатия файлов с проприетарным форматом файлов. Работающий в Google исследователь уязвимостей Тэвис Орманди обнаружил, что для преобразования данных формат RAR использует кодирование байт-кода:

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

В его репозитории rarvmtools также представлены подробности об архитектуре:

Для понимания полезно будет знакомство с x86 (предпочтительнее синтаксис ассемблера Intel).

В RarVM есть 8 именованных регистров (с r0 по r7). r7 используется в качестве указателя стека для операций, связанных со стеком (таких как push, call, pop и так далее). Как и в x86, регистру r7 можно присвоить любое значение, однако если вы будете делать с ним что-то, связанное со стеком, то в течение этой операции значение будет маскировано, чтобы уместиться в адресное пространство.

Ещё несколько примеров:

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