Who actually runs it?

A compiler never runs your program. It writes a file, and its responsibility ends there. What happens next depends on what kind of file it is: a native executable is handed to the operating system's loader; a .jar to the Java virtual machine; a .wasm module to a WebAssembly engine. This last chapter follows a Wahoo module from bytes on a disk to instructions executing on your processor.

§Programs are data

All of this rests on an idea from 1945. In his First Draft of a Report on the EDVAC, John von Neumann described a computer whose program is stored in the same memory as its data, as numbers. Before that, machines like ENIAC were programmed by rewiring them. Once a program is just data, one program can write another, which is exactly what a compiler does, and another can read it and act it out, which is what an interpreter does. Every chapter of this site is a consequence of that design.

For native code, the last steps are linking and loading. The linker joins the compiled pieces of a program and its libraries into one executable file (ELF on Linux, PE on Windows, Mach-O on macOS), patching the addresses each piece uses to refer to the others. When you start the program, the operating system's loader maps the file into memory, connects it to shared libraries, and jumps to its first instruction.

§WebAssembly

For two decades the only language browsers could run was JavaScript. In 2013 Mozilla's Alon Zakai and Luke Wagner showed with asm.js that a strict, statically typable subset of JavaScript, produced by compiling C and C++, could be optimised ahead of time to near-native speed. The lesson led the four major browser vendors to design a proper format together: WebAssembly was announced in 2015, shipped in every major browser in 2017 and became a W3C Recommendation in December 2019. Its goals fit in a sentence: fast to load, fast to run, safe to run code from anywhere, and independent of any processor or language. Today it is also used outside the browser, in servers, plug-in systems and edge networks.

WebAssembly is not a language you are meant to write (though its text form, WAT, is readable, as earlier chapters showed). It is a compilation target: C, C++, Rust, Go, Zig, Kotlin, and now Wahoo compile to it.

§Anatomy of a module

A .wasm file starts with eight bytes: the “magic number” 00 61 73 6D, which spells \0asm, and the version, 1. Then come sections, each introduced by an identifier byte and its size: the function types, the imports the host must provide, which type each defined function has, the memory, the exports, the code of every function body, and the data to place in memory. Custom sections can be added anywhere; Wahoo adds the standard name section, so that tools and error messages can show $fib instead of “function 4”.

Every number in the format is written in LEB128, a variable-length encoding: seven bits per byte, low bits first, the top bit of each byte saying whether another byte follows. Small numbers, which are the vast majority (local indices, small constants, short lengths), take a single byte. The number 624 485, for example, is E5 8E 26.

§Validation: a type checker for machine code

Before running a single instruction, the engine validates the whole module, and rejects it if anything is wrong. Validation is type checking at the lowest level: every instruction has a known effect on the stack (i32.add pops two i32 and pushes one), every block declares what it leaves behind, every branch target must exist, every function index must be in range. Because control flow is structured (chapter 04), all of this takes one linear pass over the code. That is why Wahoo's code generator had to add an unreachable after a question whose branches both return: the validator does not take the compiler's word for it.

§The sandbox

A web page can run a module written by anyone, so WebAssembly is designed to make the worst case harmless. A module can only touch its own linear memory, and every access is checked against its size (engines make this nearly free by reserving a huge region of virtual address space and letting the processor's memory protection catch stray accesses). It cannot jump to an arbitrary address: calls go to known functions and branches to known blocks. The call stack, with its return addresses, lives outside the module's memory where the module cannot overwrite it. And it can reach the outside world only through its imports. A Wahoo program has exactly four: it can print a number, a switch, a text and a line break, and nothing else.

§From WebAssembly to the processor

The module is still not machine code. The browser compiles it, once more, for the processor it runs on, using the same trade-off between speed of compilation and speed of the result that chapter 00 described. V8, Chrome's engine, first compiles every function with Liftoff, a baseline compiler that translates in a single pass, so the module can start running almost immediately. Functions that turn out to be hot are recompiled in the background by TurboFan, the optimising compiler (the same one that optimises JavaScript), and swapped in. Firefox and Safari follow a similar tiered design.

Not every host compiles. The wahoo command-line tool runs modules with wasmi, an interpreter for WebAssembly written in Rust: it validates the module and then executes it through its own internal bytecode. The same .wasm file is interpreted on the command line and compiled to machine code in the browser. It is chapter 00's lesson, one last time: being compiled or interpreted is a property of the implementation.

§When things go wrong at run time

Some failures can only be discovered while running. When a WebAssembly instruction cannot do its job, it traps: execution stops at once and the host receives an error. Wahoo programs can trap in three ways, each reported in character:

• Division by zero (i32.div_s with a zero divisor): “You fell into a pit”.
• Overflowing division: -2147483648 / -1 would be 2147483648, which does not fit in 32 bits.
• Stack overflow: too many nested calls, usually a recursion without an exit: “Too many pipes deep”.

A loop that never ends does not trap; it simply never stops, and by the halting problem no checker can always tell beforehand. The two hosts handle it differently. In the browser, Wahoo runs every program in a Web Worker, a separate thread, and kills it after three seconds (“Time's up!”). On the command line, wasmi can meter fuel: each instruction consumes a unit, and execution stops when the tank is empty (wahoo run --fuel 1000000).

§The whole journey

Follow a Wahoo program once more. Characters become tokens (01); tokens become a tree (02); the tree is checked and simplified (03); it is lowered to stack-machine instructions (04), made cheaper (05) and encoded as bytes. The browser validates those bytes, compiles them to the processor's own instructions and runs them in a sandbox, calling back into JavaScript every time the program says wahoo. In the playground you can watch every one of those steps on your own programs.

§References

1. J. von Neumann (1945). First Draft of a Report on the EDVAC. Moore School of Electrical Engineering, University of Pennsylvania.
2. J. R. Levine (1999). Linkers and Loaders. Morgan Kaufmann.
3. A. Zakai (2011). “Emscripten: An LLVM-to-JavaScript Compiler”. Proceedings of SPLASH (OOPSLA companion).
4. A. Haas, A. Rossberg, D. L. Schuff, B. L. Titzer et al. (2017). “Bringing the Web up to Speed with WebAssembly”. Proceedings of PLDI.
5. V8 team (2018). “Liftoff: a new baseline compiler for WebAssembly in V8”. v8.dev blog.
6. WebAssembly Community Group (2019). WebAssembly Core Specification, W3C Recommendation.