Как разработчик TeaVM, компилятора байт-кода JVM в JavaScript и WebAssembly, я часто рекомендую пользователям, почему-то жаждущим сгенерировать WebAssembly, начать с JavaScript. Если честно, бэкэнд WebAssembly я очень давно не развиваю, не реализую в нём недостающих фич и не фикшу баги. Меня спрашивают: а почему так? Обычно, я просто игнорирую подобные вопросы, потому что в двух предложениях ответить на них невозможно, а для того, чтобы писать больше предложений, у меня нет времени. Обычно если я встречаю чьи-то попытки объяснить, чем WebAssembly плох для реализации JVM (а так же, CLR, JavaScript и прочих динамических сред), то они сводятся к следующему: "Java (.NET, JavaScript, ваш вариант) — это управляемый язык со сборкой мусора и исключениями, так что приходится тащить с собой гигантский рантайм". Что же, на самом деле, ситуация несколько сложнее, а размер рантайма вовсе не такой страшный и не является основным источником бед.
Хочу так же оговориться, что изложенное является моим мнением, я не самый умелый разработчик компиляторов в мире, над разработкой сколь угодно известных управляемых сред не трудился, а весь мой компиляторный опыт — это упомянутый выше PET-проект (который, однако, используется в продакшене некоторыми компаниями) и около 2 лет работы над Kotlin/JS.
Прошло много времени, мой proof-of-concept становился всё более и более пригодным для реальных проектов, кто-то даже стал осторожно использовать его. И тут появляется WebAssembly. Поскольку TeaVM явно не хватало популярности, я попытался выехать на хайпе, может быть, прыгнуть в вагон поезда раньше других, и приступил к написанию WebAssembly бэкэнда (в компиляторном смысле). Однако, через какое-то время я разочаровался в этой технологии: wasm-файлы получались огромными, а производительность не была намного лучше JavaScript. При этом сгенерированный код WebAssembly было очень тяжело отлаживать и очень тяжело взаимодействовать с JavaScript. Ну и темп развития спецификации мне показался очень уж черепашьим, а докричаться до комитета и попытаться "протолкнуть" необходимые для рантайма фичи представлялось маловероятным.
Итак, для CPU нет понятия "стек". У CPU есть линейная непрерывная память, откуда можно читать и куда можно писать значения. Стек реализуется с помощью специального регистра (esp или rsp на x86), который хранит адрес в памяти вершины стека. Запись в стек (операция push) — это уменьшение esp и запись значения по адресу, хранящемуся в esp. Чтение из стека — это чтение значения по адресу, хранящемуся в esp и увеличение esp. Есть ещё операции вызова процедуры (call) и возврата из процедуры (ret). call %target% кладёт на стек адрес следующей команды (программный счётчик) и записывает %taget% в eip. ret читает значение со стека в регистр eip (адрес текущей инструкции).
При этом никто не мешает брать и читать/писать в стек минуя esp и описанные операции. Вот, например, как начинается функция, сгенерированная типичным компилятором для 32-битного x86:
push ebp
mov ebp, esp
sub esp, N
Последняя операция резервирует на стеке N байт, где N — это суммарное количество байт во всех локальных переменных функции. Дальше, если функция что-то делает с локальными переменными, то она обращается по адресу относительно ebp. Например, строчка
local1 = local2 + local3;
может превратиться во что-то вроде
mov eax, [ebp - 8]
add eax, [ebp - 12]
mov [ebp - 4], eax
и тут надо обратить внимание вот на что: у функции нет "своего" стекового кадра. Точнее, он есть только если автор функции хочет, чтобы программа не разламывалась. Но на уровне железа никаких гарантий нет. Можно брать и читать содержимое стека, можно писать в него — это вполне допустимо с точки зрения CPU. И авторы рантаймов этот факт активно используют.
void mark() {
for (var root : staticFields) {
if (root.deref() != null) {
queue.add(root.deref());
}
}
for (var frame : stack) {
for (var localVar : frame.type.localVars) {
if (frame.data.read(localVar) != null) {
queue.add(frame.data[localVar]);
}
}
}
while (queue.notEmpty()) {
o = queue.remove();
if (o.marked) continue;
o.marked = true;
for (field in o.type.fields) {
next = o.data[field];
if (next != null && !next.marked) {
queue.add(next);
}
}
}
}
В случае с x86 второй цикл — это итерация, начиная с текущего значения esp. При входе в mark на вершине стека будет лежать адрес возврата. Зная адрес возврата, можно вычислить функцию, вызвавшую mark, а для неё известен размер стекового кадра. Добавив в esp этот размер, получим адрес следующей по стеку функции и т.д. Так можно пройтись по всем кадрам. Опять же, зная адреса возврата, можно воспользоваться табличкой, которая сопоставляет эти адреса смещениям, по которым располагаются ссылочные локальные переменные. Пройдясь по этим смещениям относительно начала стекового кадра, можно пройтись по переменным этого кадра (цикл по frame.type.localVars).
И вот тут нас ожидает первая проблема: никак нельзя получить доступ к стеку WebAssembly. Выход тут один — необходимо программно эмулировать стек и значения локальных переменных, указывающих на объекты, дублировать в этом стеке перед КАЖДЫМ вызовом какого-нибудь метода. Такая структура называется shadow stack. Примерно это будет выглядеть так:
// начало метода
localRoots = shadowStack.alloc(FRAME_SIZE);
// ...
localRoots[0] = localVar1;
localRoots[1] = localVar2;
// и т.д.
foo();
// ...
shadowStack.release(FRAME_SIZE);
// конец метода
Или пример из реально сгенерированного wasm:
;; начало метода
(set_local 12 ;; выделяем в shadow stack место под хранение
;; одной 4-байтовой переменной
(call $meth_otbw_WasmRuntime_allocStack
(i32.const 1)))
;; ...
;; вызов (call site)
(i32.store offset=4 align=4 ;; помещаем значение local7 в shadow stack
(get_local 12)
(get_local 7))
(set_local 1 ;; вызываем метод (полезная работа)
(call $meth_jl_Character_forDigit
(get_local 1)
(get_local 3)))
;; ...
;; конец метода
(i32.store align=4 ;; возвращаем занятые 4 байта в shadow stack
(i32.const 728) ;; 728 - это адрес в памяти, по которому находится
;; текущее значение вершины стека
(i32.sub
(get_local 12)
(i32.const 4)))
Понятно, что это, во-первых, медленно, а, во-вторых, лишние траты памяти. Есть ухищрения, которые позволяют минимизировать записи в shadow stack, однако в любом случае, получается дорого.
Полагаю, мотивацией для разработчиков спецификации являлась безопасность. Действительно, возможность просто так взять и поменять содержимое стека или стекового регистра — это один из главных источников дыр в ПО. С другой стороны, для реализации GC вовсе не нужно менять стековый регистр или писать в стек в произвольное место. Достаточно просто прочитать оттуда данные. Ведь данные из памяти WebAssembly может читать — и ничего. То же самое с оптимизациями: при грамотно написанной спецификации оверхед можно свести к минимуму, и этот оверхед в любом случае значительно меньше того, что даёт shadow stack.
Почему в JavaScript такой проблемы нет? Потому что в JavaScript уже есть сборщик мусора. Достаточно просто превращать Java объекты в JavaScript объекты.
exceptionType = exception.getClass();
for (var frame : stack) {
callSite = callSites.lookup(frame.returnAddress)
for (var handler : callSite.exceptionHandlers) {
if (handler.exceptionType.isAssignableFrom(exceptionType)) {
stack.top = frame;
goto handler.address; // межпроцедурный goto, которого нет в Java
}
}
}
Т.е. catch, который не ловит исключение, не имеет накладных расходов, всей работой занимается только throw.
Однако, WebAssembly не даёт ходить по стеку, делать goto или узнавать адрес инструкции. Поэтому всё, что остаётся делать — это на выходе из каждого метода проверять некоторый код возврата. Кроме того, перед вызовом метода необходимо записать в shadow stack его идентификатор. На самом деле, TeaVM хранит "код возврата" в shadow stack — он пишет его поверх идентификатора call site. Вот псевдокод метода с учётом try/catch:
localRoots[0] = localVar1;
localRoots[1] = localVar2;
// и т.д.
localRoots.callSiteId = 1;
foo()
// и т.д.
switch (localRoots.callSiteId) {
case 1: goto nextInstruction;
case 2: releaseStack(); return;
case 3: goto firstExceptionHandler;
case 4: goto secondExceptionHandler;
// и т.д.
}
nextInstruction:
// continue after call
Вот пример из реального wasm-файла:
(block $block_4
(i32.store offset=4 align=4 ;; сохраняем локальную переменную в shadow stack
(get_local 13)
(get_local 2))
(i32.store align=4 ;; сохраняем в него же call site id (47)
(get_local 13)
(i32.const 47))
(set_local 3 ;; вызываем метод (полезная работа)
(call $meth_jl_Integer_parseInt_0
(get_local 2)))
(block $block_5
(block $block_3
(block $block_2
(block $block_1
(br_table $block_1 $block_2 $block_3
;; читаем код возврата
(i32.sub
(i32.load align=4
(get_local 13))
(i32.const 47))))
(br $block_4))
(br $block_5))
(br $block_0)) ;; если код 48, то выходим из метода
;; если код возврата 49, попадаем сюда, т.е. в обработчик NumberFormatException
;; тут обрабатываем исключение
(br $block_6) ;; выходим из метода
)
;; если код возврата 47, попадаем сюда, т.е. продолжаем выполнение после catch
Почему это не проблема в JavaScript? Потому что в JavaScript из коробки поддерживается try/catch, и достаточно просто превращать try/catch в Java в try/catch в JavaScript.
doSomethingWith(o.someField);
doSomethingWith(o.someMethod());
Конечно, ставить явную проверку на null — это дорого. Поэтому любая уважающая себя реализация JVM при инициализации вызывает какой-нибудь mprotect на нулевой странице (в Windows это делается похожей по смыслу функцией VirtualAlloc). Что это за mprotect? В современных CPU можно назначать разным участкам памяти (обычно, разбитым на страницы фиксированного размера) права доступа: чтение, запись, выполнение. Если программа нарушает эти права, то процессор сгенерирует исключение, которое можно попытаться обработать — этим занимается ядро операционной системы. Код программы может попросить ядро повесить обработчик на исключения процессора с помощью функции signal.
Это даёт следующий эффект: чтение поля someField из объекта — это чтение памяти по адресу o.objectAddress + OClass.someFieldOffset. Если объект не гигантского размера, то OClass.someFieldOffset будет сильно меньше размера страницы памяти. Значит, если o.objectAddress == 0 (а именно так реализуют null), то инструкция чтения поля someField прочитает что-то из нулевой страницы и вызовет исключение. Это исключение попадёт в обработчик, который JVM задаёт при инициализации. Обработчик сконструирует NullPointerException и выбросит его уже так, как это сделал бы код на Java.
Т.е. для чтения поля в x86 достаточно сгенерировать одну инструкцию:
mov eax, [ebx + 12]
Однако, в WebAssembly нет POSIX, нет концепции сигналов и защиты памяти. Поэтому всё, что остаётся делать — всё время делать явные проверки на null. В псевдокоде это выглядит так:
if (obj == null) {
localRoots.callSiteId = 1;
throw NullPointerException();
}
doSomethingWith(obj.someField);
а в Wasm так:
(set_local 4 ;; прочитали поле q объекта this
(i32.load offset=8 align=4
(get_local 0)))
(if ;; если оно null
(i32.eq
(get_local 4)
(i32.const 0))
(then
(i32.store align=4 ;; сохраняем call site id в shadow stack
(get_local 20)
(i32.const 471))
(call $teavm_throwNullPointerException)
;; кидаем NPE
(br $block_0)))
;; иначе делаем что-то c local 4
В JavaScript эта проблема присутствует частично. С одной стороны, по умолчанию JS кидает невразумительное исключение TypeError, которое может быть вызвано кучей других причин. С другой стороны, он хотя бы кидает его, виртуальная машина при этом не разваливается, куча не повреждается. В JavaScript бэкэнде TeaVM можно выбрать, генерировать ли строгий (strict) код или нет. В строгий код вставляются такие же явные проверки в JS, а нестрогий просто игнорирует подобные ситуации.
В HotSpot это не является проблемой. При первом вызове метода он будет скорее всего интерпретироваться, т.е. к моменту компиляции в нативный код мы можем быть уверены, что класс проинициализирован и, следовательно, не добавлять никаких проверок. В случае AOT компиляции ситуация сложнее. С одной стороны, у x86 и ARM нет разделения на память для кода и для данных, можно переписывать код как захочется. С другой стороны, есть защита памяти и операционная система может после загрузки запретить переписывать код. Однако, если удалось заставить ОС дать права на перезапись кода, можно вместо вызова <clinit> вписать инструкцию nop. Однако, WebAssembly такое точно не поддерживает ни при каких условиях. Т.е. если у нас есть, скажем, чтение статического поля:
doSomethingWith(SomeClass.staticField);
то это должно быть трансформировано в следующий псевдокод:
if (!SomeClass.<initialized>) {
SomeClass.<clinit>();
}
doSomethingWith(SomeClass.staticField);
но мы же помним, что для нужд GC и исключений небходимо вызов метода окружать дополнительными инструкциями? Да, ситуация ровно такова, если посмотреть на сгенерированный Wasm:
(if ;; если класс не проинициализирован
(i32.eq
(i32.and
(i32.load align=4
(i32.const 6260)) ;; 6260 - это адрес скрытого статического поля
;; BigInteger.<flags>
;; нулевой бит <flags> - флаг инициализации
(i32.const 1))
(i32.const 0))
(i32.store offset=4 align=4 ;; далее очищаем shadow stack
(get_local 11) ;; прошлый вызов положил в эти ячейки shadow stack
(i32.const 0)) ;; какие-то значения, но теперь они
(i32.store offset=8 align=4 ;; перестали быть живыми (live)
(get_local 11) ;; и мы не хотим держать ссылки на них
(i32.const 0))
(i32.store offset=12 align=4
(get_local 11)
(i32.const 0))
(i32.store align=4 ;; сохраняем id этого call site - 577
(get_local 11)
(i32.const 577))
(call $initclass_jm_BigInteger)
(if ;; если id call site изменился - выбросили исключение
(i32.ne
(i32.load align=4
(get_local 11))
(i32.const 577))
(then
(br $block_1))))) ;; в этом случае выходим из метода немедленно
(set_local 1 ;; наконец читаем поле
(i32.load align=4
(i32.const 6208)))
К счастью, для простых инициализаторов можно понять, что семантика программы не поменяется, если вызвать этот инициализатор в самом начале программы. Оказывается, что таких случаев — подавляющее большинство, и это частично решает проблему. Ещё можно анализировать поток управления метода и понимать, что перед чтением/записью поля класс уже был проинициализирован и убрать инструкции инициализации.
В JavaScript можно прибегнуть к следующему трюку:
function SomeClass_clinit() {
// do initialization
}
function SomeClass_callClinit() {
SomeClass_callClinit = function() { };
SomeClass_clinit();
}
и в месте чтения поля будет добавлен вызов SomeClass_callClinit. Казалось бы, это тоже оверхед. Но на самом деле, JS в наши дни выполняется в JIT. При первом вызове метода он будет проинтерпретирован, вызван SomeClass_callClinit, который перепишет сам себя. Так что когда JIT решит скомпилировать метод, он увидит, что в нём есть вызов пустого SomeClass_callClinit и просто удалит его.
Итак, прежде всего про GC. Начнём с того, что де-факто его нет: прошло уже 6 лет с тех пор, как я о нём услышал, а в спецификацию он до сих пор не попал и реализован только в Google Chrome под экспериментальным флагом. В любом случае, к спецификации у меня есть ряд претензий.
Во-первых, оверхед по памяти. Суть спецификации в том, что вводится понятие "структура", их можно создавать, читать/писать поля. Структуры, которые стали недостижимы, убираются. Это то, что нужно. Вот только для того, чтобы структуры убирались GC, необходимо в рантайме знать их тип, т.е. в самом начале структуры выделять N байт (подозреваю, что 4 или 8) для хранения типа. С другой стороны, в Java поддерживаются виртуальные вызовы. Как в языках поддерживаются виртуальные вызовы: в классе в начале есть невидимое поле, указывающее на таблицу функций. При виртуальном вызове компилятор порождает последовательность команд, которые получают ссылку на таблицу функций и затем вызывают функцию с известным номером из этой таблицы. Например, такой код
class A {
void foo(int param) { /* do something */ }
long bar() { /* do something */ }
}
class B extends A {
void foo(int param) { /* do something */ }
long bar() { /* return something */ }
}
void test(A a) {
a.foo(23);
a.bar();
}
можно переписать на C примерно так:
struct A;
typedef struct {
void (*foo)(A*, int);
long (*bar)(A*);
} vtable;
typedef struct A {
vtable* __vtable;
} A;
void A_foo(A* self, int parm) { /* do something*/ }
long A_bar(A* self) { /* do something*/ }
vtable A_vtable = {
&A_foo,
&A_bar
};
void B_foo(A* self, int parm) { /* do something*/}
long B_bar(A* self) { /* do something*/ }
vtable B_vtable = {
&B_foo,
&B_bar
};
void test(A* a) {
a->__vtable->foo(a, 23);
a->__vtable->bar(a);
}
ну а создание экземпляров классов будет выглядеть так:
A* a = malloc(sizeof(A));
a->__vtable = &A_vtable;
A* b = malloc(sizeof(A));
b->__vtable = &B_vtable;
На самом же деле, эта "таблица функций" как раз и описывает тип. Так что в Java достаточно иметь одно поле для того, чтобы работали и GC и виртуальные вызовы. Т.е. с учётом сборщика мусора Java структура vtable модифицируется так:
typedef struct {
int fieldCount;
short** fieldOffsets;
void (*foo)(A*, int);
long (*bar)(A*);
} vtable;
В спецификации GC для WebAssembly так сделать не получится. Про расположение полей в объекте знает только компилятор WebAssembly и он порождает примерно такой код:
typedef struct {
int fieldCount;
short** fieldOffsets;
} tuple_layout;
typedef struct {
tuple_layout __layout;
A data;
} A_tuple;
получается, что в результате в структуре будет два ссылочных поля: __layout и __vtable, что приводит к перерасходу памяти.
Во-вторых, проверки на null. Операции доступа к полям структуры выкидывают то, что в спецификации WebAssembly называется trap (ловушка). Ловушка — это не исключение, её никак нельзя поймать и обработать. Это уже лучше: в отсутствии проверки на null виртуальная машина не разваливается неожиданным образом, а просто стразу падает без возможности восстановления. Однако, это ещё хуже чем JavaScript без проверки на null, где можно NPE хоть как-то поймать. Ну и конечно хуже идеального варианта — выброса честных NPE без оверхеда.
Второе существенное обновление — это exception handling. С поддержкой браузерами тут всё намного лучше. Однако, сама спецификация странная. Во-первых, в типах исключений отсутствует наследование. Это не самая большая проблема: можно в catch подставлять идентификаторы всех подтипов заявленного типа исключения, хотя, разумеется, это оверхед. Другая неприятность: в инструкции throw тип исключения — константа. Видимо, не подумали о ситуациях, отличных от тех, когда исключение создали и тут же выбросили. Ничего лучше, чем делать огромный switch, который принимает значение типа i32 (тип исключения) и в каждой ветке выбрасывать исключение с заданным типом, я не могу придумать.
В-третьих, я бы ускорил рассмотрение proposal memory control.
habr.com
Хочу так же оговориться, что изложенное является моим мнением, я не самый умелый разработчик компиляторов в мире, над разработкой сколь угодно известных управляемых сред не трудился, а весь мой компиляторный опыт — это упомянутый выше PET-проект (который, однако, используется в продакшене некоторыми компаниями) и около 2 лет работы над Kotlin/JS.
Как я вообще дошёл до жизни такой
То есть до разработки компилятора байт-кода JVM в WebAssembly. Всё начиналось 10 лет назад, когда никакого WebAssembly ещё в планах не было. Тогда я так или иначе встречался в работе с GWT и мне очень нравилось, что можно иметь общую кодовую базу, общую IDE, систему сборки, единую культуру разработки фронтэнда и бэкэнда (я имею в виду фротэнд и бэкэнд в классическом, а не в компиляторном понимании). Но что всегда казалось странным: почему в качестве "исходника" берутся именно исходные коды Java, а не байт-код JVM? У меня тогда были определённые познания в том, как устроена JVM и байт-код, и казалось, что последний является достаточно высокоуровневым, чтобы из него можно было сгенерировать вполне прилично выглядящий JavaScript. Ведь так можно было бы транслировать в JavaScript код, написанный на любом более-менее статическом языке вроде Java или Scala (Kotlin пошёл в массы чуть позже). Т.к. темой написания компиляторов я интересовался ещё с малых лет, мне пришло в голову, что я мог бы в самообразовательных целях написать proof-of-concept аналога GWT, принимающего на вход байт-код.Прошло много времени, мой proof-of-concept становился всё более и более пригодным для реальных проектов, кто-то даже стал осторожно использовать его. И тут появляется WebAssembly. Поскольку TeaVM явно не хватало популярности, я попытался выехать на хайпе, может быть, прыгнуть в вагон поезда раньше других, и приступил к написанию WebAssembly бэкэнда (в компиляторном смысле). Однако, через какое-то время я разочаровался в этой технологии: wasm-файлы получались огромными, а производительность не была намного лучше JavaScript. При этом сгенерированный код WebAssembly было очень тяжело отлаживать и очень тяжело взаимодействовать с JavaScript. Ну и темп развития спецификации мне показался очень уж черепашьим, а докричаться до комитета и попытаться "протолкнуть" необходимые для рантайма фичи представлялось маловероятным.
Немного о стеке
Но прежде, чем рассказать о трудностях с WebAssembly, мне необходимо объяснить, как в CPU реализован стек и как компиляторы используют его для вызова функций. Я буду рассказывать на примере x86, т.к. более-менее хорошо знаю только эту архитектуру. Полагаю, ситуация на ARM практически идентична за исключением небольших тонкостей.Итак, для CPU нет понятия "стек". У CPU есть линейная непрерывная память, откуда можно читать и куда можно писать значения. Стек реализуется с помощью специального регистра (esp или rsp на x86), который хранит адрес в памяти вершины стека. Запись в стек (операция push) — это уменьшение esp и запись значения по адресу, хранящемуся в esp. Чтение из стека — это чтение значения по адресу, хранящемуся в esp и увеличение esp. Есть ещё операции вызова процедуры (call) и возврата из процедуры (ret). call %target% кладёт на стек адрес следующей команды (программный счётчик) и записывает %taget% в eip. ret читает значение со стека в регистр eip (адрес текущей инструкции).
При этом никто не мешает брать и читать/писать в стек минуя esp и описанные операции. Вот, например, как начинается функция, сгенерированная типичным компилятором для 32-битного x86:
push ebp
mov ebp, esp
sub esp, N
Последняя операция резервирует на стеке N байт, где N — это суммарное количество байт во всех локальных переменных функции. Дальше, если функция что-то делает с локальными переменными, то она обращается по адресу относительно ebp. Например, строчка
local1 = local2 + local3;
может превратиться во что-то вроде
mov eax, [ebp - 8]
add eax, [ebp - 12]
mov [ebp - 4], eax
и тут надо обратить внимание вот на что: у функции нет "своего" стекового кадра. Точнее, он есть только если автор функции хочет, чтобы программа не разламывалась. Но на уровне железа никаких гарантий нет. Можно брать и читать содержимое стека, можно писать в него — это вполне допустимо с точки зрения CPU. И авторы рантаймов этот факт активно используют.
Что такое WebAssembly
Полагаю, что у некоторых разработчиков закрепилось мнение, что WebAssembly — это такой набор команд, вроде x86/64 или ARM, который, не реализован в реальном железе, а исполняется браузером. Это отчасти справедливо, однако, есть несколько принципиальных различий:- В WebAssembly отсутствует доступ к стеку. В WebAssembly определены такие сущности, как функции и локальные переменные. При компиляции вызовов функций скорее всего будут использоваться инструкции для работы со стеком. Однако, получить доступ к аппаратному стеку никак нельзя, даже на чтение.
- В WebAssembly нельзя делать goto в произвольное место. Причём, даже внутри функции. Можно объявить блок и сделать из него break.
- В WebAssembly нет доступа к коду. Нельзя просто так взять и переписать его, как это можно делать в x86.
- В WebAssembly нельзя линковаться к системным динамическим библиотекам. WebAssembly не реализует чего-то аналогичного POSIX.
Сборка мусора
Простейший сборщик мусора — это довольно тривиальная вещь. Первая фаза, mark, сводится к обходу графа объектов в ширину или в глубину, начиная с так называемых GC roots — значений статических полей и локальных переменных на стеке JVM. Примерный псевдокод:void mark() {
for (var root : staticFields) {
if (root.deref() != null) {
queue.add(root.deref());
}
}
for (var frame : stack) {
for (var localVar : frame.type.localVars) {
if (frame.data.read(localVar) != null) {
queue.add(frame.data[localVar]);
}
}
}
while (queue.notEmpty()) {
o = queue.remove();
if (o.marked) continue;
o.marked = true;
for (field in o.type.fields) {
next = o.data[field];
if (next != null && !next.marked) {
queue.add(next);
}
}
}
}
В случае с x86 второй цикл — это итерация, начиная с текущего значения esp. При входе в mark на вершине стека будет лежать адрес возврата. Зная адрес возврата, можно вычислить функцию, вызвавшую mark, а для неё известен размер стекового кадра. Добавив в esp этот размер, получим адрес следующей по стеку функции и т.д. Так можно пройтись по всем кадрам. Опять же, зная адреса возврата, можно воспользоваться табличкой, которая сопоставляет эти адреса смещениям, по которым располагаются ссылочные локальные переменные. Пройдясь по этим смещениям относительно начала стекового кадра, можно пройтись по переменным этого кадра (цикл по frame.type.localVars).
И вот тут нас ожидает первая проблема: никак нельзя получить доступ к стеку WebAssembly. Выход тут один — необходимо программно эмулировать стек и значения локальных переменных, указывающих на объекты, дублировать в этом стеке перед КАЖДЫМ вызовом какого-нибудь метода. Такая структура называется shadow stack. Примерно это будет выглядеть так:
// начало метода
localRoots = shadowStack.alloc(FRAME_SIZE);
// ...
localRoots[0] = localVar1;
localRoots[1] = localVar2;
// и т.д.
foo();
// ...
shadowStack.release(FRAME_SIZE);
// конец метода
Или пример из реально сгенерированного wasm:
;; начало метода
(set_local 12 ;; выделяем в shadow stack место под хранение
;; одной 4-байтовой переменной
(call $meth_otbw_WasmRuntime_allocStack
(i32.const 1)))
;; ...
;; вызов (call site)
(i32.store offset=4 align=4 ;; помещаем значение local7 в shadow stack
(get_local 12)
(get_local 7))
(set_local 1 ;; вызываем метод (полезная работа)
(call $meth_jl_Character_forDigit
(get_local 1)
(get_local 3)))
;; ...
;; конец метода
(i32.store align=4 ;; возвращаем занятые 4 байта в shadow stack
(i32.const 728) ;; 728 - это адрес в памяти, по которому находится
;; текущее значение вершины стека
(i32.sub
(get_local 12)
(i32.const 4)))
Понятно, что это, во-первых, медленно, а, во-вторых, лишние траты памяти. Есть ухищрения, которые позволяют минимизировать записи в shadow stack, однако в любом случае, получается дорого.
Полагаю, мотивацией для разработчиков спецификации являлась безопасность. Действительно, возможность просто так взять и поменять содержимое стека или стекового регистра — это один из главных источников дыр в ПО. С другой стороны, для реализации GC вовсе не нужно менять стековый регистр или писать в стек в произвольное место. Достаточно просто прочитать оттуда данные. Ведь данные из памяти WebAssembly может читать — и ничего. То же самое с оптимизациями: при грамотно написанной спецификации оверхед можно свести к минимуму, и этот оверхед в любом случае значительно меньше того, что даёт shadow stack.
Почему в JavaScript такой проблемы нет? Потому что в JavaScript уже есть сборщик мусора. Достаточно просто превращать Java объекты в JavaScript объекты.
Выброс исключений
Как реализуют выброс исключений в JVM: проходятся по стеку вверх и ищут такой адрес возврата, который находится внутри catch с подходящим типом исключения. Далее, модифицируют регистр стека (esp/rsp в случае с x86) и делают goto на адрес обработчика исключения. Вот примерный псевдокод:exceptionType = exception.getClass();
for (var frame : stack) {
callSite = callSites.lookup(frame.returnAddress)
for (var handler : callSite.exceptionHandlers) {
if (handler.exceptionType.isAssignableFrom(exceptionType)) {
stack.top = frame;
goto handler.address; // межпроцедурный goto, которого нет в Java
}
}
}
Т.е. catch, который не ловит исключение, не имеет накладных расходов, всей работой занимается только throw.
Однако, WebAssembly не даёт ходить по стеку, делать goto или узнавать адрес инструкции. Поэтому всё, что остаётся делать — это на выходе из каждого метода проверять некоторый код возврата. Кроме того, перед вызовом метода необходимо записать в shadow stack его идентификатор. На самом деле, TeaVM хранит "код возврата" в shadow stack — он пишет его поверх идентификатора call site. Вот псевдокод метода с учётом try/catch:
localRoots[0] = localVar1;
localRoots[1] = localVar2;
// и т.д.
localRoots.callSiteId = 1;
foo()
// и т.д.
switch (localRoots.callSiteId) {
case 1: goto nextInstruction;
case 2: releaseStack(); return;
case 3: goto firstExceptionHandler;
case 4: goto secondExceptionHandler;
// и т.д.
}
nextInstruction:
// continue after call
Вот пример из реального wasm-файла:
(block $block_4
(i32.store offset=4 align=4 ;; сохраняем локальную переменную в shadow stack
(get_local 13)
(get_local 2))
(i32.store align=4 ;; сохраняем в него же call site id (47)
(get_local 13)
(i32.const 47))
(set_local 3 ;; вызываем метод (полезная работа)
(call $meth_jl_Integer_parseInt_0
(get_local 2)))
(block $block_5
(block $block_3
(block $block_2
(block $block_1
(br_table $block_1 $block_2 $block_3
;; читаем код возврата
(i32.sub
(i32.load align=4
(get_local 13))
(i32.const 47))))
(br $block_4))
(br $block_5))
(br $block_0)) ;; если код 48, то выходим из метода
;; если код возврата 49, попадаем сюда, т.е. в обработчик NumberFormatException
;; тут обрабатываем исключение
(br $block_6) ;; выходим из метода
)
;; если код возврата 47, попадаем сюда, т.е. продолжаем выполнение после catch
Почему это не проблема в JavaScript? Потому что в JavaScript из коробки поддерживается try/catch, и достаточно просто превращать try/catch в Java в try/catch в JavaScript.
Проверки на null
В подобных фрагментах Java-машина может выбросить NullPointerException.doSomethingWith(o.someField);
doSomethingWith(o.someMethod());
Конечно, ставить явную проверку на null — это дорого. Поэтому любая уважающая себя реализация JVM при инициализации вызывает какой-нибудь mprotect на нулевой странице (в Windows это делается похожей по смыслу функцией VirtualAlloc). Что это за mprotect? В современных CPU можно назначать разным участкам памяти (обычно, разбитым на страницы фиксированного размера) права доступа: чтение, запись, выполнение. Если программа нарушает эти права, то процессор сгенерирует исключение, которое можно попытаться обработать — этим занимается ядро операционной системы. Код программы может попросить ядро повесить обработчик на исключения процессора с помощью функции signal.
Это даёт следующий эффект: чтение поля someField из объекта — это чтение памяти по адресу o.objectAddress + OClass.someFieldOffset. Если объект не гигантского размера, то OClass.someFieldOffset будет сильно меньше размера страницы памяти. Значит, если o.objectAddress == 0 (а именно так реализуют null), то инструкция чтения поля someField прочитает что-то из нулевой страницы и вызовет исключение. Это исключение попадёт в обработчик, который JVM задаёт при инициализации. Обработчик сконструирует NullPointerException и выбросит его уже так, как это сделал бы код на Java.
Т.е. для чтения поля в x86 достаточно сгенерировать одну инструкцию:
mov eax, [ebx + 12]
Однако, в WebAssembly нет POSIX, нет концепции сигналов и защиты памяти. Поэтому всё, что остаётся делать — всё время делать явные проверки на null. В псевдокоде это выглядит так:
if (obj == null) {
localRoots.callSiteId = 1;
throw NullPointerException();
}
doSomethingWith(obj.someField);
а в Wasm так:
(set_local 4 ;; прочитали поле q объекта this
(i32.load offset=8 align=4
(get_local 0)))
(if ;; если оно null
(i32.eq
(get_local 4)
(i32.const 0))
(then
(i32.store align=4 ;; сохраняем call site id в shadow stack
(get_local 20)
(i32.const 471))
(call $teavm_throwNullPointerException)
;; кидаем NPE
(br $block_0)))
;; иначе делаем что-то c local 4
В JavaScript эта проблема присутствует частично. С одной стороны, по умолчанию JS кидает невразумительное исключение TypeError, которое может быть вызвано кучей других причин. С другой стороны, он хотя бы кидает его, виртуальная машина при этом не разваливается, куча не повреждается. В JavaScript бэкэнде TeaVM можно выбрать, генерировать ли строгий (strict) код или нет. В строгий код вставляются такие же явные проверки в JS, а нестрогий просто игнорирует подобные ситуации.
Инициализация класса
В JVM классы инициализируются лениво. Есть ряд действий, которые вызывают инициализацию класса: чтение или запись в статическое поле, вызов статического метода, вызов конструктора, явная инициализация через reflection. При инициализации класса у него вызывается скрытый метод void <clinit>().В HotSpot это не является проблемой. При первом вызове метода он будет скорее всего интерпретироваться, т.е. к моменту компиляции в нативный код мы можем быть уверены, что класс проинициализирован и, следовательно, не добавлять никаких проверок. В случае AOT компиляции ситуация сложнее. С одной стороны, у x86 и ARM нет разделения на память для кода и для данных, можно переписывать код как захочется. С другой стороны, есть защита памяти и операционная система может после загрузки запретить переписывать код. Однако, если удалось заставить ОС дать права на перезапись кода, можно вместо вызова <clinit> вписать инструкцию nop. Однако, WebAssembly такое точно не поддерживает ни при каких условиях. Т.е. если у нас есть, скажем, чтение статического поля:
doSomethingWith(SomeClass.staticField);
то это должно быть трансформировано в следующий псевдокод:
if (!SomeClass.<initialized>) {
SomeClass.<clinit>();
}
doSomethingWith(SomeClass.staticField);
но мы же помним, что для нужд GC и исключений небходимо вызов метода окружать дополнительными инструкциями? Да, ситуация ровно такова, если посмотреть на сгенерированный Wasm:
(if ;; если класс не проинициализирован
(i32.eq
(i32.and
(i32.load align=4
(i32.const 6260)) ;; 6260 - это адрес скрытого статического поля
;; BigInteger.<flags>
;; нулевой бит <flags> - флаг инициализации
(i32.const 1))
(i32.const 0))
(i32.store offset=4 align=4 ;; далее очищаем shadow stack
(get_local 11) ;; прошлый вызов положил в эти ячейки shadow stack
(i32.const 0)) ;; какие-то значения, но теперь они
(i32.store offset=8 align=4 ;; перестали быть живыми (live)
(get_local 11) ;; и мы не хотим держать ссылки на них
(i32.const 0))
(i32.store offset=12 align=4
(get_local 11)
(i32.const 0))
(i32.store align=4 ;; сохраняем id этого call site - 577
(get_local 11)
(i32.const 577))
(call $initclass_jm_BigInteger)
(if ;; если id call site изменился - выбросили исключение
(i32.ne
(i32.load align=4
(get_local 11))
(i32.const 577))
(then
(br $block_1))))) ;; в этом случае выходим из метода немедленно
(set_local 1 ;; наконец читаем поле
(i32.load align=4
(i32.const 6208)))
К счастью, для простых инициализаторов можно понять, что семантика программы не поменяется, если вызвать этот инициализатор в самом начале программы. Оказывается, что таких случаев — подавляющее большинство, и это частично решает проблему. Ещё можно анализировать поток управления метода и понимать, что перед чтением/записью поля класс уже был проинициализирован и убрать инструкции инициализации.
В JavaScript можно прибегнуть к следующему трюку:
function SomeClass_clinit() {
// do initialization
}
function SomeClass_callClinit() {
SomeClass_callClinit = function() { };
SomeClass_clinit();
}
и в месте чтения поля будет добавлен вызов SomeClass_callClinit. Казалось бы, это тоже оверхед. Но на самом деле, JS в наши дни выполняется в JIT. При первом вызове метода он будет проинтерпретирован, вызван SomeClass_callClinit, который перепишет сам себя. Так что когда JIT решит скомпилировать метод, он увидит, что в нём есть вызов пустого SomeClass_callClinit и просто удалит его.
Обновления в спецификации, которые не помогли
Со времён MVP вышли полезные дополнения, способные решить часть заявленных тут проблем: GC и Exception handling. Однако, при пристальном взгляде на них, либо решают проблемы плохо, либо порождают другие проблемы.Итак, прежде всего про GC. Начнём с того, что де-факто его нет: прошло уже 6 лет с тех пор, как я о нём услышал, а в спецификацию он до сих пор не попал и реализован только в Google Chrome под экспериментальным флагом. В любом случае, к спецификации у меня есть ряд претензий.
Во-первых, оверхед по памяти. Суть спецификации в том, что вводится понятие "структура", их можно создавать, читать/писать поля. Структуры, которые стали недостижимы, убираются. Это то, что нужно. Вот только для того, чтобы структуры убирались GC, необходимо в рантайме знать их тип, т.е. в самом начале структуры выделять N байт (подозреваю, что 4 или 8) для хранения типа. С другой стороны, в Java поддерживаются виртуальные вызовы. Как в языках поддерживаются виртуальные вызовы: в классе в начале есть невидимое поле, указывающее на таблицу функций. При виртуальном вызове компилятор порождает последовательность команд, которые получают ссылку на таблицу функций и затем вызывают функцию с известным номером из этой таблицы. Например, такой код
class A {
void foo(int param) { /* do something */ }
long bar() { /* do something */ }
}
class B extends A {
void foo(int param) { /* do something */ }
long bar() { /* return something */ }
}
void test(A a) {
a.foo(23);
a.bar();
}
можно переписать на C примерно так:
struct A;
typedef struct {
void (*foo)(A*, int);
long (*bar)(A*);
} vtable;
typedef struct A {
vtable* __vtable;
} A;
void A_foo(A* self, int parm) { /* do something*/ }
long A_bar(A* self) { /* do something*/ }
vtable A_vtable = {
&A_foo,
&A_bar
};
void B_foo(A* self, int parm) { /* do something*/}
long B_bar(A* self) { /* do something*/ }
vtable B_vtable = {
&B_foo,
&B_bar
};
void test(A* a) {
a->__vtable->foo(a, 23);
a->__vtable->bar(a);
}
ну а создание экземпляров классов будет выглядеть так:
A* a = malloc(sizeof(A));
a->__vtable = &A_vtable;
A* b = malloc(sizeof(A));
b->__vtable = &B_vtable;
На самом же деле, эта "таблица функций" как раз и описывает тип. Так что в Java достаточно иметь одно поле для того, чтобы работали и GC и виртуальные вызовы. Т.е. с учётом сборщика мусора Java структура vtable модифицируется так:
typedef struct {
int fieldCount;
short** fieldOffsets;
void (*foo)(A*, int);
long (*bar)(A*);
} vtable;
В спецификации GC для WebAssembly так сделать не получится. Про расположение полей в объекте знает только компилятор WebAssembly и он порождает примерно такой код:
typedef struct {
int fieldCount;
short** fieldOffsets;
} tuple_layout;
typedef struct {
tuple_layout __layout;
A data;
} A_tuple;
получается, что в результате в структуре будет два ссылочных поля: __layout и __vtable, что приводит к перерасходу памяти.
Во-вторых, проверки на null. Операции доступа к полям структуры выкидывают то, что в спецификации WebAssembly называется trap (ловушка). Ловушка — это не исключение, её никак нельзя поймать и обработать. Это уже лучше: в отсутствии проверки на null виртуальная машина не разваливается неожиданным образом, а просто стразу падает без возможности восстановления. Однако, это ещё хуже чем JavaScript без проверки на null, где можно NPE хоть как-то поймать. Ну и конечно хуже идеального варианта — выброса честных NPE без оверхеда.
Второе существенное обновление — это exception handling. С поддержкой браузерами тут всё намного лучше. Однако, сама спецификация странная. Во-первых, в типах исключений отсутствует наследование. Это не самая большая проблема: можно в catch подставлять идентификаторы всех подтипов заявленного типа исключения, хотя, разумеется, это оверхед. Другая неприятность: в инструкции throw тип исключения — константа. Видимо, не подумали о ситуациях, отличных от тех, когда исключение создали и тут же выбросили. Ничего лучше, чем делать огромный switch, который принимает значение типа i32 (тип исключения) и в каждой ветке выбрасывать исключение с заданным типом, я не могу придумать.
Как бы я исправил проблему
Во-первых, я бы реализовал stack walking. Такая спецификация предполагала бы ввод дополнительной инструкции call (или расширения существующей), в которой можно указать:- Идентификатор этой инструкции.
- Номера локальных переменных, которые можно наблюдать через stack walking
- Для каждой переменной из предыдущего списка — можно ли её модифицировать через stack walking.
- Список меток.
- Создать stack walker
- Выбрать следующий кадр, если это возможно
- Выбрать следующую локальную переменную в кадре, если это возможно.
- Прочиать текущую выбранную переменную.
- Записать в текущую выбранную переменную.
- Уничтожить stack walker.
- Уничтожить stack walker, завершить текущую функцию, отмотать стек к выбранному кадру и моментально перейти по метке с указанным индексом.
В-третьих, я бы ускорил рассмотрение proposal memory control.
Бонус. Немного цифр
Для этой статьи я не поленился сделать кое-какие замеры. Итак, развенчиваем мифы, что реализация GC — это огромное количество байт в бинарнике. По моим подсчётам, суммарный размер кода, отвечающего за рантайм (GC + exception handling), на текущий момент (19.08.2023) составляет 11 340 байт. Для подсчёта я просуммировал размеры wasm-функций, соответствующим методам классов org.teavm.runtime.Allocator, org.teavm.runtime.GC и org.teavm.runtime.ExceptionHandling (да, GC тоже написан на Java, на некотором специальном её подмножестве, сдобренном intrinsics). Считал на следующих примерах:- benchmark (обсчитывает сценку с помощью физической библиотеки jbox2d):
- общий размер: 771 331
- размер секции code: 547 065
- размер секции data: 194 177
- демо
- pi (считает PI до указанного количества знаков)
- общий размер: 144 000
- размер секции code: 74 996
- размер секции data: 55 509
- демо
Почему WebAssembly плохо годится для Java
Как разработчик TeaVM , компилятора байт-кода JVM в JavaScript и WebAssembly, я часто рекомендую пользователям, почему-то жаждущим сгенерировать WebAssembly, начать с JavaScript. Если честно, бэкэнд...
habr.com