Skip to main content

kevy_alloc/
lib.rs

1//! `kevy-alloc` — a per-shard, mmap-backed, header-free allocator.
2//!
3//! # Why this exists
4//!
5//! Tiering holds kevy's *logical* memory at its budget, but resident
6//! memory ran 2.24× that bound on ~400 B values and 1.65× on 4 KiB ones.
7//! The cause is not tuning: glibc's `brk` arena only shrinks from the
8//! top, so a freed chunk under a live one is a page the OS never gets
9//! back. `malloc_trim(0)` and `MALLOC_ARENA_MAX=2` were both measured
10//! and both moved it by nothing
11//! (the resident-set fragmentation finding measured both no-ops).
12//!
13//! For the small companies kevy is aimed at, RAM is the budget line, so
14//! that ratio decides how much business fits on the box they already
15//! have.
16//!
17//! # What we get from a narrower contract
18//!
19//! A general-purpose allocator serves C's `free(ptr)`, which carries no
20//! size, so it must store one beside every chunk — and those interleaved
21//! headers are part of why the heap cannot shrink. Rust hands us the
22//! `Layout` on deallocation. **This allocator serves sized deallocation
23//! only, so it stores no headers at all**: a pointer's segment, span and
24//! class are recovered by masking the address (see [`segment`]).
25//!
26//! # Status
27//!
28//! The kevy server's allocator: since 7.0 the server binary installs
29//! `KevyAlloc` (the `global` feature) as its global allocator by default, and builds on the
30//! system allocator only with `--no-default-features`.
31//!
32//! # Standing on shoulders, and where we step off
33//!
34//! - **mimalloc** — segment/page geometry, and the push-only thread-free
35//!   list that makes cross-thread frees ABA-free by construction.
36//! - **tcmalloc** — graded size classes; see [`class`] for why eight
37//!   subdivisions per octave rather than four.
38//! - **Go runtime** — span ownership, and heap accounting as a
39//!   first-class exported thing rather than a debug aid.
40//! - **mimalloc** — the purge delay: a free page goes back to the OS only
41//!   after it has gone unused for a while, so memory reused within it is
42//!   never faulted back in (see [`PURGE_DELAY`]).
43//! - **torajs-mmalloc** — a working mmap-backed realisation of all of
44//!   the above, plus two lessons it paid for: a missing per-class cap is
45//!   a SIGSEGV rather than a leak, and a cutover without a fast path
46//!   costs 10–30 ns per allocation.
47//!
48//! The step off: those allocators put a thread cache in front of a
49//! shared heap because they cannot know how threads relate to memory.
50//! kevy pins a shard per core, so the heap *is* thread-local and the
51//! fast path is already atomic-free. See [`heap`].
52//!
53//! # Example
54//!
55//! ```
56//! # use kevy_alloc::Heap;
57//! let mut heap = Heap::new(0);
58//! if let Some(p) = heap.alloc(400, 8) {
59//!     // SAFETY: `p` came from this heap with this size and alignment.
60//!     unsafe { heap.dealloc(p, 400, 8) };
61//! }
62//! let stats = heap.snapshot();
63//! assert!(stats.balanced(), "every mapped byte must be accounted for");
64//! ```
65
66// The `global` feature needs thread-local storage, which is a `std`
67// facility; the core allocator itself is `core`-only.
68#![cfg_attr(all(not(test), not(feature = "global")), no_std)]
69#![warn(missing_docs)]
70
71pub mod class;
72#[cfg(feature = "global")]
73pub mod global;
74pub mod heap;
75pub mod large;
76pub mod os;
77mod outbound;
78pub mod pagemap;
79mod purge;
80mod reclaim;
81mod rtree;
82pub mod segment;
83mod snapshot;
84mod spanlist;
85pub mod stats;
86mod tally;
87
88#[cfg(feature = "global")]
89pub use global::{KevyAlloc, thread_reclaim, thread_stats};
90pub use heap::{Heap, PER_CLASS_CAP};
91pub use large::large_stats;
92pub use purge::PURGE_DELAY;
93pub use stats::Stats;
94
95// Send and Sync are part of the public contract: a change that loses
96// either fails to compile here rather than in a caller.
97const _: () = {
98    const fn send_sync<T: Send + Sync>() {}
99    send_sync::<Stats>();
100    send_sync::<pagemap::SpanMeta>();
101    #[cfg(feature = "global")]
102    send_sync::<KevyAlloc>();
103};
104
105#[cfg(test)]
106mod tests;