Improving Webassembly and Its Tooling -- Q&A with Wasmtime’s Nick Fitzgerald

WebAssembly recently became a World Wide Web Consortium recommendation and the fourth language to run natively in browsers, after HTML, CSS, and JavaScript. While WebAssembly’s first major version focused on the browser, WebAssembly is now focusing to non-browser environments to fulfill a variety of computational tasks, where sandboxing, portability or performance are essential. In this context, non-browser-based WebAssembly runtimes are being developed in miscellaneous languages, (Wasmtime and wasmer in Rust, GraalWasm in Java, Lucet in Rust, py-wasm in Python, swam in Scala, and more), with different areas of focus (e.g., performance for wasm3, blockchain applications for eos-vm, small footprint for wasm-micro-runtime). One challenge for these runtimes is to implement and experiment with the new batch of WebAssembly proposals that strive to fulfill WebAssembly’s vision outside the browser.

Although Wasmtime is implemented in Rust, the developers maintain APIs for embedding it within various other languages:

• C
• Python
• Go
• .NET

As Wasmtime recently implemented the reference types proposals, InfoQ interviewed Nick Fitzgerald, who implemented the feature, on his work involving WebAssembly and the next steps for WebAssembly and Wasmtime.

InfoQ: Can you tell us more about you?

Nick Fitzgerald: I work on the Wasmtime WebAssembly runtime, the Cranelift code generator, and various parts of the Rust and WebAssembly ecosystems.

Outside of work, I enjoy riding bikes (both for getting places and for doing fun tricks on my BMX), listening to hip-hop (I’ve had “CLONES” by Tierra Whack on repeat recently), and reading books (I just finished The Fifth Season by N.K. Jemisin and it was stunning!). I occasionally make algorithmic art and draw it with a pen plotter. Pen plotters are a precursor to modern printers—pretty much obsolete and only used by artists these days—that hold a pen in a little robot arm and draw vector graphics. I recently adopted a kitty cat from the local humane society; his name is Goomba. My pronouns are he/him.

InfoQ: How did you get involved with WebAssembly?

Fitzgerald: I stumbled into WebAssembly, but looking back this wasn't really an accident: I was in the best position to stumble into it I could have been.

I used to work on the Firefox Developer Tools team at Mozilla, where I wrote and maintained our source map support. Source maps are a simple debugging information format for JavaScript. Minifiers and compile-to-JavaScript languages like TypeScript or Elm will emit them alongside their generated JavaScript code. The source maps allow debuggers and similar tools to translate locations in the generated code into locations in the sources that the developer originally authored. Source maps contain similar information as DWARF’s .debug_line section. With a source map, for example, the developer tools can show you “line 42, column 8 in my-module.js” rather than “line 1, column 643243982346519205631 in file minified-bundle.js.”

So here is the first connection: I was already working on tooling that helped people write code for the Web in a language that wasn’t JavaScript, should they choose to do so. WebAssembly also helps enable that, but now without compiling to JavaScript as an intermediate step. But all of this started before asm.js (a WebAssembly predecessor) was even a thing.

Anyways, source maps can contain a lot of information, so the format goes to great lengths to compact that information in as dense a representation as possible. Even so, source maps can get big, and decoding them can get quite expensive. When loading a Web page, the developer tools have to parse a source map before they let the page execute JavaScript, so that they can do things like set user-requested breakpoints in regions of top-level code that are only executed at start-up. This has to block: if it didn’t, and was asynchronous, then we have a race condition between whether we will finish parsing the source map in time to set the breakpoint, or whether that start up code will already finish executing before we get a chance to set our breakpoint. Because parsing source maps is on the critical path of reloading Web pages when the developer tools open, we care quite a bit about its performance.

Our library for parsing source maps was written in JavaScript. Over the years, we applied many optimizations and performance improvements to the library. We were bending over backward to avoid allocations and restructuring object layouts and function bodies so that Firefox’s JavaScript JIT compiler could better understand and optimize them. But we noticed that the more we optimized this code, the less idiomatic and less maintainable it became.

Fast forward a few years and WebAssembly has just started shipping on all major browsers and the Rust compiler has the brand-new wasm32-unknown-unknown compile target for compiling Rust programs into WebAssembly. I’m no longer on the Firefox Developer Tools team, but I had some free time over the 2017 winter holidays, and I wanted to try compiling some Rust to WebAssembly. Tom Tromey and I started brainstorming and bouncing ideas around, and we finally came up with the idea of replacing the core of the source map library with Rust compiled to WebAssembly and an architecture for doing that effectively. At the time, no one had been integrating Rust and Wasm into JavaScript libraries yet, and most uses of Wasm, in general, were monolithic C/C++ programs with tiny bits of JavaScript glue at the edges. People weren’t surgically replacing compute-bound kernels of JS code with small bits of Wasm like we were attempting, so we didn’t have a lot of direct examples to lean on.

When we finished rewriting the core of the source map library, we found that not only was the new code much faster, but it was still idiomatic. Rust didn’t force us to choose between runtime performance and clearly expressing our intent. For example, avoiding allocations in Rust (something that was a huge pain in the JavaScript codebase) is not only easy but natural thanks to Rust’s ownership and borrowing systems. To learn more about this project, check out my article Oxidizing Source Maps with Rust and Wasm on the Mozilla Hacks blog.

After the source map project, I was given the opportunity to work on Rust and WebAssembly full time at Mozilla. I led the Rust project’s WebAssembly working group, where we fleshed out the Rust and WebAssembly ecosystem and tooling. These days I’m focusing on the Wasmtime WebAssembly runtime for running Wasm outside the Web and the Cranelift code generator that Wasmtime uses under the covers.

InfoQ: You wrote wasm-smith, a test case generator that generates valid WebAssembly programs. Other programming languages have their own program generators (e.g. C/C++, JavaScript). What are the problems that generative testing solves that are hard to attack with other techniques?

Fitzgerald: In short, it’s about discovering otherwise hidden and hard-to-find bugs. There’s a ton that we miss with basic unit testing, where we write out some fixed set of inputs and assert that our program produces the expected output. We overlook some code paths or we fail to exercise certain program states. The reliability of our software suffers. We are fallible, but at least we can recognize our limitations and compensate for them.

Testing pseudo-random inputs helps us avoid our own biases by feeding our system “unexpected” inputs. It helps us find integer overflow bugs or pathological inputs that allow (untrusted and potentially hostile) users to trigger out-of-memory bugs or timeouts that could be leveraged as part of a denial of service attack.

Some people are familiar with testing pseudo-random inputs via “property-based testing” where you assert that some property always holds and then the testing framework tries to find inputs where your invariant is violated. For example, if you are implementing the reverse method for an array, you might assert the property that reversing an array twice is identical to the original array. Property-based testing frameworks tend to have a similar workflow as regular tests: they run in a short period of time (say a few seconds) and then report their results to you. You often run these tests during local development and each time your project receives a pull request.

Other people might be familiar with testing pseudo-random inputs via “fuzzing.” Traditionally, people doing fuzzing were more often looking for security vulnerabilities than general correctness bugs. They run tools like Address Sanitizer while fuzzing, so they can better detect memory unsafety. Rather than run tests for a few seconds during local development, fuzzing campaigns tend to run for long periods of time or even 24/7. Modern fuzzing engines aren’t generating purely random inputs; they observe the system under test’s code coverage and other heuristics, making feedback-driven mutations to old inputs when creating new inputs. This helps them efficiently explore the input space. The downside is that there is, in general, no guarantee that a given mutation will still result in a valid instance of the input type. It might, for example, introduce a syntax error.

Ultimately, mutation-based fuzzing and property-based testing are two approaches to the same pseudo-random testing problem but, due to historical accidents, have different communities and different workflows. Rust’s arbitrary crate provides an API similar to property-based testing, where you receive structured inputs rather than raw byte buffers, but is additionally designed to cooperate with modern fuzzing engines, translating their raw byte buffers into structured inputs. This gives you the best of both worlds: valid inputs that always fall within your test domain, and the ability to efficiently explore the input space via code coverage feedback and other heuristics. wasm-smith is, in turn, built upon the arbitrary crate, bringing these advantages to WebAssembly testing.

InfoQ: The ability to select a finite set of test cases that will be useful for a given goal from an infinite test space is a key characteristic of a test case generator. So is the reproducibility of test cases and the ability to measure or estimate the coverage reached vs. objectives. Why wasm-smith, how is it used and what are the key characteristics of its Wasm program generation?

Fitzgerald: Sometimes with fuzzing a programming language implementation, the fuzzer “gets stuck” in the frontend. That is, the fuzzer explores the parser really well, but even if the inputs parse successfully, they have type errors or reference undefined functions and variables. This means that you aren’t ever exercising your compiler’s optimization passes or checking that the program execution is correct. wasm-smith is designed to get deep into WebAssembly compilers and runtimes because it always generates WebAssembly modules that will pass validation and type checking. It will never generate an input that fails to parse, reference an undefined variable, or incorrectly add an integer and a float together. Its generated Wasm modules will always get past your frontend, type check successfully in your validator, get through your optimization passes, and enter program execution.

You’re absolutely correct that reproducibility is of utmost importance. If you found a bug, but now you can’t ever reproduce it, you are highly unlikely to ever fix that bug except perhaps by accident. wasm-smith takes in arbitrary bytes and translates those bytes into a valid WebAssembly module. wasm-smith is deterministic; given the same input bytes, it will always produce the same output module. This is critical for reproducing test failures.

But wasm-smith isn’t ever generating a whole corpus of tests at once; it always produces one Wasm module at a time. Instead, we trust the coverage-guided fuzzing engine that wasm-smith is sitting on top of to efficiently explore the input space and provide us with new and interesting byte sequences that wasm-smith will translate into new and interesting Wasm modules.

Another important aspect of pseudo-random testing is test case reduction. You have an input that triggers a bug, but it is huge—many kilobytes in size, most of which are probably unrelated to the bug. Ideally, we would have only the parts of the input which are required to reproduce the failure, and there wouldn’t be anything else to distract us from our bug fixing or act as a red herring when we’re trying to understand the bug. This is the goal of test case reduction: to shrink a test case down to just the few necessary bits required to trigger the bug. Often this is handled with domain-specific programs. C-Reduce, for example, will take a C source file and reduce it as much as it can while still triggering a given bug. Rather than write a Wasm-specific test case reducer, we use generic byte buffer shrinkers to reduce the size of the input bytes that wasm-smith translates into Wasm modules. This technique is simple and, because it doesn’t require domain-specific knowledge of the inputs, works for everyone building any kind of test case generator on top of the arbitrary crate. If you want to learn more about this technique, I recommend reading the paper Test-Case Reduction via Test-Case Generation by David R. MacIver and Alastair F. Donaldson.

InfoQ: Did you find any bugs in existing WebAssembly tools thanks to wasm-smith?

Fitzgerald: Oh yeah, totally. When I was initially writing wasm-smith I set up a fuzz target to check that wasm-smith was always generating valid Wasm modules using the wasmparser crate’s WebAssembly validator. At first, this fuzz target was finding all of these bugs in wasm-smith where I’d accidentally forgotten to check some precondition and it was generating invalid modules. But very soon after I fixed those bugs in wasm-smith, I started finding bugs in the wasmparser crate’s validator. wasmparser is used by a bunch of different projects: Wasmtime, Cranelift, even Firefox. The Wasmtime project has already been continuously fuzzing wasmparser and its validator with other techniques, and Firefox has been fuzzing it as well. So it isn’t like there was a ton of low-hanging fruit waiting to be plucked; wasmparser is already pretty hardened. Nonetheless, wasm-smith has already uncovered about fifteen bugs in wasmparser. It has also found a bunch of bugs in our other Wasm tooling, such as our disassembler.

InfoQ: We recently reported on your implementation of reference types in Wasmtime. What are reference types? Why are they useful?

Fitzgerald: Reference types are WebAssembly’s first foray beyond simple integer and floating-point numbers, and into the world of garbage-collected references. Wasm modules can now properly interact with external host objects. This means better integration between a Wasm module and the outside world: with DOM APIs when loaded inside a Webpage, or with a database API when instantiated on a server.

The WebAssembly MVP that was first released and shipped in major browsers could only manipulate 32- and 64-bit integers and floating-point numbers. It could load and store them in memory, where you could pack them next to each other into C-style structures, but you were always stuck within your own little world as far as data types went. You couldn’t directly hold onto references to objects outside your Wasm module. You had to “MacGyver” a custom workaround when interacting with a DOM node on the Web or an open socket on a server. These workarounds typically involved custom glue code to store external references in a side table and refer to their elements by index, since MVP Wasm could work with integer indices. There are two main problems with this custom glue code. First, if you want to run your Wasm module on the Web, in a host that is implemented in Rust, and in a host that is implemented in Python, then you have to have three copies of this glue code implemented in three different programming languages. Second, the glue code, by necessity, lives outside of the Wasm sandbox which nullifies the host’s ability to safely run untrusted code.

The reference types proposal solves these problems. Wasm can now directly hold references to external objects; it can reference DOM nodes or open sockets without glue code and its drawbacks.

Finally, a lot of people are excited for full garbage collection support in WebAssembly, where a module can define its own garbage-collected structures and instantiate objects whose lifetimes are managed by the runtime. The reference types proposal is a prerequisite for this full garbage collection support in Wasm.

InfoQ: Are there alternative implementations of reference types available? How does Wasmtime’s implementation of reference types differ?

Fitzgerald: Firefox 79 and later ships with an implementation of reference types. Safari and Chrome have work-in-progress implementations that aren’t quite enabled by default yet. Outside the Web, the WABT toolkit has reference types support in its tools and its Wasm interpreter behind the --enable-reference-types flag.

Unlike Web browsers, which already have a JavaScript engine with a garbage collector, Wasmtime didn’t already have a garbage collector to lean on. Implementing reference types in Wasmtime required that I also implement a garbage collector for Wasmtime.

Two of Wasm’s strongest selling points are its general lack of nondeterminism and its predictable performance. Garbage collectors are infamous for their unpredictable pauses, and (if they support weak references or object finalization) their nondeterminism. To reconcile these conflicts, we opted for a somewhat uncommon garbage collector design. We use reference counting, rather than tracing, garbage collection. Reference counting only runs at deterministic program points where a reference is dropped; it doesn’t randomly interrupt the program at unexpected times. When a reference count reaches zero, only that object (and any other objects that only it references) are processed; this leads to predictable amounts of work each time the collector runs because it doesn’t need to scan the whole heap.

One of the primary downsides of reference counting is that it imposes high throughput overhead because every time the program adds and drops references to an object, that object’s associated reference count must be updated. Most of these updates are redundant since most increments are canceled out by a corresponding decrement, and only the delta between the two sets of operations ultimately matters. To alleviate this overhead, we trade some incrementality for better throughput by using a variant of deferred reference counting. With deferred reference counting, we don’t update an object’s reference count each time we add or drop an on-stack reference. Instead, we make sure that the reference counts are always properly recorded for non-stack references, and then we occasionally walk the stack to precisely count on-stack references. At these moments when we’ve finished walking the stack and have a precise view of the object graph again, we can sweep any objects that are no longer in use. Avoiding reference count mutations for on-stack references eliminates most of the overhead that reference counting imposes because most references are on the stack. Finally, we are careful to only perform this stack walking and sweeping deterministically and only at points where a reference enters or escapes the stack.

There are too many details to reproduce here, but if anyone is interested in them, I suggest reading the “Implementation Details” section of my article on reference types in Wasmtime.

InfoQ: WebAssembly has a number of proposals striving to realize the vision of Wasm modules shipped with rich APIs using complex types that interoperate seamlessly with other modules and the host system: type imports, interface types, module linking, and more. How far are we from this vision?

Fitzgerald: Reference types are the first step toward getting there.

One lens to view this question through is to look at where extra-Wasm glue code is still required, determine why it’s required, and then figure out which Wasm proposal will obviate the need for that glue code. That’s your path. The specific answer you get is going to depend on what you’re doing. For example, if your Wasm module defines a main function, and isn’t used like a library, then the reference types proposal may be enough already, if you don’t mind that you can’t statically differentiate between an open file and a database connection in the type system. The host will need to perform checks that the reference you passed into a write function is actually an open file, and not (say) a source of entropy—but these checks should be cheap. If you did want to statically differentiate between those things, then you would additionally need support for type imports. On the other hand, if you want to write a Web app 100% in Wasm without any JavaScript code, you’re going to need interface types for interacting with Web APIs, ECMAScript modules integration to bootstrap the initial imports, and module linking to control instantiation.

As far as timelines go, if you’re shipping a Web app you’ll need to wait until xx% of your traffic is on browsers that support the proposals you need. That could take a couple years. Although you might be able to reach for a tool that can polyfill some of these proposals for you in the meantime, like wasm-bindgen. On the other hand, if you’re targeting one particular outside-the-Web environment, you only need that one environment to gain support for these proposals. We intend to lead the way with implementing interface types and module linking in Wasmtime, so the vision should become reality much sooner in this scenario.

InfoQ: What comes next on the roadmap for Wasmtime?

Fitzgerald: The proposals you’ve mentioned already are high up on our priorities list: type imports, interface types, and module linking.

But it’s not enough just to have a runtime that supports these features. People don’t write WebAssembly by hand, they use a toolchain to generate Wasm code. We also need these toolchains to support emitting Wasm code that takes advantage of these features. As far as the Rust toolchain for generating Wasm goes, we have plans to build a spiritual successor to wasm-bindgen that doesn’t assume a JavaScript host, so that it will work outside the Web as well, and which is 100% based on standards like interface types and module linking. Once that’s implemented, we will rebase wasm-bindgen on top of it so that it only provides the JavaScript-specific bits and the logic for polyfilling proposals that aren’t supported in all Web browsers yet.

About the Interviewee

Nick Fitzgerald works on the Wasmtime WebAssembly runtime, the Cranelift code generator, and the Rust and WebAssembly ecosystems. When he's not doing "computer" things, he's either riding his bike or playing with his cat, Goomba. His pronouns are he/him.