Noz Wu

Introducing rwat

项目地址：https://github.com/Spxg/rwat

我们在开发 wasm-bindgen 的下一个实验性版本 js-bindgen（目前叫这个名字），它需要使用内联汇编。但目前 Rust 在 wasm 平台上的内联汇编还没稳定，如果使用它，js-bindgen 只能使用 nightly 工具链，这是不能接受的。

内联汇编稳定看起来还需要一些时间1，总的来说，现在内联汇编使用了 LLVM 的 .s 文本格式，它没有正式的标准，可能还缺乏测试；相比之下，wasm 有官方标准的 .wat 文本格式，但可重定位的文本规范和标准工具链支持还不完整。

好消息是已经有人提出了对应的文本格式提案，甚至已经有实现了。但是标准化需要时间，考虑到 js-bindgen 的主要阻碍就是内联汇编相关，我决定实现一个可重定位的 wat 文本格式供它使用，也就是这篇文章要介绍的 rwat。

什么是重定位

我们先介绍一下重定位是做什么的。考虑这个 C 代码，其中 foo 调用了一个外部函数 add：

// foo.c
extern int add(int, int);
int foo(int x, int y) {
    return add(x, y);
}

我们使用 clang 编译它并看看符号信息：

$ clang -c foo.c -target wasm32-unknown-unknown -o foo.o -O3
$ llvm-nm foo.o
         U add
00000001 T foo

可以看到 add 是一个未定义的符号，它的符号地址还是未知的，需要被重定位。我们看看它的 wat 形式，确认一下 call 指令调用的是什么：

$ wasm-tools print foo.o
(module
  (type (;0;) (func (param i32 i32) (result i32)))
  (import "env" "__linear_memory" (memory (;0;) 0))
  (import "env" "add" (func (;0;) (type 0)))
  (func (;1;) (type 0) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    call 0
  )
  (@custom "linking" (after code) "\02\08\8b\80\80\80\00\02\00\04\01\03foo\00\10\00")
  (@custom "reloc.CODE" (after code) "\03\01\00\08\01")
)

可以看到它调用了立即数 02。现在我们实现一下 add，然后将它们链接到一起，并看看此时 call 的目标是什么：

// add.c
int add(int x, int y) {
    return x + y;
}
$ clang foo.c add.c -target wasm32-unknown-unknown -O3 -nostdlib -Wl,--no-entry,--export=foo,--strip-all -o foo.wasm
$ wasm-tools print foo.wasm
(module
  (type (;0;) (func (param i32 i32) (result i32)))
  (memory (;0;) 1)
  (global (;0;) (mut i32) i32.const 65536)
  (export "memory" (memory 0))
  (export "foo" (func 0))
  (func (;0;) (type 0) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    call 1
  )
  (func (;1;) (type 0) (param i32 i32) (result i32)
    local.get 1
    local.get 0
    i32.add
  )
)

可以看到，现在 call 的立即数变成了 1。

这就是一种重定位，它的类型是 R_WASM_FUNCTION_INDEX_LEB，简单来说就是将一个需要在链接时确定的符号地址写入到需要重定位的地方。

重定位信息是怎么存储的

那么重定位信息被存储到哪里呢？在上一节的 foo.o 出现了两个自定义段：

(module
  ;; ...
  (@custom "linking" (after code) "\02\08\8b\80\80\80\00\02\00\04\01\03foo\00\10\00")
  (@custom "reloc.CODE" (after code) "\03\01\00\08\01")
)

是的，重定位信息就存储在 linking 段和对应 section 的 reloc.* 段中。实际上 wasm 目标文件也是一个标准的 wasm，重要特征就是它存在 linking 段3。

对于 R_WASM_FUNCTION_INDEX_LEB 来说，linking 段会存储该目标文件的符号表，需要重定位的符号会在 reloc.CODE 段中记录它在符号表的索引，以及需要改写的立即数偏移量。我们用 wasm-objdump 看看 foo.o：

$ wasm-objdump -x foo.o -j linking
Custom:
 - name: "linking"
  - symbol table [count=2]
   - 0: F <foo> func=1 [ binding=global vis=hidden ]
   - 1: F <env.add> func=0 [ undefined binding=global vis=default ]
$ wasm-objdump -x foo.o -j reloc.CODE
Custom:
 - name: "reloc.CODE"
  - relocations for section: 3 (Code) [1]
   - R_WASM_FUNCTION_INDEX_LEB offset=0x000008(file=0x000053) symbol=1 <env.add>

可以看到 add 在符号表里的索引是 1；立即数偏移量有两个，一个是相对于 CODE 段的 0x8，一个是相对于整个文件的 0x53。我们可以用工具进行验证：

$ hexdump -C foo.o -s 0x53 -n 5
00000053  80 80 80 80 00                                    |.....|
$ wasm-objdump -h foo.o
....
     Code start=0x0000004b end=0x00000059 (size=0x0000000e) count: 1
....
$ hexdump -C foo.o -s $((0x4b + 0x8)) -n 5
00000053  80 80 80 80 00                                    |.....|

可以看到它们的结果都是一样的。但是等等，为什么这个值是 0x80 而不是我们期望的 0？原来这个值被编码成了 5 字节的 LEB4，0 也就是 0x80 0x80 0x80 0x80 0x00。这么设计是因为我们没有办法在重定位前确认这个立即数的值，所以需要预留最大的 5 字节 LEB，这样链接器在重写时就不需要重新排列后面的字节。

方案设计

我们用 wat 重写一下 foo.c 并转成 wasm，看看是什么样子的：

;; foo.wat
(module
  (import "env" "add" (func $add (param i32 i32) (result i32)))
  (func $foo (param i32 i32) (result i32)
    local.get 0
    local.get 1
    call $add
  )
)
$ wasm-tools parse foo.wat > foo.o
$ wasm-objdump -x foo.o -j linking
Section not found: linking
$ wasm-objdump -x foo.o -j reloc.CODE
Section not found: reloc.CODE

很显然，生成的文件并不是一个目标文件，它被当作普通的 wat 处理了5。不过 wat 格式支持添加自定义注解，我们可以通过注解给特定的符号和指令添加信息，再解析它们生成重定位信息，并添加 linking 和相应的 reloc.* 段。上面提到的提案中添加了 @sym 和 @reloc 这两个注解，我们可以效仿一下，将前者所标注的符号信息加到 linking 段中，后者标注的重定位信息加到 reloc.* 段中，就像这样：

;; foo.wat
(module
  (import "env" "add" (func $add (@sym) (param i32 i32) (result i32)))
  (func $foo (@sym) (param i32 i32) (result i32)
    local.get 0
    local.get 1
    call $add (@reloc)
  )
)

为了实现它们，我们需要使用一些库，这些库都来自 wasm-tools 项目6，分别是 wast、wasmparser、wasm-encoder。我们以上面的 foo.wat 为例子来介绍方案。

解析注解

我们首先使用 wast 解析注解，先添加一个 module 注解 @rwat，只有使用了这个注解的 wat 才会被 rwat 处理，以减少复杂度：

(module (@rwat))

然后我们定义一个 RelocWat，遍历所有 func 和它们的指令，收集 @sym 和 @reloc 注解的存在情况：

#[derive(Debug, Default)]
pub(crate) struct RelocWat<'a> {
    pub(crate) import_annotations: Vec<RelocImports<'a>>,
    pub(crate) func_annotations: Vec<FuncAnnotation<'a>>,
}

#[derive(Debug)]
pub(crate) struct RelocImports<'a> {
    pub(crate) syms: Vec<SymbolAnnotation<'a>>,
}

#[derive(Debug)]
pub(crate) struct FuncAnnotation<'a> {
    pub(crate) sym: SymbolAnnotation<'a>,
    pub(crate) reloc_spans: Vec<Span>,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum SymbolAnnotation<'a> {
    Missing,
    Inferred,
}

foo.wat 将会被收集成这样：

RelocWat {
  import_annotations: [RelocImports { syms: [SymbolAnnotation::Inferred] }],
  func_annotations: [FuncAnnotation { sym: SymbolAnnotation::Inferred, reloc_spans: [Instr3]}]
}

然后我们使用官方的 parser 将 wat 转化成 wasm（官方的 parser 遇到不支持的注解会跳过），再与我们收集的 reloc 信息 zip 到一起对照，就可以得到它的符号名和对应的 funcidx，同时也知道了它在符号表的位置：

symtable: [
  Symbol::FunctionImport { index: 0, symbol_name: "env.add" }
  Symbol::FunctionDefined { index: 1, symbol_name: "foo" }
]
symmap<funcidx, symbol_idx>: [(0, 0), (1, 1)]

到这里，linking 段所需要的信息已经收集到了。现在思考如何拿到 reloc.CODE 段所需要的信息。

重定位打补丁

R_WASM_FUNCTION_INDEX_LEB 类型的重定位需要两个信息，一个是立即数相对于 CODE 段的偏移量，另一个是调用目标符号在符号表的位置。

考虑我们的例子 call $add (@reloc)，我们遍历到它时，可以获取到它的目标符号的 funcidx。有了它，再结合上一步得出的 symmap，就能知道目标符号在符号表的位置。所以现在问题只剩偏移量了，这里我们使用第二个工具 wasmparser。

CODE 段是由各个 FunctionBody 组成的，这意味着我们可以使用 get_operators_reader 遍历 func 的指令，并获得指令的绝对偏移量。遇到 call $add (@reloc) 后，我们首先拿到指令的绝对偏移量 instr_offset。因为 call 的指令长度是 1，所以立即数的偏移量是 immediate_start = instr_offset + 1 - CODE_OFFSET。

看起来一切信息都有了，那我们可以生成 reloc.CODE 段了吗？答案是否定的。在前几个章节我们提到过，需要重定位的地方会被编码成 5 字节 LEB。这是最麻烦的地方，因为我们不得不重新排列 FunctionBody，并校准偏移量。

为了便于计算，我们先将立即数偏移量换算成相对于函数体的 immediate_start，然后计算出原有立即数的长度 immediate_length。对于一个函数 body[]，我们新建一个 patched_body[]，然后按照如下操作完成拷贝：

// Each relocated immediate is rewritten as a 5-byte LEB128 value, growing by at most 4 bytes.
let mut patched_body = Vec::with_capacity(body.as_bytes().len() + 4);
patched_body.extend_from_slice(&body.as_bytes()[..immediate_start]);
patched_body.extend_from_slice(encode_5_byte_u32_leb(funcidx));
patched_body.extend_from_slice(&body.as_bytes()[immediate_start + immediate_length..]);

实际上我们还需要计算它产生的 shift = 5 - immediate_length，因为一个函数内可能有多个地方需要重定位，这里就不做展开了。

最后我们需要组装 CODE 段，布局如下：

[funcs_count][leb(size(func_body))][func_body]...

需要注意的是，我们相对于函数体的 immediate_start 偏移量还需要加上 leb(size(func_body))。

完成这些后我们终于可以进行 linking 和 reloc.CODE 段的生成了。

生成重定位段

拿到上述流程产生的 symtable、symmap、patched_body、重定位目标函数的 funcidx 以及它的 offset 后，我们就可以使用 wasm-encoder 生成重定位段了。需要注意的是，这些 section 的写入顺序有要求：

  1. linking 段必须在 data 段后：Linking.md#L252
  2. reloc.* 段必须在 linking 段后：Linking.md#L62

完成这些，我们就生成了 wasm 目标文件。

总结

rwat 实现了 R_WASM_FUNCTION_INDEX_LEB 和 R_WASM_TABLE_NUMBER_LEB 类型的重定位，它既是 library 也是 binary，有趣的是你可以将它当作简单的编译器使用：

cargo install rwat --locked
rwat examples/main.wat examples/add.wat -o main.wasm -Wl,--no-entry,--export=main

愿望清单

  1. 希望 rwat 能够推动相关提案。
  2. 希望能在 wast 中实现重定位，这能省下很多工作。

  1. Moving WebAssembly inline assembly forward ↩︎

  2. 这个立即数是 funcidx，并不固定为 0 ↩︎

  3. Linking.md#L16 ↩︎

  4. Linking.md#L84 ↩︎

  5. 目前可以通过 wat2wasm --relocatable 将一个 wat 转化成一个可重定位的目标文件 ↩︎

  6. wasm-tools ↩︎

#wasm #wat

Reply to this post by email ↪