Skip to content

DLMalloc for Gear Programs

Jump to bottom
Gregory Sobol edited this page Apr 30, 2026 · 1 revision

Table of Contents

Introduction

Almost every Gear program is a self-contained WebAssembly module that runs inside a sandbox. Inside that sandbox the program needs a working allocator: most data structures used by gstd and Sails — Box, Vec, String, decoded payloads, intermediate buffers — eventually call GlobalAlloc::alloc and GlobalAlloc::dealloc (some short-lived values can live on the stack, but the heap-bound ones dominate). Whatever sits behind GlobalAlloc therefore runs in almost every program execution that uses the Gear support libraries, and its behaviour directly shapes:

  • how much linear memory the program holds,
  • how often the executor pages memory in (lazy-pages),
  • how big the post-execution state diff turns out to be, and
  • how much computation the host charges for memory growth.

Gear ships its own fork of dlmalloc-rs, called gear-dlmalloc. The crate started as a thin port of Doug Lea's classic dlmalloc, but by now most of the code has been rewritten and re-shaped specifically for Gear programs running on WASM. This article walks through the differences and explains why each one is there.

The reference implementation we compare against is upstream dlmalloc-rs — the same allocator the Rust standard library uses for wasm32-unknown-unknown.

Why a fork at all?

The natural question is:

Why not just use upstream dlmalloc-rs?

The upstream WASM backend, dlmalloc-rs/src/wasm.rs, is brutally honest about its environment. Its alloc is implemented on top of wasm::memory_grow, and all of its release primitives are no-ops: free returns false, free_part returns false, remap returns null, can_release_part returns false. The reason is structural — in plain WASM there is no way to give memory back. memory.grow only grows; the linear memory monotonically expands until the module dies. The allocator can recycle freed chunks internally, but it can never tell the host "I no longer need these 64 KiB".

For a Gear program this is a serious problem:

  • Every executor that re-runs the program has to materialize the entire grown memory, even if 99% of it is dead.
  • Lazy-pages charges gas for accessed pages. Pages that the program no longer uses still sit in the linear memory, and may still be touched by the next allocation.
  • Large transient allocations (e.g. decoding a big payload, building a temporary tree, then dropping it) leave a permanent footprint.

The Gear runtime, on the other hand, can free pages: its lazy-pages subsystem is page-granular, and host-side it owns the storage namespace for each program's memory. So we expose two host functions to the WASM program — alloc and free_range — and we want an allocator that uses them.

That is what gear-dlmalloc does.

The host interface

gear_core::alloc and gear_core::free_range

The whole WASM backend of gear-dlmalloc lives in src/wasm.rs. It boils down to two host imports:

  • gear_core::alloc(pages: u32) -> u32 — asks the host for that many WASM pages and returns the page index of the first granted page (or u32::MAX on failure).
  • gear_core::free_range(start: u32, end: u32) -> i32 — tells the host that pages in the inclusive range [start, end] no longer belong to this program.

The page size is fixed at 64 KiB, identical to the WASM page size, and the allocator's granularity is fixed at the same value. There are two important properties to notice:

  1. alloc returns a page number, not a byte offset. The host owns the page allocation policy: it can hand out non-contiguous pages, reuse pages that were freed earlier, etc. From the allocator's point of view, the returned page index times 64 KiB is just "the segment base address".
  2. free_range is a real free. It tells the host that those pages can be evicted from lazy-pages, dropped from the state diff, or reused for the next allocation.

Compare this to upstream's wasm::memory_grow-only model: there, the allocator's free is forever a no-op. Here, free is genuinely able to give pages back, and the rest of the allocator is designed to find and surface those page-aligned, releasable holes whenever possible. We will see how in Free flow.

Preinstalled memory and __heap_base

A WASM module starts with linear memory already populated by the linker: stack, static data, etc. Just past the static data the linker exports a magic global called __heap_base — the first byte the program is allowed to use as heap. In a typical wasm-allocator setup the partial WASM page that contains __heap_base is wasted: memory.grow only grants whole pages, so the bytes between __heap_base and the next page boundary go unused.

gear-dlmalloc does not waste it. On the very first allocation request, the allocator computes the residual range between __heap_base and the next page boundary and registers it as the very first segment of the allocator. For small programs that residual region (typically several KiB) is enough to satisfy the first wave of allocations without ever growing memory. For larger programs it just becomes the initial top of the heap, merged with the next host segment when that segment turns out to be adjacent.

A note on lineage: upstream dlmalloc-rs has since picked up a similar "pre-existing chunk from the linker" optimisation, but gear-dlmalloc shipped this earlier — it has been part of the Gear backend since long before upstream added its variant.

This is one of those small differences that you only notice in aggregate: tiny short-lived programs may complete their entire life cycle without a single host alloc call.

Allocator state

The data layout in gear-dlmalloc follows the spirit of Doug Lea's allocator — boundary tags, free-chunk indexing structures — but the on-memory shapes have been changed to match WASM realities. Let's walk through the parts that we actually changed.

Chunks

A chunk is the unit the allocator hands out. A chunk header sits just before the user memory:

chunk beg       head
         \     /
          [-][-][-----------------]
          /      \
prev_chunk_size   chunk memory begin = chunk beg + CHUNK_MEM_OFFSET

In Rust:

#[repr(C)]
struct Chunk {
    prev_chunk_size: usize,   // size of previous chunk in memory
    head:            usize,   // size of this chunk + flag bits
    prev: *mut Chunk,         // list links, only valid when free
    next: *mut Chunk,
}

Three flags live in the low bits of head:

bit meaning
PINUSE previous chunk in memory is in use (or there is no previous chunk)
CINUSE this chunk is in use
FLAG4 identifies the segment border chunk (described below)

MALIGN = 2 * size_of::<usize>(). The lower bits of every chunk address are zero, so they are reused for the flags above.

A subtle but important trick: when the previous chunk is in use, its prev_chunk_size field is dead, and the allocator lets the previous chunk's user memory overlap into it:

chunk1 beg            chunk1 end    chunk2 beg
         \                      \  /
          [-][-][----------------][-][-][-------------]
                |                    \
                chunk1 mem beg        chunk1 mem end

That is why the header overhead is just one usize per chunk in the common case, not two. The same trick exists in upstream dlmalloc; we keep it because it directly reduces the heap footprint of small allocations.

Half-chunks

Standard dlmalloc enforces a minimum chunk size of MIN_CHUNK_SIZE = sizeof(Chunk) = 4 * usize, because below that you cannot even fit the free-list pointers. But during cropping (e.g. carving a 24-byte request out of a 32-byte chunk) you may end up with a MALIGN-sized leftover that is too small to be a normal free chunk.

Upstream merges the leftover back into the parent chunk (so the user gets a slightly bigger chunk). gear-dlmalloc introduces an explicit notion of a half-chunk:

A free chunk of exactly MALIGN bytes that is not in any free-chunk index, but is recognised by the boundary-tag machinery and gets merged the next time a neighbour goes free.

chunk for allocation                    chunk end    free half chunk
|                                                \  /
[--(----------------------------------------------][-)-]
   |                                                 |
   requested mem begin                      requested mem end

The benefit is purely WASM-shaped: it keeps the user-visible chunk size as small as the request needs, which means tighter packing inside a 64 KiB host page, which means fewer pages need to be touched when iterating over a small allocation. It does cost an extra header word, but in our workloads this trades very favourably against an extra page fault.

Segments and the border chunk

gear-dlmalloc calls a contiguous run of host-backed memory a segment. Each segment carries its metadata at the end of its own memory, in two reserved chunks:

                            Border chunk begin    Border chunk end
                                              \       /   and seg end
[-----------------------------------][----(----][--)--]
|                                   /      \        \
Segment begin       Seg info chunk beg    Seg info beg \
                                                       Seg info end

The first reserved chunk stores the segment metadata (base, size, link to the next segment) inside its user payload and is permanently in use. The second is a one-word border chunk with a special head value that the boundary-tag walk uses as a sentinel: walking forward through the segment we always stop the moment we land on a chunk whose head matches the border pattern. There is no "is this the last segment?" branch in the hot path — the sentinel handles it.

gear-dlmalloc also enforces a strong invariant on the segment list:

No two segments may be neighbours in memory. If a freshly allocated segment is adjacent to an existing one, they are merged immediately.

This invariant matters because the free path (next sections) splits segments around released holes. Without the "no adjacent segments" rule the segment list would slowly accumulate fragments and break iteration assumptions.

The rest of the in-memory structure — the free-chunk indexing arrays, the allocator-context struct — is taken from upstream dlmalloc and is left mostly unchanged. The interesting Gear-specific pieces are the ones above plus the static buffer below.

The static buffer (sbuff)

Before the first segment exists, the allocator has nowhere to put a chunk header. Upstream dlmalloc handles this by greedily growing the very first system segment. gear-dlmalloc adds a different tier in front:

The Dlmalloc struct embeds a small sbuff buffer, partitioned into a handful of fixed-size cells. Tiny allocations served from sbuff cost zero host calls and zero chunk overhead.

The cell layout is fixed at compile time — five cells of sizes 1·MALIGN, 1·MALIGN, 6·MALIGN, 6·MALIGN, 8·MALIGN. A bitmask in the allocator state tracks which cells are occupied.

When malloc(size) is called and there is no segment yet, the allocator first looks for a free cell whose size satisfies the request and returns a pointer into that cell. Only if no cell fits does it fall through to the regular path and, eventually, ask the host for memory.

free and realloc carry symmetric branches: if the pointer falls inside the sbuff range, it is treated as an sbuff slot, never as a chunk. realloc even has a fast path that returns the same pointer if the existing cell is large enough.

The sbuff exists for two reasons specific to Gear:

  1. First-allocation latency. In a typical Gear program the very first allocation happens during init — gstd setting up its message buffer, Sails decoding the input. Without sbuff, that allocation triggers a host alloc call. With sbuff, it does not.
  2. Host-call avoidance for short-lived programs. Some programs (e.g. simple proxy or BLS verification calls) literally allocate a few small buffers, do their job, and exit. With sbuff plus the preinstalled-memory trick, they can complete without any host alloc call at all.

The buffer is sized conservatively (it lives inside the global Dlmalloc instance, so it permanently occupies static memory). The packed compile-time encoding is what keeps the cost in code size and runtime indexing low.

Allocation flow

Putting it all together, Dlmalloc::malloc(size) does the following, in priority order:

  1. sbuff fast path. If no segment has been created yet and size fits a free sbuff cell, satisfy the request from the cell.
  2. Reuse a known free chunk. Search the allocator's free-chunk index for the most suitable existing free chunk. This is the standard upstream-dlmalloc behaviour: best-fit on the appropriate index, with fast paths for small sizes.
  3. Ask the host. If no free chunk fits, call sys_alloc:
    • if the preinstalled __heap_base segment has not been initialised yet, do that and try again from it;
    • otherwise call gear_core::alloc for a granularity-aligned amount;
    • if the new segment turns out to be adjacent to an existing one, merge them on the spot;
    • carve the request out of the new segment.

Compared to upstream dlmalloc the high-level shape is similar; the differences are:

  • No mmap path. Standard dlmalloc has a separate code path for "very large" requests that goes straight to mmap. We removed it: there is no mmap analogue on WASM, and the host-side cost model treats every allocation the same. Every chunk lives in a segment; there are no "loose" mmapped chunks.
  • No footers. Upstream has optional chunk footers used for security/consistency checks. They cost an extra word per chunk and are dead weight in our deterministic, single-instance setting.
  • No morecore. Upstream tries morecore (sbrk-like) before falling back to mmap. We have neither, so the entire branch is gone.
  • Granularity is fixed at 64 KiB. No runtime tuning at all.

The result is roughly 2,700 lines of allocator code in gear-dlmalloc versus ~6,300 lines in the original dlmalloc.c, with all of the omitted code being functionality that does not apply to a single-threaded sandbox-bound Gear program.

Free flow: actually returning pages to the host

This is the section most different from anything you can do in plain WASM.

Splitting a segment around a hole

When the user calls free(mem), three things happen:

  1. sbuff fast path. If mem falls inside the sbuff range, just clear the cell bit and return. Done.
  2. Coalesce. Convert mem to its chunk and merge with any free neighbours on either side. After this step we have a single, maximal free chunk.
  3. Try to release pages to the host. This is the interesting part.

A coalesced free chunk has the layout:

Segment begin                   Can be freed by host           Segment end
|                                  /              \                 |
[=========================(=======|================|====)===========]
                          |                             |
                          Chunk begin                   Chunk end

We want to find the largest page-aligned, page-multiple sub-range of the chunk that we can hand back to the host with free_range. Two complications:

  • The chunk header itself is not page-aligned in general.
  • The segment metadata at the end of the segment must survive (or be re-created in a new segment).

The allocator does this by:

  • reserving one machine word at the start of the candidate range, because the previous in-use chunk may be using the next chunk's prev_chunk_size slot as overlap memory (the trick from Chunks);
  • reserving room for a fresh segment-info pair at the start of the candidate range as well, in case a "before" segment will need to be created;
  • if the chunk reaches all the way to the end of the segment, allowing the trailing segment-info chunk to be released too;
  • rounding the resulting interval to whole pages on both ends.

If, after all that, the page-aligned sub-range is non-empty, the allocator now does the most distinctive part of gear-dlmalloc:

It splits the segment around the hole.

before:
[=========================(=======|================|====)===========]

after:
[==========(=========]                              [==(=)===========]
   seg1                                                 seg2

The two leftover regions become two independent segments, each with their own freshly written segment-info + border chunks. The freed pages are no longer covered by any segment, so the allocator will never touch them again — and the host has been told, via free_range, that those page indices are gone.

Each side is handled independently. If only one side has a remainder, only one new segment is produced and the old segment-info structure is repurposed.

Three subtle invariants make this work:

  • Word reserve at the beginning. The previous in-use chunk may still be reading into the freed region's first word; we must not free that word.
  • Segment-info reserve at the beginning. If we are creating a "before" segment, we need room at its end for its own segment-info pair.
  • No-adjacent-segments rule. The pre-existing invariant from Segments guarantees that the new "before"/"after" segments cannot end up adjacent to anything else, so no further merge work is needed.

If the page-aligned sub-range turns out to be empty (the chunk is too small or too unaligned to release any whole page), the allocator falls back to inserting the chunk into the free-chunk index — exactly the upstream behaviour.

The net effect: for any free that touches at least one full page worth of contiguous freed space, that page goes back to the host on the spot. No madvise(MADV_DONTNEED) heuristics, no "release every N frees" rate limiter; the release is exact and immediate.

This is what makes gear-dlmalloc interact well with lazy-pages. A program that decodes a 1 MB payload, processes it, and drops the decoded representation will, in upstream dlmalloc-rs, hold those 16 pages forever. In gear-dlmalloc it gives them back the moment the last chunk is freed.

Realloc

Realloc handles the following cases, in this order:

  1. Pointer is inside sbuff. If the existing cell is big enough, return it unchanged. Otherwise free the cell, malloc fresh, and copy.
  2. Same size. Return the same pointer.
  3. Smaller than before. Crop the chunk in place and free the trailing remainder, which goes through the same coalesce-and-release machinery and may release pages.
  4. Larger than before, but the next chunk is free and big enough. Eat the next chunk in place, possibly leaving a small free remainder. No copy.
  5. None of the above. Plain malloc + copy + free.

Case 4 is the most useful one in practice: Vec::push patterns where the next chunk happens to still be free turn into in-place growth without ever calling the host. Case 3 is the case where realloc actually returns memory to the host — uncommon in upstream dlmalloc-rs, but on a Gear program it happens whenever a Vec::shrink_to_fit (or similar) crosses a page boundary.

There is no remap path. WASM has no mremap, and the host's alloc/free_range ABI does not provide one either.

Memalign

memalign(align, size) for align > MALIGN is implemented the standard dlmalloc way: allocate a chunk of size req_size + align, round the user pointer up to align, and crop the original chunk so the cropped chunk starts at the aligned address. The "before" remainder (if any) becomes a free chunk; the "after" remainder (if any) is run through coalesce-and-release and may release pages. Both remainders are inserted into the free-chunk index like any other free chunk.

What the upstream allocator has and we removed

Most of the differences boil down to a single observation: upstream dlmalloc-rs carries options for an OS-style backend that none of us has on WASM. We removed:

  • the mmap path for very large requests,
  • the morecore/sbrk path,
  • chunk footers and the security/consistency machinery built on top of them,
  • runtime-tunable parameters such as granularity and trim threshold,
  • the multi-thread mutex (replaced with a no-op — one program, one thread),
  • enable_alloc_after_fork (no fork),
  • the generic Allocator trait abstraction (the backend is selected at compile time and there is only ever one per target),
  • the memory_grow-only WASM backend (replaced with the host imports alloc and free_range).

In their place, gear-dlmalloc adds the four pieces this article walks through: reusing the __heap_base half-page, the static sbuff buffer, half-chunks, and segment splitting on free.

The result is an allocator that is smaller than upstream dlmalloc-rs in feature surface but slightly larger in source lines, because the segment-splitting machinery and the various fast paths each contribute their own logic.

Conclusion

Plain dlmalloc-rs on WASM is a one-way valve: linear memory only ever grows, freed chunks are recycled internally but never returned, and the allocator has no way to interact with anything below itself.

gear-dlmalloc is shaped around a different premise: the host actually owns the memory, and the program is a guest that should ask for pages and give them back. Concretely:

  • The WASM backend talks to the host via two imports, gear_core::alloc(pages) and gear_core::free_range(start, end), instead of wasm::memory_grow.
  • The half-page between the linker's __heap_base and the next page boundary is reclaimed and used as the initial heap.
  • A small static buffer (sbuff) inside the Dlmalloc struct serves the very first wave of tiny allocations without any host call.
  • Free turns into a real page release: the allocator splits the surrounding segment into "before hole" and "after hole" segments and tells the host to forget the pages in the middle.

Together these changes line dlmalloc up with how Gear actually charges and stores program memory: lazy-pages charges per touched page, the post-execution state diff is per-page, and program re-execution rematerialises memory page-by-page. Every WASM page that the allocator can give back is gas saved and bytes saved on every subsequent execution of the same program.

In summary, gear-dlmalloc keeps the well-understood structure of Doug Lea's allocator — boundary tags, free-chunk indexing, in-place coalescing — and replaces just the parts that assumed an OS-style backend. The result is a smaller, simpler, page-honest allocator that fits the Gear WASM execution model rather than fighting it.

Clone this wiki locally