Running Goose on WebAssembly

A proposal, not implemented. Spec §10.4 says platforms without address-space reservation fall back to "index-based references + bounds-checked growth" and leaves the details open (open issue 15); this note works them out. The cost figures in it are estimates, not measurements.

1. The problem

Each data stack is a region of reserved address space, committed as it is touched (spec §1.2, §10.4, implementation §7). Growth is a pointer bump with no capacity check, and a guard gap past each region turns an overrun into an abort. References into a stack are plain addresses and stay valid across growth because a stack's base never moves, a property the language is built around (tutorial).

WebAssembly has none of this. A module's linear memory grows only at its end, has no unmapped pages inside it, and in wasm32 holds at most 4 GB. A port with a few stacks of a small fixed size each runs, but only toy programs fit.

2. What every option needs: growth checks

Linear memory has no guard pages, so a region that overruns writes into the next one. Every approach therefore checks growth, if (lim - top < n), including a port that keeps fixed regions. The options differ in what a failed check does: abort, or move the stack. Only moving forces a different pointer representation.

The checks go wherever a stack's top moves up:

• pushes, appends and resize (EmitPush, EmitAppend);
• in-place construction: str(), to_bytes(), print's rendering, a length prefix reserved and patched afterwards (OpenRzDest, EmitReprefix, EmitSlidePrefix, varint prefixes), frame objects, the _er twins, the generated walkers;
• the runtime: a slice pool's freelist, which grows on a stack of its own (gs_spans_*), gs_bld_append in goose.h, and the helpers that write at a top with no bound, such as gs_fmt_i64(top, v) (up to 20 bytes). Each of these needs a reservation first: a worst case for a scalar, a check per chunk when rendering a nested value.

The top caches (implementation §6.10) become (top, limit) pairs, synchronized at the same points. A loop with a known trip count can reserve once before it.

3. Fixed partitions

Each stack gets a fixed slice of linear memory, and a failed check aborts with the overrun message native builds give. This is mostly configuration of the existing runtime: GS_STACK_RESERVE is the linear memory divided by the region count, and GS_STACK_BUDGET is the linear memory, which the runtime already uses to cap hardware_threads().

• RAM. On 64-bit desktop engines, linear memory that is grown but never touched is generally not backed by RAM (Windows charges commit for it), so growing to the maximum at startup wastes address space, not memory. Browsers may refuse a large memory on small devices, and Wasm cannot give pages back after a peak (there is no memory.discard).
• Capacity. The real limit is each stack's size. Programs need few regions: --stacks reports 5 for samples/14_bst, 6 for 12_huffman, 10 for 18_json (8 stacks and 2 globals' stacks), and 6 for 23_mandelbrot_threads plus 2 per worker. 4 GB over 10 regions is 400 MB per stack. Workers multiply the count.
• Sizing from a profile. Each stack index's high-water mark from a representative run could size the partitions unevenly. A native run can collect it cheaply: on Windows the fault handler commits on demand and so knows each region's depth, and POSIX can record the highest top as a region is released. GS_STACK_STATS reports only counts today. Stack numbering is specific to one build, and a profile fits one input; the inputs that overflow are the large ones.
• The open end. The partition at the end of linear memory can keep growing with memory.grow. Put the stack most likely to hold the program's large resizable there, and the common shape (one big growing array) is bounded only by the memory's own limit.
• wasm64 lifts the 4 GB cap in principle. Browsers cap memory64 (V8 at 16 GB), and every access pays an explicit bounds check. wasmtime can reserve far more and commit it lazily, which makes fixed partitions under wasm64 essentially the native model: the pragmatic choice for WASI and server-side targets.

4. Relocating stacks

Each stack is a heap block that moves to a larger one when a growth check fails, doubling its size. Since a stack can move, a reference cannot hold an address: it holds a handle.

• Encoding. A handle is one u64: the stack's id in the high bits and the offset in the low bits. Id 0 is a plain address, for static data, C memory and clang's shadow stack (where address-taken fixed locals live). Its base table entry is 0. References stay 8 bytes, so every layout stays as on the 64-bit hosts the C backend targets (implementation §6.1). The base table belongs to the thread program, like gs_stks, and also covers the globals' dedicated stacks.
• Arithmetic is unchanged. base + i * size, field offsets, the cursors that walk variable-size fields (FieldPtr), differences within a stack and a pool's range test all work on the integer. Only loads, stores and the mem* calls decode: in wasm32, bases[h >> 32] + (uint32_t)h.
• Relative references and pools need nothing. They are offsets within one stack, and a stack moves whole.
• Decodes hoist. A decoded pointer stays valid until its stack grows. Where no growth of that stack and no call that can reach it come between, a decode can be hoisted, and those are the extents top caching already computes (SyncReach, PlanTopCaches). Array loops through hoisted views (AddView) then run as they do natively. The cost falls on pointer chasing (a decode per hop through a T&) and on pushes, whose check fixed partitions pay too. An estimate: 1.1 to 1.5 times the time under fixed partitions, worst on tree and list code. Copying on relocation is amortized by the doubling; peak memory is up to two to three times the live data, with the old and new blocks and fragmentation.
• Threads. Each thread program has its own base table, thread-local. A spawn copies flat images, so no handle crosses threads.

5. Options that do not work today

• Multi-memory. A memory per stack would keep offsets stable across memory.grow, but a load names its memory as an immediate. Stacks are chosen at run time (gs_sp + k, a fat reference's stk), and C cannot target several memories.
• The memory-control proposal (memory.discard, protect, map) would bring back reserve, commit and guard pages, and with them the native model. It has not shipped.
• GC arrays cannot grow, so they relocate as heap blocks would, and C cannot reach them.
• A Wasm dialect that forbids references across growth breaks the property the language is built around.

6. Where relocation's changes fall

In order of risk, not size:

1. In-place construction while the same stack grows (the list in §2). Natively, a held pointer to a slot's start or to a prefix still to be patched survives growth. Under relocation it must be a handle, or be derived again after the growth.
2. The assumption that the base never moves. View hoisting relies on it (its safety argument is that growth writes only the length), and so do the top caches, reference aliases (refalias) and let first .= v.push(...). There are few lines here but most of the potential bugs. One rule contains them: handles everywhere, and decoded pointers only over extents the sync analysis proves.
3. The C boundary: the runtime, extern fns, the blessed packages and goose.h. The C ABI can stay on plain pointers. Slices and references are decoded at the call, since a C callee can grow a Goose stack only through a builder. A builder parameter gets a staging stack whose contents are appended after the call returns. Packages then recompile unchanged, with gs_bld_append gaining its capacity check.
4. Access spellings in codegen, which is mechanical work. A rough count is 35 *(T *) dereferences, 140 emitted ->, 26 mem* calls and 21 ->top, mostly through LoadLoc, IndexLoc, DerefLoc, PointeeLv and VarLoc.
5. Unchanged: the parser, the typechecker, the optimizer, BCE apart from view hoisting, and the standard library, which is Goose source the same codegen compiles. The library's only contact with C is its externs: math on scalars, find_any and find_pair on slices, os's builders, and json's frexp with an i32&.

7. Wasm costs outside the data stacks

• Native call stack overflow. The runtime reports it as a runtime error (implementation §7). Wasm has no vectored handler or sigaltstack, so the engine traps instead. Clang's shadow stack (64 KB by default) overflows silently unless checked (-z stack-size, Emscripten's STACK_OVERFLOW_CHECK).
• The OS layer (runtime_os.h) maps onto WASI or Emscripten.
• Threads need shared memory, which browsers give only to cross-origin-isolated pages.

Recommendation

1. Add the growth checks of §2 as a configuration of their own. Native builds can run with them, so the existing test suite covers them. Fixed partitions are then configuration, and they make a working port for programs whose stacks fit.
2. If that is not enough, add relocation as a native configuration first: stacks in heap blocks that move on growth. Give it a stress setting that moves a stack on every growth, so the test suite exposes every stale decoded pointer, and use the benchmark suite to measure the cost. Only then bring in a Wasm toolchain.