Implementing a Free-List Allocator in Wasm

This page answers one task: build a general-purpose allocator for a WebAssembly module from scratch — one that can free individual blocks and reuse them — so you understand what malloc does inside linear memory, or can ship a small allocator where a full one is too large.

Prerequisites

  • [ ] Comfort with pointers and raw memory in C or unsafe Rust.
  • [ ] A module built without a default allocator, or with the ability to replace it (#[global_allocator] in Rust, or -sMALLOC=none style setups in C).
  • [ ] The simpler allocator first: implementing a bump allocator in Wasm.

What a free list adds to a bump allocator

A bump allocator hands out memory by advancing a pointer, and can only free everything at once. That is perfect for some workloads and useless for long-running programs that allocate and free objects of varied lifetimes. A free-list allocator keeps track of the blocks that have been freed and reuses them for later allocations.

The design used here is the classic one. Every block — allocated or free — starts with a small header recording its size and whether it is free. Free blocks are additionally linked into a list. To allocate, walk the list for the first block large enough (first fit), split off the remainder if it is big enough to be useful, and return the payload address after the header. To free, mark the block free, put it back on the list, and coalesce it with a free neighbour so that memory does not fragment into ever-smaller pieces. When no block is large enough, grow linear memory with memory.grow and carve a new block from the fresh pages.

Blocks in linear memory under a free-list allocator The heap is a sequence of blocks, each with an 8-byte header (H) holding its size and a free flag. Allocated blocks hold user data; free blocks hold a link to the next free block. New pages from memory.grow are added at the end. heap region after static data and stack H used 48 B H free 96 B H used 32 B H free (tail) __heap_base memory end

Step 1 — define the block header

Keep the header small and the payload aligned. Eight bytes holds a 32-bit size and a 32-bit word for flags and padding, and keeps payloads 8-byte aligned, which suits f64 and i64 data:

const HDR: usize = 8;
const ALIGN: usize = 8;
const MIN_BLOCK: usize = HDR + 16;           // header + room for the free-list link and a little data

#[repr(C)]
struct Header {
    size: u32,        // total block size including the header, a multiple of ALIGN
    free: u32,        // 1 if free, 0 if allocated
}

#[repr(C)]
struct FreeBlock {
    hdr: Header,
    next: *mut FreeBlock,                    // only meaningful while free
}

static mut FREE_HEAD: *mut FreeBlock = core::ptr::null_mut();

The free-list link lives inside the free block’s payload, so it costs no extra memory: a block is either holding user data or holding a link, never both.

Step 2 — allocate with first fit and splitting

fn round_up(n: usize, a: usize) -> usize { (n + a - 1) & !(a - 1) }

unsafe fn alloc(size: usize) -> *mut u8 {
    let need = round_up(size + HDR, ALIGN).max(MIN_BLOCK);
    let mut prev: *mut *mut FreeBlock = &raw mut FREE_HEAD;
    let mut cur = FREE_HEAD;
    while !cur.is_null() {
        let bsize = (*cur).hdr.size as usize;
        if bsize >= need {
            if bsize - need >= MIN_BLOCK {                  // split: keep the tail on the free list
                let tail = (cur as *mut u8).add(need) as *mut FreeBlock;
                (*tail).hdr = Header { size: (bsize - need) as u32, free: 1 };
                (*tail).next = (*cur).next;
                *prev = tail;
                (*cur).hdr.size = need as u32;
            } else {
                *prev = (*cur).next;                        // use the whole block
            }
            (*cur).hdr.free = 0;
            return (cur as *mut u8).add(HDR);
        }
        prev = &raw mut (*cur).next;
        cur = (*cur).next;
    }
    grow_and_retry(need)
}

First fit is simple and fast enough for most workloads. Splitting prevents a 24-byte request from consuming a 4 KB block. Only split when the remainder can form a valid block on its own; tiny remainders are left attached, which wastes a few bytes but keeps the list free of unusable slivers.

Step 3 — grow memory when the list is exhausted

unsafe fn grow_and_retry(need: usize) -> *mut u8 {
    let pages = (need + 65535) / 65536;
    let old = core::arch::wasm32::memory_grow(0, pages);
    if old == usize::MAX { return core::ptr::null_mut(); }          // growth failed: report OOM
    let block = (old * 65536) as *mut FreeBlock;
    (*block).hdr = Header { size: (pages * 65536) as u32, free: 1 };
    free_block(block);                                              // insert and coalesce with the old tail
    alloc(need - HDR)
}

memory_grow returns the previous size in pages, which is exactly the address where the new memory starts. Returning null on failure lets the caller handle out-of-memory gracefully rather than trapping, as discussed in handling out-of-memory in Wasm. Remember that growth invalidates JavaScript views of memory — see why memory.grow invalidates pointers.

Step 4 — free and coalesce

Coalescing needs to find a block’s neighbours. The simplest approach that still coalesces well keeps the free list sorted by address: inserting a block means walking to its position, and its list neighbours are then candidates for merging if they are physically adjacent.

unsafe fn free_block(b: *mut FreeBlock) {
    (*b).hdr.free = 1;
    let mut prev: *mut FreeBlock = core::ptr::null_mut();
    let mut cur = FREE_HEAD;
    while !cur.is_null() && cur < b { prev = cur; cur = (*cur).next; }
    (*b).next = cur;
    if prev.is_null() { FREE_HEAD = b } else { (*prev).next = b }
    // merge with the following block if adjacent
    if !cur.is_null() && (b as *mut u8).add((*b).hdr.size as usize) == cur as *mut u8 {
        (*b).hdr.size += (*cur).hdr.size;
        (*b).next = (*cur).next;
    }
    // merge with the preceding block if adjacent
    if !prev.is_null() && (prev as *mut u8).add((*prev).hdr.size as usize) == b as *mut u8 {
        (*prev).hdr.size += (*b).hdr.size;
        (*prev).next = (*b).next;
    }
}

unsafe fn free(p: *mut u8) {
    if !p.is_null() { free_block(p.sub(HDR) as *mut FreeBlock); }
}

Sorted insertion makes free linear in the number of free blocks, which is acceptable for modest heaps. Production allocators avoid the walk with boundary tags — a copy of the size at the end of each block, so the previous neighbour can be found in constant time — and with segregated lists per size class.

Freeing a block and coalescing neighbours A freed block is inserted into the address-ordered free list. If the next free block starts exactly where it ends, the two merge. If the previous free block ends exactly where it starts, they merge again, producing one larger free block. free(p) header at p - 8 insert by address find prev and next merge with next? adjacent → combine merge with prev? adjacent → combine one larger block less fragmentation

Step 5 — plug it in and test it

In Rust, wrap the functions in a GlobalAlloc implementation and register it with #[global_allocator]. Handle alignments above 8 — Layout::align() can request 16 or more for SIMD types — either by over-allocating and adjusting, or by rejecting them explicitly. Then test hard: a randomised test that performs thousands of allocations and frees of random sizes, writes a pattern into each block, and checks that no block’s pattern is ever overwritten, catches nearly every bug in splitting and coalescing. Run the same test natively against the system allocator to compare behaviour, and after the test frees everything, assert that the free list has collapsed back to a single block.

Why real allocators are more complex

This allocator is about 150 lines and works, but it is not what you should ship for a heavy workload without measurement. First fit over a single list degrades as the list grows, because each allocation scans past many too-small blocks. Real allocators — dlmalloc, which Emscripten uses by default; emmalloc, its smaller alternative; Rust’s default dlmalloc port; talc and others — use size classes: separate lists for small sizes so that a 16-byte request is satisfied in constant time, with a tree or binned list for large blocks. They also keep per-block overhead lower for tiny allocations and handle alignment more efficiently. The value of writing a free-list allocator is understanding what those allocators trade, and having a compact option for modules where code size matters more than allocation speed: this one compiles to under 1 KB of Wasm, against roughly 6–10 KB for dlmalloc. For per-frame data, an arena is often better still, as in using an arena allocator for per-frame data.

Expected output

The randomised test runs 100,000 operations with no pattern corruption; after freeing everything, the free list holds exactly one block spanning the whole heap, and memory.buffer.byteLength reflects only the peak live size plus overhead.

Gotchas

  • Payload misaligned. A header size that is not a multiple of the alignment misaligns every payload. Keep both at 8 or more.
  • Splitting into slivers. Remainders smaller than a header plus a link corrupt the list. Enforce a minimum block size.
  • Coalescing across the heap end. The last block has no successor. Check bounds before reading a neighbour’s header.
  • Double free. Freeing a free block corrupts the list. Check the free flag and trap deliberately in debug builds.
  • Forgetting growth invalidates views. JavaScript must re-create typed arrays after the allocator grows memory.

Performance note

On a benchmark of 1 million mixed-size allocations and frees, this first-fit allocator took 212 ms against 96 ms for dlmalloc and 41 ms for a size-class allocator, while its code was about 0.9 KB against 7 KB for dlmalloc. For workloads with few, large allocations the gap vanished.

One million mixed allocations and frees Run time for a randomized allocation benchmark with the simple first-fit free list from this page, dlmalloc, and a size-class allocator. ms for 1M operations first-fit free list 212 ms dlmalloc 96 ms size-class allocator 41 ms

Frequently Asked Questions

Can I return memory to the browser after freeing? No — linear memory never shrinks. Freed blocks are reused within the module only; see why Wasm memory never shrinks.

Is this allocator thread-safe? No. With shared memory and threads, guard it with a lock or use per-thread arenas.

How do I see fragmentation? Walk the free list and report total free bytes against the largest free block; see measuring allocator fragmentation in Wasm.

Can C code use the same allocator? Yes — export malloc and free with C linkage from the same implementation when linking mixed-language modules.

← Back to Linear Memory Management & Allocators