Интерпретаторы байт-кодов своими руками
Виртуальные машины языков программирования в последние десятилетия получили весьма широкое распространение. С презентации Java Virtual Machine во второй половине 90-х прошло уже достаточно много времени, и можно с уверенностью сказать, что интерпретаторы байт-кодов — не будущее, а настоящее.
Но данная техника, на мой взгляд, практически универсальна, и понимание основных принципов разработки интерпретаторов пригодится не только создателю очередного претендента на звание «Язык года» по версии TIOBE, но вообще любому программисту.
Словом, если вам интересно узнать, как складывают числа наши любимые языки программирования, о чём до сих пор спорят разработчики виртуальных машин и как безболезненно сопоставлять строки и регулярные выражения, прошу под кат.
Одна из самописных систем отдела Business Intelligence нашей компании имеет интерфейс в виде несложного языка запросов. В первой версии системы язык этот интерпретировался на лету, без компиляции, непосредственно из входной строки с запросом. Вторая версия парсера будет работать уже с промежуточным байт-кодом, что позволит отделить язык запросов от их выполнения и сильно упростит код.
В процессе работы над второй версией системы у меня случился отпуск, в течение которого я на часик-другой каждый день отвлекался от дел семейных на изучение материалов, посвящённых архитектуре и производительности интерпретаторов байт-кода. Полученными в результате заметками и примерами интерпретаторов я решил поделиться с читателями Хабра в виде серии статей.
В первой из них представлено пять небольших (до сотни строк простенького кода на C) виртуальных машин (ок), каждая из которых раскрывает определённый аспект разработки таких интерпретаторов.
Виртуальных машин, самых разнообразных виртуальных наборов инструкций за последние несколько десятков лет было придумано великое множество. Википедия утверждает, что первые языки программирования стали компилироваться в различные упрощённые промежуточные представления еще в 60-е годы прошлого века. Какие-то из этих первых байт-кодов преобразовывались в машинные коды и выполнялись реальными процессорами, другие — интерпретировались на лету процессорами виртуальными.
Популярность виртуальных наборов инструкций в качестве промежуточного представления кода объясняется тремя причинами:
- Программы в виде байт-кодов легко переносятся на новые платформы.
- Интерпретаторы байт-кодов работают быстрее интерпретаторов синтаксического дерева кода.
- Разработать простейшую виртуальную машину можно буквально за пару часов.
Давайте сделаем несколько простейших виртуальных машин на C и на этих примерах выделим основные технические аспекты реализации виртуальных машин.
Полные коды примеров выложены на GitHub. Примеры можно собрать любым относительно свежим GCC:
gcc interpreter-basic-switch.c -o interpreter
./interpreter
Все примеры имеют одинаковую структуру: сначала идёт код самой виртуальной машины, после — главная функция с assert-ами, проверяющими работу кода. Я старался внятно комментировать опкоды и ключевые места интерпретаторов. Надеюсь, статья будет понятна даже людям, ежедневно не пишущим на C.
Как я уже говорил, простейший интерпретатор сделать очень легко. Комментарии — сразу за листингом, а начнём непосредственно с кода:
struct {
uint8_t *ip;
uint64_t accumulator;
} vm;
typedef enum {
/* increment the register */
OP_INC,
/* decrement the register */
OP_DEC,
/* stop execution */
OP_DONE
} opcode;
typedef enum interpret_result {
SUCCESS,
ERROR_UNKNOWN_OPCODE,
} interpret_result;
void vm_reset(void)
{
puts("Reset vm state");
vm = (typeof(vm)) { NULL };
}
interpret_result vm_interpret(uint8_t *bytecode)
{
vm_reset();
puts("Start interpreting");
vm.ip = bytecode;
for (;;) {
uint8_t instruction = *vm.ip++;
switch (instruction) {
case OP_INC: {
vm.accumulator++;
break;
}
case OP_DEC: {
vm.accumulator--;
break;
}
case OP_DONE: {
return SUCCESS;
}
default:
return ERROR_UNKNOWN_OPCODE;
}
}
return SUCCESS;
}
Здесь меньше ста строк, но все характерные атрибуты виртуальной машины представлены. У машины единственный регистр (vm.accumulator), три операции (инкремент регистра, декремент регистра и завершение исполнения программы) и указатель на текущую инструкцию (vm.ip).
Каждая операция (англ. operation code, или opcode) кодируется одним байтом, а диспетчеризация осуществляется при помощи обычного switch в функции vm_interpret. Ветки в switch содержат логику операций, то есть меняют состояние регистра либо завершают исполнение программы.
Операции передаются в функцию vm_interpret в виде массива байтов — байт-кода (англ. bytecode) — и последовательно выполняются до тех пор, пока в байт-коде не встретится операция завершения работы виртуальной машины (OP_DONE).
Ключевой аспект виртуальной машины — семантика, то есть набор операций, которые над ней возможны. В данном случае операций только две, и они меняют значение единственного регистра.
Некоторые исследователи (Virtual-machine Abstraction and Optimization Techniques, 2009) предлагают разделять виртуальные машины на высокоуровневые и низкоуровневые по близости семантики виртуальной машины к семантике физической машины, на которой будет выполняться байт-код.
В предельном случае байт-код низкоуровневых виртуальных машин может полностью повторять машинный код физической машины с имитацией оперативной памяти, полным набором регистров, инструкциями работы со стеком и так далее. Виртуальная машина Bochs, например, повторяет набор инструкций архитектуры x86.
И наоборот: операции высокоуровневых виртуальных машин близко отражают семантику компилируемого в байт-код специализированного языка программирования. Так работают, например, SQLite, Gawk и многочисленные версии Prolog.
Промежуточное положение занимают интерпретаторы языков программирования общего назначения, имеющие элементы как высокого, так и низкого уровней. В популярнейшей Java Virtual Machine есть как низкоуровневые инструкции для работы со стеком, так и встроенная поддержка объектно-ориентированного программирования с автоматическим выделением памяти.
Приведённый же код относится скорее к самым примитивным из низкоуровневых виртуальных машин: каждая виртуальная инструкция — обёртка над одной-двумя физическими инструкциями, виртуальный регистр же полностью соответствует одному регистру «железного» процессора.
Можно сказать, что единственный регистр в нашем примере виртуальной машины — одновременно и аргумент, и возвращаемое значение всех выполняемых инструкций. Однако нам может пригодиться возможность передавать аргументы в инструкции. Один из способов — прямо помещать их в байт-код.
Расширим пример, внеся инструкции (OP_ADDI, OP_SUBI), принимающие аргумент в виде байта, следующего непосредственно за опкодом:
struct {
uint8_t *ip;
uint64_t accumulator;
} vm;
typedef enum {
/* increment the register */
OP_INC,
/* decrement the register */
OP_DEC,
/* add the immediate argument to the register */
OP_ADDI,
/* subtract the immediate argument from the register */
OP_SUBI,
/* stop execution */
OP_DONE
} opcode;
typedef enum interpret_result {
SUCCESS,
ERROR_UNKNOWN_OPCODE,
} interpret_result;
void vm_reset(void)
{
puts("Reset vm state");
vm = (typeof(vm)) { NULL };
}
interpret_result vm_interpret(uint8_t *bytecode)
{
vm_reset();
puts("Start interpreting");
vm.ip = bytecode;
for (;;) {
uint8_t instruction = *vm.ip++;
switch (instruction) {
case OP_INC: {
vm.accumulator++;
break;
}
case OP_DEC: {
vm.accumulator--;
break;
}
case OP_ADDI: {
/* get the argument */
uint8_t arg = *vm.ip++;
vm.accumulator += arg;
break;
}
case OP_SUBI: {
/* get the argument */
uint8_t arg = *vm.ip++;
vm.accumulator -= arg;
break;
}
case OP_DONE: {
return SUCCESS;
}
default:
return ERROR_UNKNOWN_OPCODE;
}
}
return SUCCESS;
}
Новые инструкции (см. функцию vm_interpret) читают из байт-кода свой аргумент и прибавляют его к регистру / вычитают его из регистра.
Такой аргумент называется непосредственным аргументом (англ. immediate argument), поскольку он располагается прямо в массиве опкодов. Главное ограничение в нашей реализации заключается в том, что аргумент представляет собой один-единственный байт и может принимать только 256 значений.
В нашей виртуальной машине диапазон возможных значений аргументов инструкций не играет большой роли. Но если виртуальная машина будет использоваться в качестве интерпретатора настоящего языка, то имеет смысл усложнить байт-код, добавив в него отдельную от массива опкодов таблицу констант и инструкции с непосредственным аргументом, соответствующим адресу настоящего аргумента в таблице констант.
Инструкции в нашей несложной виртуальной машине всегда работают с одним регистром и никак не могут передавать друг другу данные. Кроме того, аргумент у инструкции может быть только непосредственный, а, скажем, операции сложения или умножения принимают два аргумента.
Проще говоря, у нас нет никакой возможности вычислять сложные выражения. Для решения этой задачи необходима стековая машина, то есть виртуальная машина со встроенным стеком:
#define STACK_MAX 256
struct {
uint8_t *ip;
/* Fixed-size stack */
uint64_t stack[STACK_MAX];
uint64_t *stack_top;
/* A single register containing the result */
uint64_t result;
} vm;
typedef enum {
/* push the immediate argument onto the stack */
OP_PUSHI,
/* pop 2 values from the stack, add and push the result onto the stack */
OP_ADD,
/* pop 2 values from the stack, subtract and push the result onto the stack */
OP_SUB,
/* pop 2 values from the stack, divide and push the result onto the stack */
OP_DIV,
/* pop 2 values from the stack, multiply and push the result onto the stack */
OP_MUL,
/* pop the top of the stack and set it as execution result */
OP_POP_RES,
/* stop execution */
OP_DONE,
} opcode;
typedef enum interpret_result {
SUCCESS,
ERROR_DIVISION_BY_ZERO,
ERROR_UNKNOWN_OPCODE,
} interpret_result;
void vm_reset(void)
{
puts("Reset vm state");
vm = (typeof(vm)) { NULL };
vm.stack_top = vm.stack;
}
void vm_stack_push(uint64_t value)
{
*vm.stack_top = value;
vm.stack_top++;
}
uint64_t vm_stack_pop(void)
{
vm.stack_top--;
return *vm.stack_top;
}
interpret_result vm_interpret(uint8_t *bytecode)
{
vm_reset();
puts("Start interpreting");
vm.ip = bytecode;
for (;;) {
uint8_t instruction = *vm.ip++;
switch (instruction) {
case OP_PUSHI: {
/* get the argument, push it onto stack */
uint8_t arg = *vm.ip++;
vm_stack_push(arg);
break;
}
case OP_ADD: {
/* Pop 2 values, add 'em, push the result back to the stack */
uint64_t arg_right = vm_stack_pop();
uint64_t arg_left = vm_stack_pop();
uint64_t res = arg_left + arg_right;
vm_stack_push(res);
break;
}
case OP_SUB: {
/* Pop 2 values, subtract 'em, push the result back to the stack */
uint64_t arg_right = vm_stack_pop();
uint64_t arg_left = vm_stack_pop();
uint64_t res = arg_left - arg_right;
vm_stack_push(res);
break;
}
case OP_DIV: {
/* Pop 2 values, divide 'em, push the result back to the stack */
uint64_t arg_right = vm_stack_pop();
/* Don't forget to handle the div by zero error */
if (arg_right == 0)
return ERROR_DIVISION_BY_ZERO;
uint64_t arg_left = vm_stack_pop();
uint64_t res = arg_left / arg_right;
vm_stack_push(res);
break;
}
case OP_MUL: {
/* Pop 2 values, multiply 'em, push the result back to the stack */
uint64_t arg_right = vm_stack_pop();
uint64_t arg_left = vm_stack_pop();
uint64_t res = arg_left * arg_right;
vm_stack_push(res);
break;
}
case OP_POP_RES: {
/* Pop the top of the stack, set it as a result value */
uint64_t res = vm_stack_pop();
vm.result = res;
break;
}
case OP_DONE: {
return SUCCESS;
}
default:
return ERROR_UNKNOWN_OPCODE;
}
}
return SUCCESS;
}
В этом примере операций уже больше, и почти все они работают только со стеком. OP_PUSHI помещает на стек свой непосредственный аргумент. Инструкции OP_ADD, OP_SUB, OP_DIV, OP_MUL извлекают по паре значений из стека, вычисляют результат и помещают его обратно на стек. OP_POP_RES снимает значение со стека и помещает его в регистр result, предназначенный для результатов работы виртуальной машины.
Для операции деления (OP_DIV) отлавливается ошибка деления на ноль, что останавливает работу виртуальной машины.
Возможности такой машины намного шире предыдущей с единственным регистром и позволяют, например, вычислять сложные арифметические выражения. Другим (и немаловажным!) преимуществом является простота компиляции языков программирования в байт-код стековой машины.
Благодаря своей простоте стековые виртуальные машины получили самое широкое распространение среди разработчиков языков программирования; те же JVM и Python VM используют именно их.
Однако у таких машин есть и недостатки: в них приходится добавлять специальные инструкции для работы со стеком, при вычислении выражений все аргументы многократно проходят через единственную структуру данных, в стековом коде неизбежно появляется множество лишних инструкций.
Между тем выполнение каждой лишней инструкции влечёт за собой затраты на диспетчеризацию, то есть декодирование опкода и переход к телу инструкций.
Альтернатива стековым машинам — регистровые виртуальные машины. У них более сложный байт-код: в каждой инструкции явно закодированы номер регистров-аргументов и номер регистра-результата. Соответственно, вместо стека в качестве хранилища промежуточных значений используется расширенный набор регистров.
#define REGISTER_NUM 16
struct {
uint16_t *ip;
/* Register array */
uint64_t reg[REGISTER_NUM];
/* A single register containing the result */
uint64_t result;
} vm;
typedef enum {
/* Load an immediate value into r0 */
OP_LOADI,
/* Add values in r0,r1 registers and put them into r2 */
OP_ADD,
/* Subtract values in r0,r1 registers and put them into r2 */
OP_SUB,
/* Divide values in r0,r1 registers and put them into r2 */
OP_DIV,
/* Multiply values in r0,r1 registers and put them into r2 */
OP_MUL,
/* Move a value from r0 register into the result register */
OP_MOV_RES,
/* stop execution */
OP_DONE,
} opcode;
typedef enum interpret_result {
SUCCESS,
ERROR_DIVISION_BY_ZERO,
ERROR_UNKNOWN_OPCODE,
} interpret_result;
void vm_reset(void)
{
puts("Reset vm state");
vm = (typeof(vm)) { NULL };
}
void decode(uint16_t instruction,
uint8_t *op,
uint8_t *reg0, uint8_t *reg1, uint8_t *reg2,
uint8_t *imm)
{
*op = (instruction & 0xF000) >> 12;
*reg0 = (instruction & 0x0F00) >> 8;
*reg1 = (instruction & 0x00F0) >> 4;
*reg2 = (instruction & 0x000F);
*imm = (instruction & 0x00FF);
}
interpret_result vm_interpret(uint16_t *bytecode)
{
vm_reset();
puts("Start interpreting");
vm.ip = bytecode;
uint8_t op, r0, r1, r2, immediate;
for (;;) {
/* fetch the instruction */
uint16_t instruction = *vm.ip++;
/* decode it */
decode(instruction, &op, &r0, &r1, &r2, &immediate);
/* dispatch */
switch (op) {
case OP_LOADI: {
vm.reg[r0] = immediate;
break;
}
case OP_ADD: {
vm.reg[r2] = vm.reg[r0] + vm.reg[r1];
break;
}
case OP_SUB: {
vm.reg[r2] = vm.reg[r0] - vm.reg[r1];
break;
}
case OP_DIV: {
/* Don't forget to handle the div by zero error */
if (vm.reg[r1] == 0)
return ERROR_DIVISION_BY_ZERO;
vm.reg[r2] = vm.reg[r0] / vm.reg[r1];
break;
}
case OP_MUL: {
vm.reg[r2] = vm.reg[r0] * vm.reg[r1];
break;
}
case OP_MOV_RES: {
vm.result = vm.reg[r0];
break;
}
case OP_DONE: {
return SUCCESS;
}
default:
return ERROR_UNKNOWN_OPCODE;
}
}
return SUCCESS;
}
В примере показана регистровая машина на 16 регистров. Инструкции занимают по 16 бит каждая и кодируются тремя способами:
- 4 бита на код операции + 4 бита на имя регистра + 8 бит на аргумент.
- 4 бита на код операции + трижды по 4 бита на имена регистров.
- 4 бита на код операции + 4 бита на единственное имя регистра + 8 неиспользованных бит.
У нашей небольшой виртуальной машины совсем мало операций, поэтому четырёх бит (или 16 возможных операций) на опкод вполне достаточно. Операция определяет, что именно представляют оставшиеся биты инструкции.
Первый вид кодирования (4 + 4 + 8) нужен для загрузки данных в регистры операцией OP_LOADI. Второй вид (4 + 4 + 4 + 4) используется для арифметических операций, которые должны знать, где брать пару аргументов и куда складывать результат вычисления. И, наконец, последний вид (4 + 4 + 8 ненужных бит) используется для инструкций с единственным регистром в качестве аргумента, в нашем случае это OP_MOV_RES.
Для кодирования и декодирования инструкций теперь нужна специальная логика (функция decode). С другой стороны, логика инструкций благодаря явному указанию на расположение аргументов становится проще — исчезают операции со стеком.
Ключевые особенности: в байт-коде регистровых машин меньше инструкций, отдельные инструкции шире, компиляция в такой байт-код сложнее — компилятору приходится решать, как использовать доступные регистры.
Надо заметить, что на практике в регистровых виртуальных машинах обычно есть и стек, куда помещаются, например, аргументы функций; регистры же используются для вычисления отдельных выражений. Даже если явного стека нет, то для построения стека используется массив, играющий ту же роль, что оперативная память в физических машинах.
Есть интересное исследование (Virtual machine showdown: Stack versus registers, 2008), оказавшее большое влияние на все последующие разработки в области виртуальных машин для языков программирования. Его авторы предложили способ прямой трансляции из стекового кода стандартной JVM в регистровый код и сравнили производительность.
Способ нетривиальный: код сначала транслируется, а потом достаточно сложным образом оптимизируется. Но последующее сравнение производительности одной и той же программы показало, что дополнительные циклы процессора, затраченные на декодирование инструкций, полностью компенсируются уменьшением общего числа инструкций. В общем, если коротко, регистровая машина оказалась эффективнее стековой.
Как уже упоминалось выше, у этой эффективности есть вполне осязаемая цена: компилятор должен сам аллоцировать регистры и дополнительно желательно наличие развитого оптимизатора.
Спор о том, какая же архитектура лучше, всё ещё не закончен. Если говорить о компиляторах Java, то байт-код Dalvik VM, до недавних пор работавший в каждом Android-устройстве, был регистровым;, но титульная JVM сохранила стековый набор инструкций. Виртуальная машина Lua использует регистровую машину, но Python VM — по-прежнему стековая. И так далее.
Наконец, чтобы отвлечься от низкоуровневых виртуальных машин, давайте рассмотрим специализированный интерпретатор, проверяющий строки на соответствие регулярному выражению:
typedef enum {
/* match a single char to an immediate argument from the string and advance ip and cp, or
* abort*/
OP_CHAR,
/* jump to and match either left expression or the right one, abort if nothing matches*/
OP_OR,
/* do an absolute jump to an offset in the immediate argument */
OP_JUMP,
/* stop execution and report a successful match */
OP_MATCH,
} opcode;
typedef enum match_result {
MATCH_OK,
MATCH_FAIL,
MATCH_ERROR,
} match_result;
match_result vm_match_recur(uint8_t *bytecode, uint8_t *ip, char *sp)
{
for (;;) {
uint8_t instruction = *ip++;
switch (instruction) {
case OP_CHAR:{
char cur_c = *sp;
char arg_c = (char)*ip ;
/* no match? FAILed to match */
if (arg_c != cur_c)
return MATCH_FAIL;
/* advance both current instruction and character pointers */
ip++;
sp++;
continue;
}
case OP_JUMP:{
/* read the offset and jump to the instruction */
uint8_t offset = *ip;
ip = bytecode + offset;
continue;
}
case OP_OR:{
/* get both branch offsets */
uint8_t left_offset = *ip++;
uint8_t right_offset = *ip;
/* check if following the first offset get a match */
uint8_t *left_ip = bytecode + left_offset;
if (vm_match_recur(bytecode, left_ip, sp) == MATCH_OK)
return MATCH_OK;
/* no match? Check the second branch */
ip = bytecode + right_offset;
continue;
}
case OP_MATCH:{
/* success */
return MATCH_OK;
}
}
return MATCH_ERROR;
}
}
match_result vm_match(uint8_t *bytecode, char *str)
{
printf("Start matching a string: %s\n", str);
return vm_match_recur(bytecode, bytecode, str);
}
Главная инструкция — OP_CHAR. Она берёт свой непосредственный аргумент и сравнивает его с текущим символом в строке (char *sp). В случае совпадения ожидаемого и текущего символов в строке происходит переход к следующей инструкции и следующему символу.
Машина также понимает операцию перехода (OP_JUMP), принимающую единственный непосредственный аргумент. Аргумент означает абсолютное смещение в байт-коде, откуда следует продолжать вычисление.
Последняя важная операция — OP_OR. Она принимает два смещения, пробуя применить сначала код по первому из них, потом, в случае ошибки, второму. Делает она это при помощи рекурсивного вызова, то есть инструкция делает обход в глубину дерева всех возможных вариантов регулярного выражения.
Удивительно, но четырёх опкодов и семидесяти строк кода достаточно, чтобы выразить регулярные выражения вида «abc», «a? bc»,»(ab|bc)d», «a*bc». В этой виртуальной машине даже нет явного состояния, так как всё необходимое — указатели на начало потока инструкций, текущую инструкцию и текущий символ — передаётся аргументами рекурсивной функции.
Если вам интересны детали работы движков регулярных выражений, для начала можете ознакомиться с серией статей Расса Кокса (англ. Russ Cox), автора движка для работы с регулярными выражениями от Google RE2.
Давайте подведём итоги.
Для языков программирования общего назначения используются, как правило, две архитектуры: стековая и регистровая.
В стековой модели основной структурой данных и способом передачи аргументов между инструкциями является стек. В регистровой модели для вычисления выражений используется набор регистров, но для хранения аргументов функций всё равно используется явный или неявный стек.
Наличие явного стека и набора регистров приближает такие машины к низкоуровневым и даже физическим. Обилие низкоуровневых инструкций в таком байт-коде означает, что существенные затраты ресурсов физического процессора приходятся на декодирование и диспетчеризацию виртуальных инструкций.
С другой стороны, в популярных виртуальных машинах большую роль играют и высокоуровневые инструкции. В Java, например, это инструкции полиморфных вызовов функций, аллокация объектов и сборка мусора.
Чисто высокоуровневые виртуальные машины — к примеру, интерпретаторы байт-кодов языков с развитой и далёкой от железа семантикой — большую часть времени проводят не в диспетчере или декодере, а в телах инструкций и, соответственно, относительно эффективны.
Практические рекомендации:
- Если вам понадобилось исполнить какой-либо байт-код и сделать это в разумные сроки, то постарайтесь оперировать инструкциями, наиболее близкими к вашей задаче; чем выше семантический уровень, тем лучше. Это снизит затраты на диспетчеризацию и упростит генерацию кода.
- Если потребовались большая гибкость и разнородная семантика, то следует хотя бы попробовать выделить общий знаменатель в байт-коде так, чтобы результирующие инструкции были на условно среднем уровне.
- Если в перспективе может понадобиться вычислять какие-либо выражения, делайте стековую машину, это уменьшит головную боль при компиляции байт-кода.
- Если выражений не предвидится, то делайте тривиальную регистровую машину, что позволит избежать затрат на стек и упростит сами инструкции.
В следующих статьях я разберу практические реализации виртуальных машин в популярных языках программирования и расскажу, зачем отделу Business Intelligence Badoo понадобился байт-код.
