noah-huppert / alligator-wasm-alloc Goto Github PK
View Code? Open in Web Editor NEWReal-time memory allocator built for WebAssembly, written in Rust.
Real-time memory allocator built for WebAssembly, written in Rust.
I ran the fuzzer for 2 hours on the week6 release and got 21 unique crashes. Horray! Lets fix these.
crashes.tar.gz
Even if the allocator is still in Alpha there should be an easy way to use it.
There is WebAssembly threads proposal which defines a shared
parameter on a WebAssembly memory.
This seems to be playing with the idea that WebAssembly memory instructions make you specify a memory ID. So in the future maybe shared and non shared memories could exist together.
Having a flag which indicates if the memory is shared sounds convenient for an allocator to know.
Allocate the MetaPage on program startup.
To be more aligned with the mission of Alligator to be real time.
Unsure if this is needed. As the runtime for a Rust WASM program allocates a bunch of stuff before the program runs. So this actually probably does allocate the MetaPage at start-up.
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.
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.
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.
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.
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.
I was reading through the readme and found a couple places which said "KB" instead of "KiB". Make sure tiny things like that are all correct.
Try to compile some program which includes the allocator init object as a start. Maybe later tests can be added.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.