Технопорно с WebAssembly +35


По просьбам трудящихся, пишу о внутреннем устройстве WebAssembly.


WebAssembly — байткод для стековой виртуальной машины. Значит, для запуска кода такой нужны интерпретатор, стек и хранилище кода. Если мы хотим взаимодействовать с внешним миром, нужен интерфейс к внешней машине, хосту. Дополнительно стандарт определяет две структуры: непрерывную память и таблицы. В версии MVP стандарта их может быть по одной штуке каждого, или не быть вовсе.


В итоге, наш технобордель выглядит так:



  • Интерпретатор
  • Интерфейс к хосту
  • Стек
  • Хранилище кода
  • Память
  • Таблица

Займёмся делом!


Стековая виртуальная машина.


Есть два базовых вида машинных архитектур: стековая и регистровая. Нас интересует стековая.


image


Все операции стековой машины, очевидно, работают со стеком переменных. У виртуальной машины WebAssembly две особенности:


  • Формализованность: по коду всегда можно однозначно вычислить размер стека и типы значений на любом этапе исполнения
  • Независимость стека: переменные на стеке не могут быть адресованы по указателю

Остальные принципы работы машины обычны: прежде, чем выполнить операцию, операнды нужно положить в стек. Операция забирает аргументы из стека, выполняется и кладёт результат в стек.


Когда вы вызываете функцию из WebAssembly, интерпретатор:


  1. Кладёт аргументы функции на стек
  2. Дополняет их локальными переменными
  3. Выполняет работу
  4. Снимает локальные переменные и параметры со стека, оставляя только результат

В стандарте всего 4 типа переменных:


  • i32: 32-битное целое
  • i64: 64-битное целое
  • f32: 32-битное с плавающей точкой
  • f64: 64-битное с плавающей точкой

Не определена ни знаковость, ни типы 16-битных и 8-битных значений. Всё это отдано на откуп компилятору исходного языка. В случае в C/C++/Rust локальные переменные будут расширены до 32-битных значений. Указатели представляются как i32, что позволяет адресовать только 4гб памяти. Версия wasm64 с 64-битными указателями в разработке.


Посмотрим на примере:


int increment(int value) {
    return value + 1;
}

(module
  ;; Cигнатура функции: берёт один i32,  возвращает один i32
  (type (;0;) (func (param i32) (result i32)))
  ;; А это - сама функция
  (func (;0;) (type 0) (param i32) (result i32)
    (local i32 i32)
    i32.const 1 ;; Размещаем 1 на стеке
    set_local 1 ;; Устанавливаем локальную переменную 1, забирая аргумент со стека
    get_local 0 ;; Кладём на стек переменную 0 (это входной параметр)
    get_local 1 ;; Кладём на стек переменную 1
    i32.add     ;; Суммируем два последних аргумента на стеке
    set_local 2 ;; Кладём в переменную 2 результат со стека
    get_local 2 ;; Кладём на стек переменную 2
    return) ;; Выходим из функции, возвращая результат
  (export "incr_decr" (func 0)))

По мелочи

Синтаксис подсвечен для ocaml, который построен на таких же S-выражениях, как и текстовый формат WebAssembly. Вдруг такой грязный хак кому пригодится.


Как видно, компилятор создаёт довольно много ненужного кода по управлению локальными переменными. Для устранения этого, совсем недавно в binaryen добавлен проход оптимизатора.


Примеры привожу не в рукописном виде S-выражений, а в виде декомпиляции бинарного формата с помощью WABT. Так проще для понимания с непривычки, ИМХО.


Устройство кода.


Код в WebAssembly это команды для виртуальной машины, управляющие положением дел на стеке. Традиционно они называются опкодами (от operation code). Стандартный набор кодов меньше 255, потому при бинарном кодировании такие коды занимают один байт. Наборы расширений (SIMD, потоки, исключения) определяют свои наборы опкодов, для которых используются однобайтные префиксы. То есть, опкод расширения занимает два байта.


Опкодами представлены все основные операции: арифметика, преобразования типов, работа с локальными переменными и памятью, вызовы функций, управление потоком исполнения.


Опкоды сгруппированы в функции. У каждой функции есть порядковый номер и сигнатура: список параметров и возвращаемых значений с указанием типа. На основе сигнатуры определяется, сколько значений нужно взять из стека, и сколько вернуть.


Функции вызываются опкодами call и call_indirect. Cперва на стек нужно положить аргументы, а в результате аргументы будут сняты, а результат покладен добавлен на стек.


  (func (;0;) (type 0) (param f64 f32) (result f32)
    ;; Принимаем два параметра и возвращаем второй
    get_local 1
  )
  (func (;1;) (type 1) (result f32)
    ;; добавляем два параметра на стек
    f64.const 0x1p+6 (;=64;)
    f32.const 0x1p+5 (;=32;)
   ;; вызываем функцию 0
    call 0
    ;; на стеке останется результат вызова,
    ;; который пробросится и в исходный вызов
  )

В традиционном ассемблере циклы и условные переходы организуются с помощью аналогов goto. Но в WebAssembly из ненависти к goto пошли другим путём.


Внутри функции код организован в блоки. Всего блоков три вида:


  • block .. end — обычный блок, с помощью которого организуются условные переходы, устанавливает метку перехода на опкод end
  • loop .. end — блок для организации циклов, устанавливает метку перехода на опкод loop (то есть, команда прерывания блока на самом деле перезапускает этот блок)
  • if .. else .. end — выделенный блок для условий, прерывание блока вызывает переход к опкоду end, как и для обычного блока.

К блокам есть команды перехода:


  • br — безусловный переход
  • br_if — условный переход, берёт значение со стека и прерывает целевой блок, если значение не нуль
  • br_table — переход по таблице, используется для аналогов switch, прерывает блок, определяемый по индексу, взятому со стека

Параметр команды перехода — блок, который она прерывает. Блок указывается по глубине вложенности: 0 — последний открытый блок, 1 — сразу перед последним открытым.


Блоки служат ограничителями стека и могут возвращать значения. Внутри блока нельзя снять со стека аргументы, которые были на стеке во время входа в блок. Если возврат значения блоком не определён, размер стека на входе в блок будет соответствовать размеру на выходе из блока. Возвращаемые значения будут добавлены на стек сверху.


Система вышла довольно непривычной и для тех, кто привык к традиционным if-else-end и while, и для тех, кто привык работать с goto.


Выглядит это так:


(func (type 1) (param i32) (result i32)
  i32.const 1
  block (result i32) ;; начинаем внешний блок
    i32.const 2
    drop ;; убираем последнее значение со стека
    i32.const 4
    block (result i32) ;; начинаем внутренний блок
      i32.const 8
      get_local 0 ;; кладём на стек первый параметр функции
      br_if 1 ;; выходим из внешнего блока по условию со стека
      ;; если выход был успешен, на стеке останется константа 8 как результат
      drop ;; убираем константу 8 со стека
      i32.const 1 ;; устанавливаем новый результат
    end
    br_if 0 ;; отсюда внешний блок имеет индекс 0, а не 1
    drop
    i32.const 16
   end
   i32.add ;; возвращаем результат сложения
)

С переходом по таблице чуть сложнее:


(func (type 5) (param i32) (result i32)
  block ;; Будет блоком 4
    block ;; Будет блоком 3
      block  ;; Будет блоком 2
        block  ;; Будет блоком 1
          block  ;; Будет блоком 0
            get_local 0 ;; Берём параметр
            ;; значение со стека используется как индекс в таблице
            ;; если индекс слишком большой, выбирается последнее
            ;; значение (4 в данном случае)
            br_table 3 2 1 0 4
            i32.const 99
            return
          end
          i32.const 100
          return
        end
        i32.const 101
        return
      end
      i32.const 102
      return
    end
    i32.const 103
    return
  end
  i32.const 104
)

Для понимания, на C это выглядит так:


int switch_test(int l0) {
  switch(l0) {
  case 0: return 103; break;
  case 1: return 102; break;
  case 2: return 101; break;
  case 3: return 100; break;
  default: return 104; break;
  }
}

Далее, циклы выглядят так:


(func (;16;) (type 2) (param i64) (result i64)
  (local i64)
  i64.const 1
  set_local 1
  block  ;; переход на этот блок (1) прервёт выполнение цикла
    loop ;; а на этот (0): запустит следующую итерацию
      get_local 0
      i64.eqz
      br_if 1 ;; по условию прерываем блок
      get_local 0
      get_local 1
      i64.mul
      set_local 1
      get_local 0
      i64.const 1
      i64.sub
      set_local 0
      br 0 ;; переходим на следующую итерацию
    end
    unreachable
  end
  get_local 1
)

Подробности из кухни написания интерпретатора

Хоть ты тресни, но конкретно в коде для исполнения все увиденные мной интерпретаторы преобразуют все контрольные инструкции в аналоги goto ещё на этапе чтения чтении. Так быстрее и привычнее для машинного кода. Из каких соображений для байткода был выбран именно такой формат управляющих конструкций? Неужели только для красивого ручного написания?


Память


Сложные операции в WebAssembly выполняются через непрерывную память. Для WebAssembly из памяти хоста выделяются непрерывные блоки памяти страницами по 64 килобайта. По требованиям стандарта, блоки должны выделяться только для специальных нужд, в них не должны храниться ни стек, ни таблицы, ни внешние ресурсы. Адресация внутри памяти строго контролируется, получение или запись по адресу вне блока считаются ошибкой. Таким образом, создаётся песочница для безопасной работы с памятью. Чтобы зловреды на wasm не имели доступа к памяти хоста.


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


Изнутри с памятью работают опкоды вида TYPE.storeN и TYPE.loadN. Первый записывает переменную или её часть в память по заданному смещению, второй — загружает по заданному смещению.


Память — единственный способ передавать достаточно большие объекты составных типов между WebAssembly и хостом. На хосте память обычно представлена массивом байт. Указатели на память — переменные типа i32, хранящие смещение внутри этого массива. WebAssembly может запросить больше памяти операцией grow_memory. В таком случае, обычно, выделяется новый массив с новым размером, старые данные копируются в новый массив.


Имея знания об устройстве памяти, можно, наконец, написать самую известную программу:


const char *hello_world() {
    return "Hello World!";
}

(module
  (type (;0;) (func (result i32)))
  (func (;0;) (type 0) (result i32)
    ;; Строка будет записана в память при запуске модуля
    ;; Хост сможет получить эту строку по смещению внутри памяти
    i32.const 16 ;; При вызове функции вернётся 16 - смещение строки в памяти модуля
    return)
  (memory (;0;) 1)
  (export "hello_world" (func 0))
  ;; Компиляторы обычно резервируют первые байты памяти для собственных нужд,
  ;; а пользовательские данные начинают записывать со смещением.
  ;; Наша строка записана с позиции 16
  (data (i32.const 16) "Hello World!\00"))

Таблицы


Таблица — непрерывный контейнер для элементов определённого типа (одного из базовых типов WebAssembly). Таблицы, как и память, могут использоваться для связи с хостом. В отличии от памяти, таблицы строго типизированы. С точки зрения дизайна, на базе таблиц могут быть сделаны списки ссылок для сборки мусора, списки внешних ресурсов вроде дескрипторов файлов и сокетов. Сейчас таблица допускается только одна и используется она со строго определённой целью: для работы call_indirect.


call_indirect, он же непрямой или виртуальный вызов — инструмент для вызова кода, имя которому не может быть дано при компиляции. Показать это можно на примере виртуальных функций в C++. При компиляции мы определяем смещение функции в таблице виртуальных функций, а саму таблицу можно определить во время работы программы.


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


Разбираться проще на примере:


struct Vec2 {
    float x;
    float y;

    Vec2(float x, float y) : x(x), y(y) { }
    virtual ~Vec2() { }
    virtual float sq_dist() const{ return x * x + y * y; }
    virtual bool is_3d() const { return false; }
};

struct Vec3 : Vec2 {
    float z;

    Vec3(float x, float y, float z) : Vec2(x, y), z(z) { }
    virtual ~Vec3() { }
    virtual float sq_dist() const{ return Vec3::sq_dist() + z * z; }
    virtual bool is_3d() const { return true; }
};

Vec2 makeVec2(float x, float y) {
    return Vec2 ( x, y );
}

Vec3 makeVec3(float x, float y, float z) {
    return Vec3 ( x, y, z );
}

float sq_dist(const Vec2 &vec) {
    return vec.sq_dist();
}

(module
  (type (;0;) (func (param i32) (result f32)))
  (type (;1;) (func (param i32)))
  (type (;2;) (func))
  (type (;3;) (func (param i32) (result i32)))
  (type (;4;) (func (param i32 f32 f32)))
  (type (;5;) (func (param i32 f32 f32 f32)))
  (import "env" "_ZdlPv" (func (;0;) (type 1)))
  (func (;1;) (type 4) (param i32 f32 f32) ... return)
  (func (;2;) (type 3) (param i32) (result i32) ... return)
  (func (;3;) (type 1) (param i32) ... return)
  (func (;4;) (type 0) (param i32) (result f32) ... return)
  (func (;5;) (type 3) (param i32) (result i32) ... return)
  (func (;6;) (type 5) (param i32 f32 f32 f32)
    ;; Это конструктор Vec3(float x, float y, float z)
    ;; Составные типы передаются через память
    ;; Первый аргумент - адрес в памяти, в который будет записана структура
    (local i32 i32 i32 i32)
    i32.const 36 ;; Смещение в таблице виртуальных методов для Vec3
    i32.const 8 ;; Первые 8 байт в таблице зарезервированы для отслеживания
    ;; неправильно созданных вызовов
    i32.add ;; Вычисляем реальное смещение таблицы в памяти
    set_local 7 ;; И записываем в переменную

    ;; Первым значением в памяти Vec3 записывается адрес виртуальной таблицы
    ;; Таким образом, x записывается со смещением в 4 байта
    get_local 0
    get_local 1
    f32.store offset=4 ;; записываем значение x
    get_local 0
    get_local 2
    f32.store offset=8 ;; записываем значение y
    get_local 0
    get_local 7
    i32.store ;; записываем адрес виртуальной таблицы
    get_local 0
    get_local 3
    f32.store offset=12 ;; записываем значение z
    return)
  (func (;7;) (type 1) (param i32) ... return)
  (func (;8;) (type 0) (param i32) (result f32) ... return)
  (func (;9;) (type 3) (param i32) (result i32) ... return)
  (func (;10;) (type 0) (param i32) (result f32)
    ;; float sq_dist(const Vec2 &vec)
    ;; Параметр - адрес структуры в памяти
    (local i32 i32 f32)
    get_local 0
    i32.load ;; Загружаем адрес виртуальной таблицы
    set_local 2
    get_local 2
    i32.load offset=8 ;; Загружаем индекс нашей функции в таблице по смещению 8
    ;; То есть, это третья по счёту функция в таблице
    set_local 1
    get_local 0
    get_local 1
    call_indirect (type 0) ;; Заполняем аргументы и вызываем функцию
    return)
  (func (;11;) (type 2)
    ;; Для сообщения об ошибке при динамическом вызове компилятор создаёт
    ;; функцию, которая явно вызывает ошибку
    unreachable)
  (table (;0;) 8 8 anyfunc)
  (memory (;0;) 1)
  (export "memory" (memory 0))
  (export "_Z7sq_distRK4Vec2" (func 10))
  ;; Таблица адресуемых функций. По индексу 0 записана функция с ошибкой
  ;; По индексам 3 и 6 - реализации sq_dist для разных типов
  ;; (функция вызова читает из таблицы виртуальных методов по смещению 8,
  ;; начало таблицы смещено ещё на 8, а по смещению 16 в первой таблице записано
  ;; значение 3, а во второй - 6)
  (elem (i32.const 0) 11 2 3 4 5 7 8 9)

  ;; Таблица виртуальных методов для Vec2
  (data (i32.const 12) "\00\00\00\00\00\00\00\00\01\00\00\00\02\00\00\00\03\00\00\00\04\00\00\00")
  ;; Таблица виртуальных методов для Vec3
  (data (i32.const 36) "\00\00\00\00\00\00\00\00\01\00\00\00\05\00\00\00\06\00\00\00\07\00\00\00"))

Глобальные переменные


Глобальные переменные это как локальные, только для всех. В модуле есть список глобальных переменных, получить доступ к которым может любая функция в модуле с помощью опкодов get_global и set_global. Глобальные переменные бывают изменяемыми и постоянными. Тип глобальных переменных, как и локальных, ограничен базовыми. Если нужно хранить нечто более сложное — используется память, а переменная будет указателем на неё.


Основное назначение глобальных переменных — передача глобального состояния хосту и от хоста. Если вы используете глобальную переменную при компиляции своего модуля, компилятор, скорее всего, разместит её в линейной памяти и не будет создавать глобальный объект.


Комментарий аффтара

Мне вообще не удалось заставить LLVM создать глобальную переменную внутри модуля, только импортируемую. С одной стороны, это понятно, и глобальные переменные в общем смысле — глобальное зло. Но если есть механизм — должен быть и способ его использовать. А то ж*па есть, а слова нет.


Ну, поехали...


typedef struct {
    char valueChar;
    short valueShort;
    int valueInt;
    long valueLong;
    long long valueLongLong;

    unsigned char valueUnsignedChar;
    unsigned short valueUnsignedShort;
    unsigned int valueUnsignedInt;
    unsigned long valueUnsignedLong;
    unsigned long long valueUnsignedLongLong;

    float valueFloat;
    double valueDouble;

    char *valueCharPointer;
    char valueCharArray[25];
    int valueIntArray[3];
} test_struct;

extern test_struct g_importedStruct;

static test_struct g_internalStruct = {
    .valueChar = -1,
    .valueShort = -2,
    .valueInt = -3,
    .valueLong = -4,
    .valueLongLong = -5,
    .valueUnsignedChar = 1,
    .valueUnsignedShort = 2,
    .valueUnsignedInt = 3,
    .valueUnsignedLong = 4,
    .valueUnsignedLongLong = 5,
    .valueFloat = 123.0f,
    .valueDouble = 5.0,
    .valueCharPointer = "StringValue"
};

test_struct *get_imported_by_ptr() {
    return &g_importedStruct;
}

test_struct get_imported_by_value() {
    return g_importedStruct;
}

test_struct *get_internal_by_ptr() {
    return &g_internalStruct;
}

test_struct get_internal_by_value() {
    return g_internalStruct;
}

extern float g_importedFloat;

float get_imported_float() {
    return g_importedFloat;
}

(module
  (type (;0;) (func (param i32 i32 i32) (result i32)))
  (type (;1;) (func (result i32)))
  (type (;2;) (func (param i32)))
  (type (;3;) (func (result f32)))
  ;; в коде не включено ни одного заголовка,
  ;; так что memcpy - самодеятельность компилятора
  ;; в webassembly нет эффективного способа копировать куски памяти
  ;; и компилятор решил попросить такой у хоста
  (import "env" "memcpy" (func (;0;) (type 0)))
  (import "env" "g_importedStruct" (global (;0;) i32)) ;; наша g_importedStruct
  (import "env" "g_importedFloat" (global (;1;) i32)) ;; почему-то i32...
  (func (;1;) (type 1) (result i32) ;; get_imported_by_ptr
    get_global 0 ;; Просто возвращаем глобальную переменную по индексу
    return)
  (func (;2;) (type 2) (param i32) ;; get_imported_by_value
    ;; Прошу заметить, здесь мы принимаем параметр, хотя в коде на С
    ;; мы структуру возвращаем. Это, с одной стороны, RVO, а, с другой,
    ;; без известного системе механизма распределения памяти иного
    ;; варианта нет
    get_local 0 ;; параметр - указатель на блок памяти, в который запишем структуру
    get_global 0 ;; глобальная переменная - тоже указатель на блок памяти
    i32.const 112 ;; размер блока
    call 0 ;; вызываем memcpy(dest, source, size)
    drop ;; убираем результат вызова
    return)
  (func (;3;) (type 1) (result i32) ;; get_internal_by_ptr
    ;; Здесь всё проще, поскольку положение структуры в памяти
    ;; мы знаем на этапе компиляции
    i32.const 16 ;; его и возвращаем
    return)
  (func (;4;) (type 2) (param i32) ;; get_internal_by_value
    ;; то же самое, что и в get_imported_by_value,
    ;; но с заранее известным указателем
    get_local 0
    i32.const 16
    i32.const 112
    call 0
    drop
    return)
  (func (;5;) (type 3) (result f32) ;; get_imported_float
    ;; как очевидно из вызова f32.load, наша g_importedFloat тоже указатель
    i32.const 0 ;; Компилятор предполагает, что указатель может быть с каким-то
    ;; смещением. Скорее всего, это связано с выравниванием в памяти,
    ;; которое для float не нужно.
    get_global 1
    i32.add
    f32.load
    return)
  (memory (;0;) 1)
  (export "memory" (memory 0))
  (export "get_imported_by_ptr" (func 1))
  (export "get_imported_by_value" (func 2))
  (export "get_internal_by_ptr" (func 3))
  (export "get_internal_by_value" (func 4))
  ;; Здесь можно посмотреть, как наша g_internalStruct лежит в памяти
  (data (i32.const 16) "\ff\00\fe\ff\fd\ff\ff\ff\fc\ff\ff\ff\00\00\00\00\fb\ff\ff\ff\ff\ff\ff\ff\01\00\02\00\03\00\00\00\04\00\00\00\00\00\00\00\05\00\00\00\00\00\00\00\00\00\f6B\00\00\00\00\00\00\00\00\00\00\14@\80\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00\00")
  ;; И отдельно от неё лежит строковый литерал, который в структуре
  ;; определён как указатель
  (data (i32.const 128) "StringValue\00"))

Общение с хостом


Высшая формой организации WebAssembly — модуль. WebAssembly распространяется, загружается и исполняется в виде модулей.


Всего у нас набралось 4 типа объектов в WebAssembly: функции, память, таблицы и глобальные переменные. Каждый из этих объектов может быть импортирован и экспортирован (и даже одновременно импортирован и экспортирован).


Модуль содержит все определённые в нём объекты, и описывает структуру импортов и экспортов. Как можно было заметить, все объекты (и ещё сигнатуры, которые type) имеют свои порядковые номера. Пространство номеров у каждого типа своё. То есть, функция 2 не имеет никакого отношения ни к глобальной переменной 2, ни к сигнатуре 2. Пространство номеров обычно начинается с импортированных объектов.


С точки зрения кода, вызов функции хоста или получение глобальной переменной хоста не отличаются от обычных: так же call N или get_global N. Интерпретатор на основе метаданных модуля сам определит, нужно ли вызвать функцию хоста, или даже функцию другого модуля, этим хостом загруженного.


С памятью и таблицами всё сложнее. При совместном использовании несколькими модулями одной памяти или одной таблицы нужно определиться с регионами, в которых каждый из модулей хранит свои глобальные данные. По этому поводу есть рекомендация, но пока она слабо поддерживается компиляторами.


В итоге, для общения между модулем и хостом:


  • Хост может определять и изменять глобальные переменные, импортируемые модулем
  • Хост может вызывать экспортируемые функции из модуля, а модуль — импортировать и вызывать функции хоста
  • Хост может записывать данные в память и таблицы модуля, и читать из них же

Заключение


С основными внутренностями я закончил. Практически к каждому пункту можно написать огромный список дополнений и особенностей компиляции, но это уже частные случаи. Как видно, хоть технология и называется WebAssembly, внутри к вебу никаких привязок нет.


Для компиляции и декомпиляции примеров использовался пакет WABT и LLVM 5.0. Emscripten я не использую, ибо он, как раз, создаёт кучу всего, предназначенного исключительно для веб-модулей, запускаемых совместно с JavaScript.


Далее будем рассуждать, чего нужно в стандартной библиотеке, как распределять память, и как запускать весь этот бедлам на мобильных платформах.


P.S. Хотелось написать нечто для фронтэндеров, которые хотят разобраться с сей технологией. Не уверен, что получилось. Если вы — фронтендер, и вам что-то не понятно — пишите в комментарии смело, буду исправляться.




К сожалению, не доступен сервер mySQL