В некоторых внутренних системах для быстрого поиска по большому битовому массиву мы в Badoo используем JIT. Это очень интересная и не самая известная тема. И, чтобы исправить такую досадную ситуацию, я перевел полезную статью Элая Бендерски о том, что такое JIT и как его использовать.

Раньше я уже публиковал вводную статью по libjit для программистов, которые уже знакомы с JIT. Хотя бы немного. В том посте я совсем коротко описал JIT, а в этом сделаю полный обзор JIT и дополню его примерами, код в которых не требует никаких дополнительных библиотек.

Определение JIT

JIT – это акроним от “Just In Time” или, если переводить на русский, “на лету”. Это нам ни о чем не говорит и звучит так, будто к программированию не имеет никакого отношения. Мне кажется, это описание JIT больше всего похоже на правду:

Если какая-то программа во время своего исполнения создает и выполняет какой-нибудь новый исполняемый код, который не был частью изначальной программы на диске, – это JIT.

Но откуда произошло это название? К счастью, Джон Айкок из университета Калгари написал очень интересную статью под названием “Краткая история JIT”, в которой рассматривает JIT-техники с исторической точки зрения. Судя по статье, первое упоминание кодогенерации и исполнения кода во время работы программы появилось в 1960 году в статье про LISP, написанной McCarthy. В более поздних работах (например, статья Томсона от 1968 года про регулярные выражения) этот подход совсем очевиден (регулярные выражения компилируются в машинный код и исполняются на лету).

Сам же термин JIT впервые появился в книгах по Java Джеймса Гослинга. Айкок говорит, что Гослинг перенял этот термин из области промышленного производства и начал его использовать в ранних 90-х. Если вам интересны подробности, то прочитайте статью Айкока. А теперь давайте посмотрим, как все описанное выше работает на практике.

JIT: сгенерируйте машинный код и запустите его

Мне кажется, что JIT проще понять, если сразу разделить его на две фазы:

• Фаза 1: генерация машинного кода во время работы программы
• Фаза 2: выполнение машинного кода во время работы программы

Первая фаза – это 99% всей сложности JIT. Но в то же время это самая банальная часть процесса: это именно то, что делает обычный компилятор. Широко известные компиляторы, такие как gcc и clang/llvm, транслируют исходники из C/C++ в машинный код. Дальше машинный код обычно сохраняется в файл, но нет смысла не оставлять его в памяти (на самом деле и в gcc, и в clang/llvm есть готовые возможности для сохранения кода в памяти для использования его в JIT). Но в этой статье я хотел бы сфокусироваться на второй фазе.

Выполнение сгенерированного кода

Современные операционные системы очень избирательны в том, что программе разрешено делать во время ее работы. Времена дикого запада закончились с появлением защищенного режима, который позволяет операционной системе выставлять различные права на различные куски памяти процесса. То есть в “обычном” режиме вы можете выделить память на куче, но вы не можете просто выполнить код, который выделен на куче, предварительно явно не попросив об этом ОС.

Я надеюсь, всем понятно, что машинный код – это просто данные, набор байтов. Как вот это, например:

unsigned char[] code = {0x48, 0x89, 0xf8};

Для кого-то эти три байта – просто три байта, а для кого-то – бинарное представление валидного x86-64 кода:

mov %rdi, %rax

Поместить этот машинный код в память очень легко. Но как сделать его исполняемым и, собственно, исполнить?

Посмотрим на код

Дальше в этой статье будут примеры кода для POSIX-совместимой UNIX операционной системы (а именно Linux). На других ОС (таких как Windows) код будет отличаться в деталях, но не в подходе. У всех современных ОС есть удобные API для того, чтобы сделать то же самое.

Без лишних предисловий посмотрим, как динамически создать функцию в памяти и выполнить ее. Эта функция специально сделана очень простой. В C она выглядит так:

long add4(long num) {
  return num + 4;
}

Вот первая попытка (полный исходник вместе с Makefile доступен в репозитории):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>

// Выделяет RWX память заданного размера и возвращает указатель на нее. В случае ошибки
// печатает ошибку и возвращает NULL.
void* alloc_executable_memory(size_t size) {
  void* ptr = mmap(0, size,
                   PROT_READ | PROT_WRITE | PROT_EXEC,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (ptr == (void*)-1) {
    perror("mmap");
    return NULL;
  }
  return ptr;
}

void emit_code_into_memory(unsigned char* m) {
  unsigned char code[] = {
    0x48, 0x89, 0xf8,                   // mov %rdi, %rax
    0x48, 0x83, 0xc0, 0x04,             // add $4, %rax
    0xc3                                // ret
  };
  memcpy(m, code, sizeof(code));
}

const size_t SIZE = 1024;
typedef long (*JittedFunc)(long);

// Выделяет RWX память напрямую.
void run_from_rwx() {
  void* m = alloc_executable_memory(SIZE);
  emit_code_into_memory(m);

  JittedFunc func = m;
  int result = func(2);
  printf("result = %d\n", result);
}

Три основных этапа, которые выполняет этот код:

1. Использование mmap для выделения куска памяти на куче, в которую можно писать, из которой можно читать и которую можно исполнять.
2. Копирование машинного кода, реализующего add4 в эту память.
3. Выполнение кода из этой памяти путем преобразования указателя в указатель на функцию и вызова ее через этот указатель.

Прошу заметить, что третий этап возможен только тогда, когда кусок памяти с машинным кодом имеет права на исполнение. Без нужных прав вызов функции привел бы к ошибке ОС (скорее всего, ошибке сегментирования). Это произойдет, если, например, мы выделим m обычным вызовом malloc, который выделяет RW память, но не X.

Отвлечемся на минутку: heap, malloc и mmap

Внимательные читатели могли заметить, что я сказал о памяти, выделяемой mmap, как о “памяти из кучи”. Строго говоря, “куча” — название для источника памяти, который используют функции malloc, free и другие. В отличие от стека, которым управляет компилятор напрямую.

Но не все так просто. :-) Если традиционно (то есть очень давно) malloc использовал только один источник для выделяемой памяти (системный вызов sbrk), то сейчас большинство реализаций malloc во многих случаях используют mmap. Детали отличаются от операционки к операционке и в разных реализациях, но обычно mmap используется для больших кусков памяти, а sbrk – для маленьких. Различие в эффективности во время использования одного или другого способа получения памяти от операционной системы.

Так что называть память, полученную от mmap “памятью из кучи”, не ошибка, по моему мнению, и я собираюсь и дальше использовать это название.

Заботимся о безопасности

У кода выше есть серьезная уязвимость. Причина в блоке RWX-памяти, который он выделяет – рай для эксплоитов. Давайте будем чуть более ответственными. Вот немного измененный код:

// Выделяет RW память заданного размера и возвращает указатель на нее. В случае ошибки
// печатает ошибку и возвращает NULL. В отличие от malloc, память выделяется
// на границе страниц памяти, так что ее можно использовать при вызове mprotect.
void* alloc_writable_memory(size_t size) {
  void* ptr = mmap(0, size,
                   PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
  if (ptr == (void*)-1) {
    perror("mmap");
    return NULL;
  }
  return ptr;
}

// Ставит RX права на этот кусок выровненной памяти. Возвращает
// 0 при успехе. При ошибке печатает ошибку и возвращает -1.
int make_memory_executable(void* m, size_t size) {
  if (mprotect(m, size, PROT_READ | PROT_EXEC) == -1) {
    perror("mprotect");
    return -1;
  }
  return 0;
}

// Выделяет RW память, сохраняет код в нее и меняет права на RX перед
// исполнением.
void emit_to_rw_run_from_rx() {
  void* m = alloc_writable_memory(SIZE);
  emit_code_into_memory(m);
  make_memory_executable(m, SIZE);

  JittedFunc func = m;
  int result = func(2);
  printf("result = %d\n", result);
}

Этот пример эквивалентен предыдущему примеру во всех отношениях, кроме одного: память сначала выделяется с RW-правами (как и с обычным malloc). Это достаточные права для того, чтобы мы могли записать туда наш кусок кода. После того, как код уже находится в памяти, мы используем mprotect, чтобы поменять права с RW на RX, запрещая запись. В итоге эффект такой же, но ни на каком из этапов наша память не является одновременно и перезаписываемой, и исполняемой. Это хорошо и правильно с точки зрения безопасности.

Что насчет malloc?

Могли ли мы использовать malloc вместо mmap для выделения памяти в предыдущем коде? Ведь RW-память – это именно то, что нам дает malloc. Да, мы могли. Но тут больше проблем, чем удобств. Дело в том, что права можно выставить только на целые страницы. И, выделяя память с помощью malloc, нам нужно было бы вручную удостовериться, что память выровнена по границе страницы. Mmap решает эту проблему таким образом, что выделяет всегда выровненную память (потому что mmap по определению работает только с целыми страницами).

Подводя итоги

Эта статья начиналась с общего обзора JIT, того, что мы вообще подразумеваем, когда говорим “JIT”, и закончилась примерами кода, который демонстрирует, как динамически выполнять кусок машинного кода из памяти. Техники, представленные в статье – это примерно то, как делается JIT в настоящих JIT-системах (LLVM или libjit). Остается всего лишь “простая” часть генерации машинного кода из какого-либо другого представления.

LLVM содержит в себе полноценный компилятор, так что он может транслировать C и C++-код (через LLVM IR) в машинный код на лету и исполнять его. Libjit работает на гораздо более низком уровне: он может служить бэкендом для компилятора. Моя вводная статья по libjit демонстрирует, как генерировать и выполнять нетривиальный код с помощью этой библиотеки. Но JIT – это гораздо более общий концепт. Создавать код на лету можно для структур данных, регулярных выражений и даже для доступа к C из виртуальных машин различных языков. Я покопался в архивах своего блога и нашел упоминание о JIT в статье восьмилетней давности. Она о Perl-коде, который генерирует другой Perl-код на лету (из XML-файла с описанием), но идея та же самая.

Вот почему я считаю, что описывать JIT важно, разделяя две фазы. Для второй фазы (которую я описал в этой статье) реализация довольно банальна и использует стандартные API операционной системы. Для первой фазы возможностей бесконечное количество. И что именно будет в ней в конечном счете, зависит от конкретного приложения, которое вы разрабатываете.