Introduction

WebAssembly (Wasm) is an essential part of the software ecosystem. It runs on billions of browsers around the world, supporting applications ranging from Zoom [6] and Figma [8] to Photoshop [32] and Google Earth [31]. Firefox relies on it to sandbox untrusted native libraries [10,23]. It enables safe extensibility in the data center via infrastructure like Istio [28] and server-side applications like Shopify [5]. Simultaneously, Wasm is enabling a new generation of highscale, low-latency, function-as-a-service (FaaS) edge computing platforms such as Fastly's Compute@Edge [27] and Cloudflare's Workers [18].

Wasm relies on Software-based Fault Isolation (SFI) [35] to enforce memory isolation. We offer two optimizations -Segue and ColorGuard -that improve SFI performance and scalability.

The key to improving performance is reducing instrumentation overhead. SFI enforces isolation by instrumenting every memory operation in an application. These operations are often part of the application's critical path; thus, reducing instrumentation overhead in even small ways enhances performance in a wide range of workloads, such as those on the client-side web.

The key to improving scalability (i.e., how many instances we can run in a process) is tied to how Wasm is used serverside in high-scale FaaS platforms such as Cloudflare's and Fastly's. These systems spin up a new Wasm instance in response to every network request-and handle massive numbers of requests concurrently. Wasm's fast startup times (30 µs [26]) and low context switch overheads [19] (2-3 orders of magnitude cheaper than OS context switches [15]) are critical for enabling this. To maximize efficiency, FaaS providers want to minimize the number of OS-level worker processes needed to run Wasm instances-this reduces OS context switch overheads, prevents load imbalances, and enables efficient communication between instances [7].

This paper introduces Segue and ColorGuard to improve SFI performance and scalability by leveraging the unique features of modern x86 processors.

With Segue, we note that all SFI instrumentation has two steps. First, a base address (e.g., the start of a Wasm linear memory) is added to the operand of a memory operation, (e.g., an i32.load in Wasm). Second, a bounds check is performed. This is similar to a segmented memory system. It turns out that the x86-64 ISA retains a vestige of x86 segmentation support; thus, by moving our base address to a segment register and using segment relative addressing (e.g., as part of the x86 mov that implements an i32.load), we can eliminate at least one instruction, free up a general purpose register, and even free an operand slot in our x86 mov operation (that was previously used for base addition). This gives the compiler more freedom to efficiently allocate resources, resulting in speedups ranging from 5.4%-38% depending on the workload (see § 3).

With ColorGuard, we note that all production Wasm implementations rely on a large address space (4GB) and guard We present these two techniques in the next section. In § 3 we evaluate the performance of these techniques in production Wasm toolchains. We survey some related work in § 4 and conclude in § 5.

Design

We briefly describe how SFI works in WebAssembly ( § 2.1), then explore how we optimize it with Segue ( § 2.2) and Col-orGuard ( § 2.3).

SFI in WebAssembly

WebAssembly (Wasm) enables multiple isolated execution environments (sandboxes) within a single process address space. Memory isolation is enforced on 32-bit address spaces, called linear memories.

A Wasm load or store takes two 32-bit unsigned operands. A Wasm compiler will generate code to add these operands (resulting in a 33bit address), and add the result to a 64bit base address (the start of the linear memory for a particular sandbox), presumably perform a bounds check, then finally do the load or store with the computed address.

However, bounds checks are expensive [37], which is why they are rarely done in practice. Instead, production Wasm implementations generally enforce bounds implicitly using a system of large address spaces and guard regions-they combine a 4 GB linear memory address space and a following 4 GB unmapped memory region (a guard region). Thus, by construction, any 33bit unsigned offset plus the base address will be within 8GB of the base, and any access beyond the first 32-bit (4GB) address space will trap.

For the purpose of our discussion, two details here are important. First is the base addition step, which we largely optimize away with Segue. Second is the 8GB per-instance requirement, which we reduce with ColorGuard.

Reducing SFI overhead with Segue

Segue is an optimization for WebAssembly that leverages the partial support for segmentation in x86-64 CPUs. Historically, segmentation support started with the 8086 to expand memory beyond 16-bit addressing, was extended to support protection in the 80286, and grew to support 32-bit addressing [4].

Segmentation allowed applications to define segmentsregions of memory identified by a start address (the base) and a size (limit) -for different portions of application memory such as the stack, heap, code, etc. Segmented applications expressed memory addresses as offsets into segments, relying on the hardware to convert each offset into a full global address (by adding the base), and to check that each offset is below the segment limit.

Segmentation, however, never found broad adoption in the most popular 32-bit operating systems. Instead, the large address spaces supported by 32-bit processors led to flat addressing being sufficient for a time. When applications finally did outgrow 32-bit addressing, the flat addressing model persisted in x86-64. Support for segmentation was largely dropped in 64-bit mode. However, two segment registers (%FS and %GS) were enhanced in x86-64 to support 64-bit base addresses. Modern operating systems dedicate one of these registers to thread level storage (TLS), and the unused register (e.g., %GS on Linux) is free for other uses.

Segue leverages the available segment register to optimize base address addition in Wasm by storing the Wasm linear memory base in this register. Segue performs all Wasm linear memory accesses using segment-relative addressingfoot_0 .

Despite this hardware functionality existing in all x86-64compatible CPUs for more than a decade, and the requirement for converting relative offsets in data structures for managed runtimes existing even longer, no Wasm runtime currently uses this approach. Prior 32-bit SFI implementations like vx32 [9] and NaCl [36] leveraged x86-32 segmentation to support efficient isolation-however, with the changes in x86-64, segmentation was no longer perceived to be useful beyond optimizing TLS. We offer the observation that this hardware is still beneficial today. We use Wasm as an initial example, but this technique could potentially generalize to other managed runtimes.

To see how Segue can benefit Wasm compilation, consider Figure 1. Figure 1a offers an example of two common ways a program might access memory. The first read (line 7 in Figure 1a) is a simple access into Wasm's heap from some previously calculated address. Looking at Figure 1b (which shows this code compiled without Segue), we can see the compiler must first use an instruction to truncate the 64-bit value ptr to 32 bits (Wasm heaps are a maximum of 4GB), and then use another instruction to add the Wasm linear memory base and access the memory. Back in Figure 1a, the second read on line 11 is accessing an array element, which similarly requires 2 instructions in Figure 1b.

If we instead compile with the Segue optimization (Figure 1c), we can see the following benefits:

◮ Segue frees up a general purpose register (GPR), so it can be used for other computations. Today, Wasm compilers use a register to store the heap base. In Figure 1b we can see rax being used for this purpose, and how Segue uses the otherwise unused gs instead in Figure 1c.

◮ Segue frees an operand slot in complex x86 memory addresses. x86 supports a variety of memory address formats that can specify complex address calculations. Wasm compilers today must reserve one of these operand slots to specify the Wasm base as shown in lines 7 and 11 in Figure 1b (base is stored in register rax). Thus, the compiler cannot use this slot for other inline addition.

In our example, we can see how this forces the Wasm compiler to use two separate instructions, first to add the values for arr and idx, and then separately perform the memory access (lines 9 and 11 in Figure 1b). Segue restores the operand slot and allows this operation in a single instruction(line 8 in Figure 1c).

◮ Segue truncates segment offsets to enforce Wasm bounds.

Wasm compilers today must calculate machine addresses using 64-bit input values, because the Wasm linear memory base is 64 bits wide, and register operands of different sizes cannot be mixed in x86 memory operands. For example, in Figure 1a on line 7, we must use rbx (a 64bit register) as the parameter when adding to rax. Thus, we must have a prior instruction for truncation (on line 5) to 32-bits (required because the Wasm address space is 4GB). With Segue, we use a particular x86 prefix to override the default address size and instead cause the segment offset to be limited to 32 bits. This truncation occurs within the mov instruction directly, as is apparent from its use of ebx in line 6 in Figure 1c.

These three benefits allow Wasm compilers to more efficiently use registers and emit instructions, which in turn speeds up computations. The only added cost is a slight increase in the size of memory instructions when using the %GS prefix and address size override prefix (x86 instructions are variable length). However, we believe in general the benefits outweigh this.

Improving Scalability with ColorGuard

While 64-bit address spaces may seem nearly unlimited, they are not. Intel® 64-bit CPUs only support a 48-bit address spacefoot_1 , and only 47 bits are available to user space applications [17]. As each Wasm sandbox requires 8GB of address space, we can only create 2 47 /8GB sandboxes per processroughly 16K.

Production FaaS services that use Wasm, such as Fastly, are already bumping up against this limit [26]. Running more sandboxes requires instantiating more processes. This increases overhead, as process context switches are expensive, and splitting Wasm instances across processes induces load imbalances and increases communication overheads between instances [7]. Unfortunately, this is only likely to get worse in the future. For example, the Wasm component model [34] is likely to significantly increase the number of desired instances for a given application. Thus, we must address the cause of this limit.

The main culprit is the memory footprint of Wasm sandboxes, which as already noted, demands 8GB for each instance, including the linear allocated space and guard page. This means, for example, that even if a sandbox uses only 1GB of memory, it still needs to reserve (but not necessarily commit) 8GB, wasting 78.5% of its assigned address space. In practice, Wasm instances in FaaS settings rarely exceed a few hundred megabytes [7].

Efficiently Packing Sandboxing with ColorGuard. To rectify this problem, we present ColorGuard, an optimization that efficiently packs sandboxes in memory by leveraging Memory Protection Keys (MPK) [17]. MPK is a recent x86 hardware feature 3 that adds thread-specific, hardware-enforced page permissions to the virtual memory systems.

MPK allows applications to assign a 4-bit tag (called a domain or color) to page table entries (PTEs) via system calls. The application can then manage which colors a thread has access to completely in userspace via the pkru registerpkru updates are very fast (roughly 25 cycles [25])-enabling rapid transitions between different protection mappings.

ColorGuard leverages MPK to increase the maximum number of sandboxes that can be run in an 8GB address range by a theoretical maximum of 15× (although in practice, we see a maximum of 11.91× as discussed in §3.2). The key intuition behind ColorGuard is that sandbox B's working memory can be used as sandbox's A's guard region, so long as A is a different color than B, ensuring that any access by A to B will trap.

To achieve this property, ColorGuard uses MPK to stripe memory such that nearby sandboxes have different colors. We see this illustrated in Figure 2 which contrasts the memory layouts of sandboxes using traditional guard regions with sandboxes using ColorGuard.

More precisely, ColorGuard requires every sandbox that occupies memory in the 8GB following the first sandbox use a different color for its linear memory; all other memory (in- 3 MPK in this paper can refer to Page Protection Keys support, which was added to Intel® server-class systems as of Skylake (2017) and clients as of Tiger Lake (2020), or to Memory Protection Keys support that was added by AMD in EPYC Milan (2021).

cluding the memory belonging to the host application) is completely unchanged and assigned the default MPK color (0).

We see this illustrated in Figure 2. Here, each sandbox has a 1GB linear memory and uses one of eight MPK colors to stripe the 7GB region following the end of sandbox 1-offering an 8x increase in sandbox density. In our example, any out-ofbounds memory access from sandbox 1 would trap as it would hit a region with a different color. We could further increase density to 15×, by using all of MPK's colors and creating smaller sandboxes, i.e., for sandboxes of 8GB/15 ≈ 550MB.

Finally, we note that this striping pattern scales up to any number of sandbox chains -sandboxes that are placed in adjacent memory regions. We only need guard pages in a sandbox chain in two instances: (1) after the final sandbox to ensure the last sandbox in the chain is protected, and (2) if 15 consecutive sandboxes use less than 8 GB combined, we'll need a guard page before using the first color again. We also note that clever sandbox runtimes can also chain sandboxes of different sizes to efficiently use colors and possibly eliminate the second case; we leave such explorations to future work.

Evaluation

To evaluate the overhead of Segue and ColorGuard, we implement them in two Wasm compilers used in production today, then evaluate each mechanism on applicable benchmark suites.

Segue focuses on improving the performance of SFI; we thus benchmark it in the Wasm2c compiler [1] used by Firefox to efficiently sandbox buggy dependencies [16]. On the other hand, ColorGuard addresses scalability; we thus evaluate it in the Wasmtime compiler [2] used by cloud platforms like Fastly to sandbox computations from different clients in a cloud server.

Implementing Segue in Wasm2c. Wasm2c compiles Wasm by transpiling it to a limited subset of C which can then be compiled with a standard C compiler. We modified Wasm2c so that accesses to the heap were performed using a segment register. Specifically, our version of Wasm2c emits C code that relies on a GNU-extension called named address spaces [11]; this extension allows pointers in C to indicate that they belong to a particular segment. We then compile the emitted C code with Clang to get a native binary 4

Related Work

The designs of Segue and ColorGuard draw upon a long history of SFI research.

SFI techniques and their cost

The first instance of SFI was developed by Wahbe et al. [35]. Both Wahbe's implementation and subsequent work [9,14,22,29,30] incurred performance overheads between 20% and 30%. As a result, techniques have been developed to optimize these overheads [38] through static analysis. In contrast to these approaches, Segue removes overheads by leveraging hardware.

Various SFI systems have used x86-32 segmentation for sandboxing on 32-bit platforms [9,19,36]. However, using 32-bit segmentation in modern systems is infeasible as it requires sharing a 4GB address space across all running sandboxes. In contrast, Segue demonstrates how we can extract the benefits of segmentation even on 64-bit platforms.

SFI systems have used other CPU features to improve performance as well, for example Intel® Memory Protection Extensions (MPX) [20], MPK [15,33], Intel® protection rings [21], virtualization [3,12,15], and ARM's memory domains [39]. However, use of such hardware comes at a cost. MPX has overheads comparable to software implementations [20], and MPK is restricted to 15 domains when directly used to sandboxed code [33]. Meanwhile, while ring, virtualization and Memory Domains incur expensive context switches due to ring/privilege switches [17]. In contrast, Segue allows SFI compilers to leverage hardware without incurring such extra costs.

Reducing register pressure in SFI compilers Register pressure has been a recurring source of performance degradation in SFI systems. Wahbe et al.'s SFI implementation on MIPS and Alpha machines reserved four and five registers respectively out of the available 32. Reserving these registers increased pressure on the remaining registers, which caused up to a 10% penalty on their benchmarks. Subsequent work [22,29,30] optimized SFI schemes so that they only reserved one register. However, for platforms like x86 and x86-64 which support only 8 and 16 general purpose registers respectively, this still produces significant register pressure. Segue takes the final step in reducing register pressure and reduces the number of reserved general purpose registers to zero, allowing for more efficient SFI implementations.

Guard pages and scaling in SFI tools Guard pages have long been used in SFI systems, and they have long been a bottleneck for scaling. For example, Wahbe et al. [35] used guard regions to protect the stack, and NaCl64 [29] used 80GB guard regions to optimize heap accesses. NaCl64's 80GB guard pages eliminate bounds checks but cost the system its scalability: indeed, these limit it to only 255 sandboxes [23].

Limited hardware resources have also caused scalability problems in SFI systems. For example, SFI tools that solely rely on MPK [15,33] to enforce memory isolation have trouble scaling due to the limited size of the PKRU register. Since the PKRU only supports 16 domains, these systems cannot use more than 16 sandboxes, or they suffer expensive domain evictions which require swapping out pkeys of all pages belonging to a memory region [25]. In contrast, ColorGuard improves scaling by combining classic SFI with MPK.

Conclusion

For decades, SFI was largely an academic curiosity. In the last five years, WebAssembly has made it a critical technology for the internet-used by billions of clients, and an increasing number of servers around the world.

However, there are still limitations of Wasm that both constrain existing users and represent barriers to even greater adoption: performance and scalability. Segue is a novel use of existing Intel® hardware (segmentation) to bring down the cost of an instrumented load to a single instruction (the same as non-Wasm, non-SFI code).

ColorGuard uses a more recent Intel® feature (MPK) to enable guarded sandbox instances to be packed more densely, in the best case by more than an order of magnitude.