Laying Out Memory

Linear memory comes with no structure at all. It is a run of zero bytes, and a compiler has to decide what goes where: the program's constants and static variables, a stack for the values that cannot live in locals, and a heap. This chapter goes through those decisions and builds the two pieces nearly every compiler needs: a shadow stack, and an allocator.

#A memory map10.1

Here is the layout most toolchains use, LLVM's among them:

• Low addresses are left unused. LLVM starts static data at 1024 by default. The gap means a write through a null pointer, or through a small offset from one, lands in memory nobody uses.
• Static data comes next: string literals, constant tables, and initialised and zero-initialised global variables. Their addresses are fixed at compile time, so code refers to them by constant address.
• The shadow stack follows, growing downwards from its top towards the static data. Its size is chosen at link time; LLVM's default is 64 KiB, and real programs usually need more.
• The heap starts above the stack and grows upwards, using memory.grow when it runs out of room.

With this layout, a stack overflow runs down into the static data and corrupts it silently. LLVM's linker has an option, --stack-first, that puts the stack at the very bottom of memory instead, below the static data. Then an overflow takes the stack pointer below address 0, where it wraps around to a huge unsigned address, and the next access through it traps as out of bounds. That turns a silent corruption into a crash, at the cost of giving up the unused low area for catching null pointers. Either way, a compiler can also check the stack pointer against a limit in each prologue, and trap explicitly.

None of this is part of WebAssembly. It is a convention between the compiler, its runtime library and the host. Your compiler can use a different layout, as long as everything that shares a memory agrees.

#The shadow stack10.2

Chapter 5 explained that the engine's call stack is invisible, and that locals have no addresses. A variable whose address is taken must live in linear memory instead. The usual home for such variables is a shadow stack: an area of linear memory, managed exactly like a native stack, with the stack pointer kept in a mutable global.

Each function that needs stack memory subtracts its frame size from the stack pointer on entry, uses the memory between the new and old values, and adds the frame size back before it returns. Functions that need no stack memory do not touch the stack pointer at all, and in practice that is most of them.

Here is a C function that needs a frame, because it passes the addresses of two locals to another function:

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

int test(void) {
    int x = 1, y = 2;
    swap(&x, &y);
    return x * 10 + y;
}

And here it is, compiled by hand the way a compiler would:

(module
  (memory 1)
  (global $sp (mut i32) (i32.const 65536))      ;; the stack starts at the top of memory

  (func $swap (param $a i32) (param $b i32)
    (local $t i32)
    (local.set $t (i32.load (local.get $a)))
    (i32.store (local.get $a) (i32.load (local.get $b)))
    (i32.store (local.get $b) (local.get $t)))

  (func (export "main") (result i32)
    (local $frame i32)
    ;; prologue: an 8-byte frame, x at frame+0 and y at frame+4
    (local.set $frame (i32.sub (global.get $sp) (i32.const 8)))
    (global.set $sp (local.get $frame))

    (i32.store offset=0 (local.get $frame) (i32.const 1))
    (i32.store offset=4 (local.get $frame) (i32.const 2))
    (call $swap
      (local.get $frame)
      (i32.add (local.get $frame) (i32.const 4)))

    ;; epilogue, with the return value computed first
    (i32.add
      (i32.mul (i32.load offset=0 (local.get $frame)) (i32.const 10))
      (i32.load offset=4 (local.get $frame)))
    (global.set $sp (i32.add (local.get $frame) (i32.const 8)))))

21

The frame pointer is kept in a local, $frame, so that every variable in the frame is reached as $frame plus a constant offset, which the load and store offset immediates make free.

Only x and y live in memory, because only their addresses are taken. Everything else, including $t in swap, stays in locals, where the engine can keep it in a register.

The stack pointer in LLVM's convention is a global named __stack_pointer. It is usually not exported, but when several modules share a memory, as in dynamic linking, it must be imported by all of them from a single place, so they agree on where the stack is.

If a function returns early, from several places, it must restore the stack pointer on every path. Wrapping the body in a block and branching to an epilogue at its end is the easy way. If the function can be left by an exception (Chapter 20), the stack pointer must be restored by whoever catches it, which is one reason compilers save it before each try.

#Struct layout10.3

A compiler chooses the layout of each aggregate type: the offset of each field, and the alignment and size of the whole. WebAssembly does not care, since every access is just an address and an offset, and unaligned accesses work. But the C rules are a good default, and are what you need if your structs are shared with C code compiled to the same memory:

• each field is placed at the next offset that is a multiple of its alignment, which for numbers is their size;
• the struct's alignment is the largest alignment of its fields;
• the struct's size is rounded up to a multiple of its alignment, so that arrays of it keep every element aligned.

For example:

Reordering the fields from largest to smallest alignment (value, count, tag) would make it 8 bytes. A language that does not promise field order, such as Rust, can do that reordering automatically.

Natural alignment matters less for speed on WebAssembly than it once did on native hardware, but it is still worth having: engines may emit different code for unaligned accesses on some ARM chips, and the atomic instructions of Chapter 23 require natural alignment and trap without it.

#Passing and returning aggregates10.4

A struct passed by value can be split into its fields and passed as several parameters, which keeps it in registers. Returning it can use multiple results (Chapter 5). For anything larger, the common convention, and the one C uses on WebAssembly, is:

• to pass a large struct, the caller copies it to its own stack frame and passes a pointer;
• to return one, the caller allocates space in its frame and passes a pointer to it as a hidden first parameter, which the callee fills in.

A compiler that will never call C, and never be called by it, can choose its own convention. Splitting small structs into scalars, up to four or so fields, and using memory beyond that, is a reasonable rule.

#A bump allocator10.5

The simplest heap is a bump allocator: a pointer to the first free byte, which each allocation moves forwards. When the pointer passes the end of memory, it grows memory. Nothing is ever freed individually:

(module
  (import "env" "print_i32" (func $print (param i32)))
  (memory 1)
  (global $heap (mut i32) (i32.const 1024))

  ;; allocate $size bytes, aligned to 8
  (func $alloc (param $size i32) (result i32)
    (local $p i32)
    (local $end i32)
    (local.set $p (i32.and (i32.add (global.get $heap) (i32.const 7)) (i32.const -8)))
    (local.set $end (i32.add (local.get $p) (local.get $size)))
    ;; grow memory if the block does not fit
    (if (i32.gt_u (local.get $end) (i32.mul (memory.size) (i32.const 65536)))
      (then
        (if (i32.eq
              (memory.grow
                (i32.shr_u
                  (i32.sub
                    (i32.add (local.get $end) (i32.const 65535))
                    (i32.mul (memory.size) (i32.const 65536)))
                  (i32.const 16)))
              (i32.const -1))
          (then unreachable))))       ;; out of memory
    (global.set $heap (local.get $end))
    (local.get $p))

  (func (export "main")
    (call $print (call $alloc (i32.const 3)))
    (call $print (call $alloc (i32.const 100)))
    (call $print (call $alloc (i32.const 200000)))   ;; needs 3 more pages
    (call $print (memory.size))))

1024
1032
1136
4

Rounding up to a multiple of 8 is the usual (p + 7) & ~7. The amount to grow is the shortfall rounded up to whole pages: add 65,535 and shift right by 16, since a page is 2¹⁶ bytes.

A bump allocator on its own is only right for programs that never free memory, or that free everything at once. That second case covers more than it sounds like. A game can give each frame an arena: allocate freely during the frame, then reset the pointer to where it started when the frame ends, freeing everything in one store. Level loading can use another arena, reset when the level is unloaded.

For general-purpose malloc and free, compilers link in a real allocator, compiled to WebAssembly like any other code. Emscripten uses dlmalloc or its own emmalloc; Rust's standard library uses dlmalloc too. Since memory never shrinks, an allocator's peak usage is what the tab keeps, so fragmentation matters more than usual.

#Null pointers10.6

Since address 0 is valid memory, dereferencing a null pointer does not trap. If your language promises that it will, you have three options:

• check before each dereference, and trap or raise your own error if the pointer is zero. The check is a compare and a branch, cheap but not free;
• make the address of every valid object large and every invalid one small, and rely on the reserved low memory catching the damage, without a guarantee;
• use the garbage-collected references of Chapter 22, where null is a real value and dereferencing it traps, but which do not live in linear memory at all.

Checks that can be proven redundant, such as a second dereference of the same pointer, can be removed by your compiler. Engines will not remove them for you, because they cannot know what the check means.

#Strings, arrays and slices10.7

A dynamically sized array in linear memory is usually represented as a pointer and a length, passed together. With multiple results and multiple parameters, the pair can stay in two locals rather than being stored as a struct:

(module
  (import "env" "print" (func $print (param i32 i32)))
  (memory (export "memory") 1)
  (data (i32.const 100) "  trim me  ")

  ;; return the slice without leading and trailing spaces
  (func $trim (param $p i32) (param $n i32) (result i32 i32)
    (block $done
      (loop $front
        (br_if $done (i32.eqz (local.get $n)))
        (br_if $done (i32.ne (i32.load8_u (local.get $p)) (i32.const 32)))
        (local.set $p (i32.add (local.get $p) (i32.const 1)))
        (local.set $n (i32.sub (local.get $n) (i32.const 1)))
        (br $front)))
    (block $done
      (loop $back
        (br_if $done (i32.eqz (local.get $n)))
        (br_if $done (i32.ne (i32.load8_u (i32.add (local.get $p) (i32.sub (local.get $n) (i32.const 1))))
                             (i32.const 32)))
        (local.set $n (i32.sub (local.get $n) (i32.const 1)))
        (br $back)))
    (local.get $p)
    (local.get $n))

  (func (export "main")
    (call $print (call $trim (i32.const 100) (i32.const 11)))))

trim me

The two results of $trim are exactly the two parameters $print expects, so the call passes them straight through.

#What you have seen10.8

A compiler decides the layout of linear memory: a reserved low area, static data at fixed addresses, a shadow stack for address-taken locals with its pointer in a global, and a heap grown with memory.grow. Struct layout follows whatever rules you choose, and C's are a good default. Allocators are ordinary WebAssembly code, and a bump allocator with per-frame arenas suits games well. Null is a valid address, so null checks are your compiler's job.

The next chapter covers the rest of a module's state: globals and tables.