Pull to refresh

Компиляция C в WebAssembly без Emscripten

Reading time 11 min
Views 12K
Original author: Das Surma
Компилятор — часть Emscripten. А что, если удалить все свистелки и оставить только его?

Emscripten необходим для компиляции C/C++ в WebAssembly. Но это гораздо больше, чем просто компилятор. Цель Emscripten в том, чтобы полностью заменить ваш компилятор C/C++ и запустить в вебе код, который изначально не предназначен для Сети. Для этого Emscripten эмулирует всю операционную систему POSIX. Если программа использует fopen(), то Emscripten предоставит эмуляцию файловой системы. Если используется OpenGL, то Emscripten предоставит С-совместимый контекст GL, поддерживаемый WebGL. Это немалая работа, и немало кода, который придётся внедрить в итоговый пакет. Но можно ли просто… удалить его?

Собственно компилятором в наборе инструментов Emscripten является LLVM. Именно он переводит код C в байт-код WebAssembly. Это современный модульный фреймворк для анализа, трансформации и оптимизации программ. LLVM модульный в том смысле, что он никогда не компилирует прямо в машинный код. Вместо этого встроенный фронтенд-компилятор генерирует промежуточное представление (IR). Это промежуточное представление, собственно, и называется LLVM, аббревиатура от Low-Level Virtual Machine, отсюда и название проекта.

Затем бэкенд-компилятор выполняет перевод IR в машинный код хоста. Преимущество такого строгого разделения заключается в том, что новые архитектуры поддерживаются «простым» добавлением нового компилятора. В этом смысле WebAssembly — лишь одна из многих целей компиляции, которые поддерживает LLVM, и в течение некоторого времени он активировался специальным флагом. Начиная с LLVM 8 цель компиляции WebAssembly доступна по умолчанию.

На MacOS вы можете установить LLVM с помощью homebrew:

$ brew install llvm
$ brew link --force llvm

Проверяем поддержку WebAssembly:

$ llc --version
LLVM (http://llvm.org/):
  LLVM version 8.0.0
  Optimized build.
  Default target: x86_64-apple-darwin18.5.0
  Host CPU: skylake

  Registered Targets:
    # …Господи, сколько архитектур…
    systemz    - SystemZ
    thumb      - Thumb
    thumbeb    - Thumb (big endian)
    wasm32     - WebAssembly 32-bit # Ура! Ура! Ура!
    wasm64     - WebAssembly 64-bit
    x86        - 32-bit X86: Pentium-Pro and above
    x86-64     - 64-bit X86: EM64T and AMD64
    xcore      - XCore

Кажется, мы готовы!

Компиляция C трудным путём


Примечание: здесь рассмотрим некоторые низкоуровневые форматы RAW WebAssembly. Если вам их трудно понять, это нормально. Хорошее использование WebAssembly не требует обязательного понимания всего текста в этой статье. Если ищете код для копипаста, см. вызов компилятора в разделе «Оптимизация». Но если вам интересно, продолжайте читать! Ранее я написал введение в чистый Webassembly и WAT: это основы, необходимые для понимания этого поста.
Предупреждение: я немного отклонюсь от стандарта и на каждом шаге постараюсь использовать удобочитаемые форматы (насколько это возможно). Наша программа здесь будет очень простой, чтобы избежать пограничных ситуаций и не отвлекаться:

// Filename: add.c
int add(int a, int b) {
  return a*a + b;
}

Какой умопомрачительный инженерный подвиг! Особенно потому что программа называется add, а на самом деле она ничего не add (не добавляет). Что более важно: программа не использует стандартную библиотеку, а из типов здесь только 'int'.

Превращаем C во внутреннее представление LLVM


Первый шаг — превратить нашу программу C в LLVM IR. Это задача фронтенд-компилятора clang, который установился с LLVM:

clang \
  --target=wasm32 \ # Target WebAssembly
  -emit-llvm \ # Emit LLVM IR (instead of host machine code)
  -c \ # Only compile, no linking just yet
  -S \ # Emit human-readable assembly rather than binary
  add.c

И в результате мы получаем add.ll с внутренним представлением LLVM IR. Я показываю его только ради полноты картины. При работе с WebAssembly или даже clang вы как разработчик на C никогда не вступаете в контакт с LLVM IR.

; ModuleID = 'add.c'
source_filename = "add.c"
target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
target triple = "wasm32"

; Function Attrs: norecurse nounwind readnone
define hidden i32 @add(i32, i32) local_unnamed_addr #0 {
  %3 = mul nsw i32 %0, %0
  %4 = add nsw i32 %3, %1
  ret i32 %4
}

attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 8.0.0 (tags/RELEASE_800/final)"}

LLVM IR полна дополнительных метаданных и аннотаций, что позволяет компилятору принимать более обоснованные решения при генерации машинного кода.

Превращаем LLVM IR в объектные файлы


Следующий шаг — вызов бэкенд-компилятора llc, чтобы сделать из внутреннего представления объектный файл.

Выходной файл add.o — это уже валидный модуль WebAssembly, который содержит весь скомпилированный код нашего файла C. Но обычно вы не сможете запустить объектные файлы, поскольку в них отсутствуют существенные части.

Если бы в команде мы опустили -filetype=obj, то получили бы ассемблер LLVM для WebAssembly, человекочитаемый формат, который в чём-то похож на WAT. Однако инструмент llvm-mc для работы с такими файлами ещё не полностью поддерживает формат и часто не может обработать файлы. Поэтому дизассемблируем объектные файлы постфактум. Для проверки этих объектных файлов нужен специфический инструмент. В случае WebAssembly это wasm-objdump, часть WebAssembly Binary Toolkit или wabt для краткости.

$ brew install wabt # in case you haven’t
$ wasm-objdump -x add.o

add.o:  file format wasm 0x1

Section Details:

Type[1]:
 - type[0] (i32, i32) -> i32
Import[3]:
 - memory[0] pages: initial=0 <- env.__linear_memory
 - table[0] elem_type=funcref init=0 max=0 <- env.__indirect_function_table
 - global[0] i32 mutable=1 <- env.__stack_pointer
Function[1]:
 - func[0] sig=0 <add>
Code[1]:
 - func[0] size=75 <add>
Custom:
 - name: "linking"
  - symbol table [count=2]
   - 0: F <add> func=0 binding=global vis=hidden
   - 1: G <env.__stack_pointer> global=0 undefined binding=global vis=default
Custom:
 - name: "reloc.CODE"
  - relocations for section: 3 (Code) [1]
R_WASM_GLOBAL_INDEX_LEB offset=0x000006(file=0x000080) symbol=1 <env.__stack_pointer>

Выдача показывает, что наша функция add() находится в этом модуле, но она также содержит разделы custom с метаданными и, что удивительно, несколько импортов. На следующем этапе компоновки разделы custom будут проанализированы и удалены, а с импортом разберётся компоновщик (линкер).

Компоновка


Традиционно задачей компоновщика является сборка нескольких объектных файлов в исполняемый файл. Компоновщик LLVM называется lld, и он вызывается с указанием целевой символической ссылки. Для WebAssembly это wasm-ld.

wasm-ld \
  --no-entry \ # We don’t have an entry function
  --export-all \ # Export everything (for now)
  -o add.wasm \
  add.o

В результате получается модуль WebAssembly размером 262 байта.

Запуск


Конечно, самое главное — увидеть, что всё действительно работает. Как и в прошлой статье, можно использовать пару строк встроенного JavaScript для загрузки и запуска этого модуля WebAssembly.

<!DOCTYPE html>

<script type="module">
  async function init() {
    const { instance } = await WebAssembly.instantiateStreaming(
      fetch("./add.wasm")
    );
    console.log(instance.exports.add(4, 1));
  }
  init();
</script>

Если всё нормально, вы увидите в консоли DevTool число 17. Мы только что успешно скомпилировали C в WebAssembly, не трогая Emscripten. Также стоит отметить, что здесь нет никакого связующего кода для настройки и загрузки модуля WebAssembly.

Компиляция C немного попроще


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

clang \
  --target=wasm32 \
  -nostdlib \ # Don’t try and link against a standard library
  -Wl,--no-entry \ # Flags passed to the linker
  -Wl,--export-all \
  -o add.wasm \
  add.c

Здесь мы получаем такой же файл .wasm, но одной командой.

Оптимизация


Посмотрим на WAT нашего модуля WebAssembly, запустив wasm2wat:

(module
  (type (;0;) (func))
  (type (;1;) (func (param i32 i32) (result i32)))
  (func $__wasm_call_ctors (type 0))
  (func $add (type 1) (param i32 i32) (result i32)
    (local i32 i32 i32 i32 i32 i32 i32 i32)
    global.get 0
    local.set 2
    i32.const 16
    local.set 3
    local.get 2
    local.get 3
    i32.sub
    local.set 4
    local.get 4
    local.get 0
    i32.store offset=12
    local.get 4
    local.get 1
    i32.store offset=8
    local.get 4
    i32.load offset=12
    local.set 5
    local.get 4
    i32.load offset=12
    local.set 6
    local.get 5
    local.get 6
    i32.mul
    local.set 7
    local.get 4
    i32.load offset=8
    local.set 8
    local.get 7
    local.get 8
    i32.add
    local.set 9
    local.get 9
    return)
  (table (;0;) 1 1 anyfunc)
  (memory (;0;) 2)
  (global (;0;) (mut i32) (i32.const 66560))
  (global (;1;) i32 (i32.const 66560))
  (global (;2;) i32 (i32.const 1024))
  (global (;3;) i32 (i32.const 1024))
  (export "memory" (memory 0))
  (export "__wasm_call_ctors" (func $__wasm_call_ctors))
  (export "__heap_base" (global 1))
  (export "__data_end" (global 2))
  (export "__dso_handle" (global 3))
  (export "add" (func $add)))

Ничего себе, какой большой код. К моему удивлению, модуль использует память (что видно по операциям i32.load и i32.store), восемь локальных и несколько глобальных переменных. Вероятно, вручную можно написать более лаконичную версию. Эта программа такая большая, потому что мы не применили никаких оптимизаций. Давай сделаем это:

clang \
   --target=wasm32 \
+  -O3 \ # Agressive optimizations
+  -flto \ # Add metadata for link-time optimizations
   -nostdlib \
   -Wl,--no-entry \
   -Wl,--export-all \
+  -Wl,--lto-O3 \ # Aggressive link-time optimizations
   -o add.wasm \
   add.c

Примечание: технически, оптимизация при компоновке (LTO) не даёт никаких преимуществ, поскольку мы компонуем только один файл. В больших проектах LTO поможет заметно уменьшить размер файла.
После выполнения этих команд файл .wasm уменьшился с 262 до 197 байт, а WAT тоже стал намного проще:

(module
  (type (;0;) (func))
  (type (;1;) (func (param i32 i32) (result i32)))
  (func $__wasm_call_ctors (type 0))
  (func $add (type 1) (param i32 i32) (result i32)
    local.get 0
    local.get 0
    i32.mul
    local.get 1
    i32.add)
  (table (;0;) 1 1 anyfunc)
  (memory (;0;) 2)
  (global (;0;) (mut i32) (i32.const 66560))
  (global (;1;) i32 (i32.const 66560))
  (global (;2;) i32 (i32.const 1024))
  (global (;3;) i32 (i32.const 1024))
  (export "memory" (memory 0))
  (export "__wasm_call_ctors" (func $__wasm_call_ctors))
  (export "__heap_base" (global 1))
  (export "__data_end" (global 2))
  (export "__dso_handle" (global 3))
  (export "add" (func $add)))

Вызов стандартной библиотеки


Использование C без стандартной библиотеки libc кажется довольно грубым. Логично добавить её, но буду честен: это не будет легко. На самом деле мы напрямую не вызываем в статье никаких библиотек libc. Есть несколько подходящих, особенно glibc, musl и dietlibc. Однако большинство этих библиотек предполагается запускать в операционной системе POSIX, которая реализует определённый набор системных вызовов. Поскольку у нас в JavaScript нет интерфейса ядра, нам придётся самостоятельно реализовать эти системные вызовы POSIX, вероятно, через JavaScript. Это сложная задача и я не собираюсь этим тут заниматься. Хорошая новость в том, что именно этим для вас занимается Emscripten.

Конечно, не все функции libc полагаются на системные вызовы. Такие функции, как strlen(), sin() или даже memset(), реализованы в простом C. Это означает, что вы можете использовать эти функции или даже просто скопировать/вставить их реализацию из какой-нибудь упомянутой библиотеки.

Динамическая память


Без libc нам недоступны фундаментальные интерфейсы C, такие как malloc() и free(). В неоптимизированном WAT мы видели, что компилятор в случае необходимости использует память. Это означает, что мы не можем просто использовать память, как нам нравится, не рискуя её повредить. Нужно понять, как она используется.

Модели памяти LLVM


Способ сегментации памяти WebAssembly немного удивит опытных программистов. Во-первых, в WebAssembly технически допустим нулевой адрес, но часто он всё равно обрабатывается как ошибка. Во-вторых, стек приходит первым и увеличивается вниз (к более низким адресам), а куча появляется потом и растёт вверх. Причина в том, что память WebAssembly может увеличиться во время выполнения. Это означает, что нет фиксированного конца для размещения стека или кучи.

Вот макет wasm-ld:



Стек растёт вниз, а куча — вверх. Стек начинается с __data_end, а куча — с __heap_base. Потому что стек размещается первым, он ограничен максимальным размером, установленным при компиляции, то есть __heap_base минус __data_end

Если вернуться и посмотреть на раздел globals в нашем WAT, мы найдём эти значения: __heap_base установлен в 66560, а __data_end — в 1024. Это означает, что стек может вырасти максимум до 64 КиБ, что не много. К счастью, wasm-ld позволяет изменить это значение:

clang \
   --target=wasm32 \
   -O3 \
   -flto \
   -nostdlib \
   -Wl,--no-entry \
   -Wl,--export-all \
   -Wl,--lto-O3 \
+  -Wl,-z,stack-size=$[8 * 1024 * 1024] \ # Set maximum stack size to 8MiB
   -o add.wasm \
   add.c

Сборка аллокатора


Известно, что область кучи начинается с __heap_base. Поскольку функция malloc() отсутствует, мы знаем, что следующую область памяти можно спокойно использовать. Мы можем разместить там данные как угодно, и не нужно бояться повреждения памяти, поскольку стек растёт в другую сторону. Однако свободная для всех куча может быстро засориться, поэтому обычно требуется какое-то динамическое управление памятью. Один из вариантов — взять полноценную реализацию malloc(), такую как реализация malloc от Дага Ли, которая используется в Emscripten. Есть ещё несколько небольших реализаций с различными компромиссами.

Но почему бы не написать собственный malloc()? Мы так глубоко увязли, что это уже без разницы. Один из простейших — bump-аллокатор: он супербыстрый, чрезвычайно маленький и простой в реализации. Но есть и недостаток: вы не можете освободить память. Хотя на первый взгляд такой аллокатор кажется невероятно бесполезным, но при разработке Squoosh я столкнулся с прецедентами, где он стал бы отличным выбором. Концепция бамп-аллокатора заключается в том, что мы храним начальный адрес неиспользуемой памяти как глобальный. Если программа запрашивает n байт памяти, мы передвигаем маркер на n и возвращаем предыдущее значение:

extern unsigned char __heap_base;

unsigned int bump_pointer = &__heap_base;
void* malloc(int n) {
  unsigned int r = bump_pointer;
  bump_pointer += n;
  return (void *)r;
}

void free(void* p) {
  // lol
}

Глобальные переменные из WAT фактически определяются wasm-ld, так что мы можем получить к ним доступ из нашего кода C как к обычным переменным, если объявим их extern. Итак, мы только что написали собственный malloc()… в пяти строчках C.

Примечание: наш бамп-аллокатор не полностью совместим с malloc() из C. Например, мы не даём никаких гарантий выравнивания. Но он достаточно хорошо и работает, так что...

Использование динамической памяти


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

int sum(int a[], int len) {
  int sum = 0;
  for(int i = 0; i < len; i++) {
    sum += a[i];
  }
  return sum;
}

Функция sum(), надеюсь, довольно понятна. Более интересный вопрос заключается в том, как передать массив из JavaScript в WebAssembly — в конце концов, WebAssembly понимает только числа. Общая идея состоит в том, чтобы использовать malloc() из JavaScript, чтобы выделить кусок памяти, скопировать туда значения и передать адрес (число!) где находится массив:

<!DOCTYPE html>

<script type="module">
  async function init() {
    const { instance } = await WebAssembly.instantiateStreaming(
      fetch("./add.wasm")
    );

    const jsArray = [1, 2, 3, 4, 5];
    // Allocate memory for 5 32-bit integers
    // and return get starting address.
    const cArrayPointer = instance.exports.malloc(jsArray.length * 4);
    // Turn that sequence of 32-bit integers
    // into a Uint32Array, starting at that address.
    const cArray = new Uint32Array(
      instance.exports.memory.buffer,
      cArrayPointer,
      jsArray.length
    );
    // Copy the values from JS to C.
    cArray.set(jsArray);
    // Run the function, passing the starting address and length.
    console.log(instance.exports.sum(cArrayPointer, cArray.length));
  }
  init();
</script>

После запуска вы должны увидеть в консоли DevTools ответ 15, что действительно является суммой всех чисел от 1 до 5.

Заключение


Итак, вы дочитали до конца. Поздравляю! Опять же, если чувствуете себя немного перегруженным, всё в порядке. Не обязательно читать все детали. Их понимание совершенно необязательно для хорошего веб-разработчика и даже не требуется для отличного использования WebAssembly. Но я хотел поделиться этой информацией, потому что она позволяет действительно оценить всю работу, которую делает для вас такой проект, как Emscripten. В то же время это даёт понимание, насколько маленькими могут быть чисто вычислительные модули WebAssembly. Модуль Wasm для суммирования массива вместился всего в 230 байт, включая аллокатор динамической памяти. Компиляция того же кода с помощью Emscripten даст 100 байт кода WebAssembly и 11K связующего кода JavaScript. Нужно постараться ради такого результата, но бывают ситуации, когда оно того стоит.
Tags:
Hubs:
+26
Comments 5
Comments Comments 5

Articles