Un-embed metadata from heap

[Noah-Huppert]

Goal

Currently meta-data about normal sized allocations is stored embedded in the heap right before the 2 KiB of a MiniPage, in the form of MiniPageHeader objects. This complicates a few aspects of design (alignment is harder / impossible, MiniPageHeader objects must be fixed size: future optimizations impossible). To create some freedom in the design MiniPageHeader objects will be moved from before MiniPages to an array in the meta-page.

Design Issues

Maximum Size

Problem

The meta-page is located in the first portion of the heap. Addresses allocated to users start right after the meta-page. So the meta-page must have a fixed size. Therefor the number of MiniPageHeader objects in the array must be fixed to the maximum size.

In WebAssembly the maximum memory size right now is 4 GB. MiniPages are 2 KiB large which means there can be a maximum of 2,097,120 MiniPages.

The problem is that even if each MiniPageHeader was only 1 byte large (they're not, they're much larger), this array would be 2048 KiB large, taking up 32 64 KiB WebAssembly pages best case. More realistically a MiniPageHeader is ~260 bytes, so many more than 32 heap pages. I have implemented allocating an array of this size and of course the program immediately segfaults when trying to allocate the meta-page. This is because it is assumed that a meta-page is smaller than a WebAssembly heap page.

Additionally the WebAssembly community does have aspirations to have more than 4 GB of mememory. So this max number of pages approach will only get worse as WebAssembly grows more powerful.

Proposed Solution

It is likely that many programs use a portion of heap memory, and not the full 4 GB. Some WebAssembly runtimes even max out at 2 GB right now. This means a fixed size array of MiniPageHeader objects in the meta-page would probably remain very empty for most programs. Wasting tons of memory to record details about heap memory that isn't anywhere close to being allocated.

The allocator system can be changed to only record details about currently in use WebAssembly heap pages.

Make each WebAssembly 64 KiB page have its own meta-page (right now there is one global meta-page for everywhere). Which has stacks and a MiniPageHeader array only for the minipages in that WebAssembly heap page's area.

A WebAssembly heap page can fit 32 MiniPages. This would mean the formerly huge MiniPageHeader array in the meta-page would only have 32 entries in a WebAssembly heap page specific meta-page design. This is an acceptable size.

Performance

Problem

This change to having multiple meta-pages would add a linear search into the allocation critical path.

Currently the allocation pops from stacks in the meta-page to retrieve the next free allocation address. With the change from one meta-page to multiple, it is ambiguous which meta-page's stacks to pop from. The allocator would have to start on the first WebAssembly heap page's meta-page, and iterate until it finds a page with free space.

Proposed Solution

To avoid this I propose creating a sort of multi-layer page table style system, with stacks. Similar to how free Minipages are stored on stacks, WebAssembly heap pages with free space could be stored on a stack. Then the program could simply pop from this free WebAssembly page stack and know in constant time which meta-page's stacks to pop from.

These free WebAssembly page stacks would reside within a new "global meta-page". Which would be allocated on the very first WebAssembly heap page. This structure would hold information which is not specific to individual WebAssembly heap pages.

There would be one free WebAssembly heap page stack for each size class. Only WebAssembly heap pages with free space for that size class would be allowed on the stack. When a WebAssembly heap page runs out of space it would be popped off.

[Noah-Huppert]

Additionally, should a ratio between new WebAssembly pages, and re-used WebAssembly pages be kept? Sort of like how the ratio between new and re-used MiniPages is kept?

[Noah-Huppert]

• Update documentation