MemAlloc

A custom, thread-safe, general-purpose memory allocator written in Rust.

MemAlloc is cross-platform and it implements the GlobalAlloc trait.

The memory is managed directly from the operating system using mmap syscalls on Unix and VirtualAlloc on Windows.

Run the examples:

cargo run --example basic
cargo run --example global

Run the tests:

cargo test

Internal Structure

The internals of the allocator work all behind the following core Data Structures. All the source code is fully documented, including ASCII diagrams if you want further detail. For a deep dive into the codebase, the best point to start is src/memalloc.rs, you can follow the rest by reading the documentation and using the intra-doc links.

Region & Block

Memory is requested from the OS kernel in large chunks called Regions. Each region is a linked list of Blocks. A block contains a header (with all its metadata) and a payload (user memory).

+-----------------------------------------------+
|        | +-------+    +-------+    +-------+  |
| Region | | Block | -> | Block | -> | Block |  |
|        | +-------+    +-------+    +-------+  |
+-----------------------------------------------+

FreeList

To avoid iterating over every single block during allocation, we mantain a separate Free List.

                                   Free List

                    Next free block                Next free block
               +----------------------+  +--------------------------------------+
               |                      |  |                                      |
+--------------|----------------------|--|----+      +--------------------------|-----+
|        | +---|--+    +-------+    +-|--|-+  |      |        | +-------+    +--|---+ |
| Region | | Free | -> | Block | -> | Free |  | ---> | Region | | Block | -> | Free | |
|        | +------+    +-------+    +------+  |      |        | +-------+    +------+ |
+---------------------------------------------+      +--------------------------------+