rulloc/lib.rs
1//! General purpose memory allocator. Memory regions are requested from the
2//! underlying kernel using
3//! [`mmap`](https://man7.org/linux/man-pages/man2/mmap.2.html) syscalls on
4//! Unix platforms and
5//! [`VirtualAlloc`](https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc)
6//! on Windows platforms. This is how the allocator looks like internally:
7//!
8//! ```text
9//! Next Free Block Next Free Block
10//! +------------------------------------+ +-----------------------+
11//! | | | |
12//! +--------+-------|----------------+ +--------+---|---|-----------------------|-----+
13//! | | +-----|-+ +-------+ | | | +-|---|-+ +-------+ +---|---+ |
14//! 0 -> | Region | | Free | -> | Block | | ---> | Region | | Free | -> | Block | -> | Free | |
15//! | | +-------+ +-------+ | | | +-------+ +-------+ +-------+ |
16//! +--------+------------------------+ +--------+-------------------------------------+
17//!
18//! Next Free Block
19//! +----------------------------------------+
20//! | |
21//! +--------+------------------|-----+ +--------+------------------|------------------+
22//! | | +-------+ +---|---+ | | | +-------+ +---|---+ +-------+ |
23//! 1 -> | Region | | Block | -> | Free | | ---> | Region | | Block | -> | Free | -> | Block | |
24//! | | +-------+ +-------+ | | | +-------+ +-------+ +-------+ |
25//! +--------+------------------------+ +--------+-------------------------------------+
26//!
27//! ..............................................................................................
28//!
29//! Next Free Block
30//! +---------------------------+
31//! | |
32//! +--------+------------------|-----+ +--------+-----|-------------------------------+
33//! | | +-------+ +---|---+ | | | +---|---+ +-------+ +-------+ |
34//! N -> | Region | | Block | -> | Free | | ---> | Region | | Free | -> | Block | -> | Block | |
35//! | | +-------+ +-------+ | | | +-------+ +-------+ +-------+ |
36//! +--------+------------------------+ +--------+-------------------------------------+
37//! ```
38//!
39//! The allocator contains multiple buckets, each bucket contains a list of
40//! regions and each region stores a list of memory blocks. Implemented
41//! optimizations:
42//!
43//! - **Block coalescing**: merge adjacent free blocks into one bigger block.
44//! - **Block splitting**: blocks that are too big are split in two blocks.
45//! - **Free list**: linked list of only free blocks, finds free blocks faster.
46//! - **In place reallocations**: if possible, avoid creating new memory blocks.
47//! - **Fixed size buckets**: reduce fragmentation by grouping allocation sizes.
48//!
49//! See [`Rulloc`] for usage examples.
50
51#![feature(allocator_api)]
52#![feature(alloc_layout_extra)]
53#![feature(is_some_and)]
54#![feature(nonnull_slice_from_raw_parts)]
55#![feature(strict_provenance)]
56#![feature(slice_ptr_get)]
57
58use std::{alloc::AllocError, ptr::NonNull};
59
60mod alignment;
61mod allocator;
62mod block;
63mod bucket;
64mod freelist;
65mod header;
66mod list;
67mod platform;
68mod realloc;
69mod region;
70
71/// Non-null pointer to `T`. We use this in most cases instead of `*mut T`
72/// because the compiler will yell at us if we don't write code for the `None`
73/// case. I think variance doesn't have much implications here except for
74/// [`list::LinkedList<T>`], but that should probably be covariant anyway.
75pub(crate) type Pointer<T> = Option<NonNull<T>>;
76
77/// Shorter syntax for allocation/reallocation return types.
78pub(crate) type AllocResult = Result<NonNull<[u8]>, AllocError>;
79
80pub use allocator::Rulloc;