Project: https://github.com/Spxg/rwat

We are working on js-bindgen, the next experimental version of wasm-bindgen under its current name. It needs to use inline assembly. However, Rust inline assembly on wasm is not stable yet. If we used it directly, js-bindgen would have to require a nightly toolchain, which is not acceptable.

Inline assembly stabilization still looks like it will take some time¹. Broadly speaking, the current inline assembly uses LLVM’s .s text format. It has no formal standard and may still lack testing. In contrast, wasm has an officially standardized .wat text format, but the specification and standard toolchain support for relocatable text are still incomplete.

The good news is that someone has already proposed a corresponding text format proposal, and there is even an implementation. But standardization takes time. Since the main blocker for js-bindgen is related to inline assembly, I decided to implement a relocatable wat text format for it. That is rwat, the project introduced in this article.

What is relocation?

Let us first introduce what relocation does. Consider this C code, where foo calls an external function add:

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

We compile it with clang and inspect the symbol information:

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

As shown above, add is an undefined symbol. Its symbol address is still unknown, so it needs to be relocated. Let us look at its wat form and confirm what the call instruction is calling:

$ 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")
)

We can see that it calls immediate value 0². Now we implement add, link them together, and see what the call target becomes:

// 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
  )
)

Now the immediate value of call has become 1.

This is one kind of relocation. Its type is R_WASM_FUNCTION_INDEX_LEB. In short, it writes a symbol address that can only be determined at link time into the place that needs relocation.

How is relocation information stored?

So where is relocation information stored? In the foo.o from the previous section, we saw two custom sections:

(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")
)

Yes, relocation information is stored in the linking section and the corresponding reloc.* section for each section. A wasm object file is still a standard wasm file; the important feature is that it has a linking section³.

For R_WASM_FUNCTION_INDEX_LEB, the linking section stores the symbol table of the object file. The symbol that needs relocation is recorded in the reloc.CODE section, together with its index in the symbol table and the offset of the immediate value that needs to be rewritten. Let us inspect foo.o with wasm-objdump:

$ 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>

We can see that the index of add in the symbol table is 1. There are two immediate offsets: one is 0x8 relative to the CODE section, and the other is 0x53 relative to the whole file. We can verify this with tools:

$ 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                                    |.....|

The results are the same. But wait, why is this value 0x80 instead of the 0 we expected? It turns out that the value is encoded as a 5-byte LEB⁴, where 0 is 0x80 0x80 0x80 0x80 0x00. The reason for this design is that we cannot know the immediate value before relocation, so the largest 5-byte LEB is reserved. This way, the linker does not need to rearrange the following bytes when rewriting it.

Design

Let us rewrite foo.c in wat and convert it to 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

Clearly, the generated file is not an object file. It has been treated as an ordinary wat file⁵. However, the wat format supports custom annotations. We can use annotations to attach information to specific symbols and instructions, parse those annotations to generate relocation information, and then add the linking section and the corresponding reloc.* sections. The proposal mentioned above adds two annotations, @sym and @reloc. We can follow the same idea: add the symbol information marked by the former to the linking section, and add the relocation information marked by the latter to the reloc.* section, like this:

;; 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)
  )
)

To implement this, we need several libraries from the wasm-tools project⁶: wast, wasmparser, and wasm-encoder. We will use the foo.wat above as the example when introducing the design.

Parsing annotations

First, we use wast to parse annotations. We add a module annotation, @rwat; only wat files using this annotation will be processed by rwat, which keeps the complexity down:

(module (@rwat))

Then we define a RelocWat, traverse all funcs and their instructions, and collect the presence of @sym and @reloc annotations:

#[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 will be collected like this:

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

Then we use the official parser to convert wat into wasm. The official parser skips unsupported annotations. We then zip it together with the reloc information we collected and compare the two. This gives us the symbol name and the corresponding funcidx, and also tells us where it is in the symbol table:

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

At this point, the information required by the linking section has been collected. Now we need to think about how to get the information required by the reloc.CODE section.

Patching relocations

R_WASM_FUNCTION_INDEX_LEB relocation needs two pieces of information: the offset of the immediate relative to the CODE section, and the position of the call target symbol in the symbol table.

Consider our example, call $add (@reloc). When we traverse to it, we can get the funcidx of its target symbol. With that, combined with the symmap from the previous step, we know the target symbol’s position in the symbol table. So the only remaining problem is the offset. This is where we use the second tool, wasmparser.

The CODE section consists of FunctionBody values. This means we can use get_operators_reader to traverse the instructions of a func and obtain the absolute offset of each instruction. After encountering call $add (@reloc), we first get the absolute instruction offset, instr_offset. Since the length of the call instruction is 1, the offset of the immediate is immediate_start = instr_offset + 1 - CODE_OFFSET.

It looks like we now have all the information. Can we generate the reloc.CODE section? The answer is no. As mentioned in the earlier sections, the place that needs relocation must be encoded as a 5-byte LEB. This is the most troublesome part, because we have to rearrange the FunctionBody and adjust offsets.

To make the calculation easier, we first convert the immediate offset to an immediate_start relative to the function body, and then calculate the length of the original immediate, immediate_length. For a function body[], we create a new patched_body[] and copy bytes as follows:

// 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..]);

In practice, we also need to calculate the resulting shift = 5 - immediate_length, because a single function may contain multiple places that need relocation. I will not expand on that here.

Finally, we need to assemble the CODE section. Its layout is:

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

One thing to note is that the immediate_start offset relative to the function body also needs to include leb(size(func_body)).

After this, we can finally generate the linking and reloc.CODE sections.

Generating relocation sections

After obtaining the symtable, symmap, patched_body, the funcidx of the relocation target function, and its offset from the flow above, we can use wasm-encoder to generate the relocation sections. One important detail is that these sections must be written in order:

1. The linking section must appear after the data section: Linking.md#L252
2. The reloc.* sections must appear after the linking section: Linking.md#L62

After completing these steps, we have generated a wasm object file.

Summary

rwat implements relocation of the R_WASM_FUNCTION_INDEX_LEB and R_WASM_TABLE_NUMBER_LEB types. It is both a library and a binary. Interestingly, you can also use it as a simple compiler:

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

Wishlist

1. I hope rwat can help move the related proposal forward.
2. I hope relocation can be implemented in wast, which would save a lot of work.