rulloc 0.1.0

General purpose memory allocator
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

//! General purpose memory allocator. Memory regions are requested from the
//! underlying kernel using
//! [`mmap`](https://man7.org/linux/man-pages/man2/mmap.2.html) syscalls on
//! Unix platforms and
//! [`VirtualAlloc`](https://learn.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-virtualalloc)
//! on Windows platforms. This is how the allocator looks like internally:
//!
//! ```text
//!                                  Next Free Block                    Next Free Block
//!                       +------------------------------------+   +-----------------------+
//!                       |                                    |   |                       |
//!      +--------+-------|----------------+      +--------+---|---|-----------------------|-----+
//!      |        | +-----|-+    +-------+ |      |        | +-|---|-+    +-------+    +---|---+ |
//! 0 -> | Region | | Free  | -> | Block | | ---> | Region | | Free  | -> | Block | -> | Free  | |
//!      |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
//!      +--------+------------------------+      +--------+-------------------------------------+
//!
//!                                               Next Free Block
//!                                  +----------------------------------------+
//!                                  |                                        |
//!      +--------+------------------|-----+      +--------+------------------|------------------+
//!      |        | +-------+    +---|---+ |      |        | +-------+    +---|---+    +-------+ |
//! 1 -> | Region | | Block | -> | Free  | | ---> | Region | | Block | -> | Free  | -> | Block | |
//!      |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
//!      +--------+------------------------+      +--------+-------------------------------------+
//!
//! ..............................................................................................
//!
//!                                         Next Free Block
//!                                  +---------------------------+
//!                                  |                           |
//!      +--------+------------------|-----+      +--------+-----|-------------------------------+
//!      |        | +-------+    +---|---+ |      |        | +---|---+    +-------+    +-------+ |
//! N -> | Region | | Block | -> | Free  | | ---> | Region | | Free  | -> | Block | -> | Block | |
//!      |        | +-------+    +-------+ |      |        | +-------+    +-------+    +-------+ |
//!      +--------+------------------------+      +--------+-------------------------------------+
//! ```
//!
//! The allocator contains multiple buckets, each bucket contains a list of
//! regions and each region stores a list of memory blocks. Implemented
//! optimizations:
//!
//! - **Block coalescing**: merge adjacent free blocks into one bigger block.
//! - **Block splitting**: blocks that are too big are split in two blocks.
//! - **Free list**: linked list of only free blocks, finds free blocks faster.
//! - **In place reallocations**: if possible, avoid creating new memory blocks.
//! - **Fixed size buckets**: reduce fragmentation by grouping allocation sizes.
//!
//! See [`Rulloc`] for usage examples.

#![feature(allocator_api)]
#![feature(alloc_layout_extra)]
#![feature(is_some_and)]
#![feature(nonnull_slice_from_raw_parts)]
#![feature(strict_provenance)]
#![feature(slice_ptr_get)]

use std::{alloc::AllocError, ptr::NonNull};

mod alignment;
mod allocator;
mod block;
mod bucket;
mod freelist;
mod header;
mod list;
mod platform;
mod realloc;
mod region;

/// Non-null pointer to `T`. We use this in most cases instead of `*mut T`
/// because the compiler will yell at us if we don't write code for the `None`
/// case. I think variance doesn't have much implications here except for
/// [`list::LinkedList<T>`], but that should probably be covariant anyway.
pub(crate) type Pointer<T> = Option<NonNull<T>>;

/// Shorter syntax for allocation/reallocation return types.
pub(crate) type AllocResult = Result<NonNull<[u8]>, AllocError>;

pub use allocator::Rulloc;