Skip to main content

rusty_alloc_api/
lib.rs

1//! Safe Rust-native surface of rusty_alloc (plan §5.14).
2//!
3//! From M2, [`RustyAlloc`] is a real [`core::alloc::GlobalAlloc`]:
4//!
5//! ```ignore
6//! #[global_allocator]
7//! static ALLOC: rusty_alloc_api::RustyAlloc = rusty_alloc_api::RustyAlloc;
8//! ```
9//!
10//! [`Heap`] is a first-class heap. With the `allocator-api` feature (Rust
11//! 1.100 and later) both it and [`RustyAlloc`] implement
12//! [`core::alloc::Allocator`], so `Vec::new_in(&heap)` and
13//! `Box::new_in(x, RustyAlloc)` work; the `allocator` module's docs go through
14//! the trait's contract clause by clause. This crate stays a thin veneer over
15//! the same internals as the C ABI — no separate code path, so corpus numbers
16//! speak for Rust users too.
17
18#![cfg_attr(not(test), no_std)]
19#![deny(missing_docs)]
20
21use core::alloc::{GlobalAlloc, Layout};
22
23pub use rusty_alloc::{MI_COMPAT_VERSION, VERSION, version};
24
25// The one module above the crate's `rust-version`, which is why it is a
26// feature. Telling clippy its real floor keeps `incompatible_msrv` checking
27// the rest of the crate against 1.88, and this module against 1.100.
28#[cfg(feature = "allocator-api")]
29#[clippy::msrv = "1.100"]
30mod allocator;
31
32/// The global allocator handle (zero-sized).
33///
34/// It holds no state: every `RustyAlloc` is the same allocator, so copying
35/// one, or making another, gives a handle that frees what any other
36/// allocated.
37#[derive(Clone, Copy, Debug, Default)]
38pub struct RustyAlloc;
39
40/// One machine word: every block the allocator hands out is aligned this far.
41const WORD: usize = core::mem::size_of::<usize>();
42
43/// The alignment the size classes already give every block of MORE than one
44/// word: `bins::bin` rounds word counts up to even ones (upstream's
45/// `MI_ALIGN2W`), and every page area starts on a slice boundary, so a block
46/// of two words or more sits on a two-word boundary — 16 bytes on a 64-bit
47/// target, `MAX_ALIGN_SIZE`. Only the one-word class is not, which is why a
48/// request aligned between one and two words is raised to two words.
49///
50/// This is the alignment hashbrown asks for on every table (its SSE2 control
51/// group is 16 bytes), so a Rust `HashMap` used to go through the aligned
52/// path on every allocation and through allocate-copy-free on every realloc.
53const NATURAL_ALIGN: usize = 2 * WORD;
54
55/// A first-class heap (plan §5.14): `Drop` runs `mi_heap_delete` semantics
56/// (blocks migrate to the thread's backing heap and stay valid) unless built
57/// with [`Heap::new_destroyable`], where `Drop` releases every block at once.
58/// The destroyable form inherits C's contract for the raw methods below:
59/// callers must not touch its blocks after drop. With the `allocator-api`
60/// feature that is unrepresentable in safe code: a collection made with
61/// `Vec::new_in(&heap)` borrows the heap and cannot outlive it.
62pub struct Heap {
63    hb: *mut rusty_alloc::init::HeapBox,
64    destroy_on_drop: bool,
65}
66
67impl Heap {
68    /// New heap; dropped ⇒ blocks migrate to the backing heap.
69    ///
70    /// # Panics
71    /// When the OS refuses the heap's backing mapping (memory exhaustion) —
72    /// a defined panic, matching std's convention for infallible
73    /// constructors, rather than a null pointer carried into later use.
74    pub fn new() -> Heap {
75        let hb = rusty_alloc::init::create_heap(0, false, -1);
76        assert!(!hb.is_null(), "rusty_alloc: heap creation failed (OOM)");
77        Heap {
78            hb,
79            destroy_on_drop: false,
80        }
81    }
82
83    /// New heap; dropped ⇒ every allocation is released wholesale
84    /// (arena-style teardown).
85    ///
86    /// # Panics
87    /// As [`Heap::new`], on memory exhaustion.
88    pub fn new_destroyable() -> Heap {
89        let hb = rusty_alloc::init::create_heap(0, true, -1);
90        assert!(!hb.is_null(), "rusty_alloc: heap creation failed (OOM)");
91        Heap {
92            hb,
93            destroy_on_drop: true,
94        }
95    }
96
97    /// Allocate `layout`, borrowing the heap (so the block cannot outlive it).
98    ///
99    /// `#[inline]`, like the `GlobalAlloc` methods below and for their reason:
100    /// the fast path is a pop from the heap's direct table, and it belongs in
101    /// the caller. Out of line through `heap_malloc` it cost 28 instructions
102    /// and a call on every allocation, against the global handle's inline
103    /// pop, which is what put a `Vec` in a heap 6.6 % behind one on the global
104    /// allocator (`docs/opps.md`, "The `Allocator` route").
105    #[inline]
106    pub fn alloc(&self, layout: core::alloc::Layout) -> Option<core::ptr::NonNull<u8>> {
107        // SAFETY: hb live (we own it), called on the owning thread by the
108        // !Send/!Sync nature of raw-pointer fields.
109        //
110        // The three tiers are `GlobalAlloc::alloc`'s. They are stated in
111        // words, not as `<= 8`: on a 32-bit target a one-word block is four
112        // bytes and only four-aligned, so `<= 8` handed an eight-aligned
113        // layout of four bytes or fewer a block that could sit on an odd
114        // word. Up to `NATURAL_ALIGN` the size classes carry the alignment
115        // once the request is two words long.
116        let p = unsafe {
117            if layout.align() <= WORD {
118                rusty_alloc::alloc::heap_malloc_fast(self.hb, layout.size())
119            } else if layout.align() <= NATURAL_ALIGN {
120                rusty_alloc::alloc::heap_malloc_fast(self.hb, layout.size().max(NATURAL_ALIGN))
121            } else {
122                rusty_alloc::alloc::heap_malloc_aligned_at(
123                    self.hb,
124                    layout.size(),
125                    layout.align(),
126                    0,
127                )
128            }
129        };
130        core::ptr::NonNull::new(p)
131    }
132
133    /// Zeroed variant of [`alloc`](Self::alloc).
134    #[inline]
135    pub fn alloc_zeroed(&self, layout: core::alloc::Layout) -> Option<core::ptr::NonNull<u8>> {
136        // SAFETY: as alloc.
137        let p = unsafe {
138            if layout.align() <= WORD {
139                rusty_alloc::alloc::heap_zalloc_fast(self.hb, layout.size())
140            } else if layout.align() <= NATURAL_ALIGN {
141                rusty_alloc::alloc::heap_zalloc_fast(self.hb, layout.size().max(NATURAL_ALIGN))
142            } else {
143                rusty_alloc::alloc::heap_zalloc_aligned_at(
144                    self.hb,
145                    layout.size(),
146                    layout.align(),
147                    0,
148                )
149            }
150        };
151        core::ptr::NonNull::new(p)
152    }
153
154    /// Free a block previously allocated from this heap.
155    ///
156    /// # Safety
157    /// `p` came from this heap's alloc methods and is freed exactly once.
158    #[inline]
159    pub unsafe fn dealloc(&self, p: core::ptr::NonNull<u8>) {
160        // The inline free `GlobalAlloc::dealloc` uses, for its reason: through
161        // `free` this was a call into a symbol that tests for null first, and
162        // a `NonNull` is not null.
163        // SAFETY: forwarded contract; a block is freed by its page's owner,
164        // whichever heap of this thread it came from.
165        unsafe { rusty_alloc::alloc::free_inline_flags_first(p.as_ptr()) }
166    }
167
168    /// Whether `p` points into memory this heap owns (`mi_heap_contains_block`).
169    ///
170    /// A diagnostic, and not a fast one: it walks the heap's segments. It
171    /// answers by segment, so it is true of any address inside one of them,
172    /// allocated or not, and false of a block of another heap or of the
173    /// global allocator. Any address may be asked about; nothing is read
174    /// through it.
175    pub fn contains(&self, p: core::ptr::NonNull<u8>) -> bool {
176        // SAFETY: hb live (we own it), on the owning thread as `alloc` is;
177        // the walk compares `p`'s segment address and dereferences only the
178        // heap's own lists.
179        unsafe { rusty_alloc::alloc::heap_contains_block(self.hb, p.as_ptr()) }
180    }
181
182    /// Drain cross-thread frees and retire empty pages.
183    pub fn collect(&self) {
184        // SAFETY: owner thread (see alloc).
185        unsafe { rusty_alloc::alloc::heap_collect(self.hb, true) }
186    }
187}
188
189impl Default for Heap {
190    fn default() -> Self {
191        Self::new()
192    }
193}
194
195impl Drop for Heap {
196    fn drop(&mut self) {
197        // SAFETY: we own hb; exactly one of delete/destroy runs, once.
198        unsafe {
199            if self.destroy_on_drop {
200                rusty_alloc::init::heap_destroy(self.hb);
201            } else {
202                rusty_alloc::init::heap_delete(self.hb);
203            }
204        }
205    }
206}
207
208// SAFETY: GlobalAlloc contract — Layout-described allocation/free delegated to
209// the rusty_alloc core, which returns blocks satisfying the layout's size and
210// alignment (natural bins up to `NATURAL_ALIGN`; the aligned path above it)
211// and accepts any such block back in `free` regardless of which thread frees
212// it (M4: per-thread heaps, no lock — `free` routes by the segment's owner and
213// hands cross-thread blocks to the loom-modeled remote protocol).
214//
215// Every method is `#[inline]`, as the `mimalloc` crate's are. rustc generates
216// `__rust_alloc` and friends in the crate that declares `#[global_allocator]`,
217// and without the hint each one was a shim that loaded `&self`, shuffled the
218// arguments and jumped through the GOT into an out-of-line method — on every
219// Rust allocation and every drop. With it the fast paths land in the shims and
220// in their callers. Measured whole-program (callgrind, same output): a boxed-
221// tree/buffer/`Rc` workload −17.9 %, a HashMap/BTreeMap/String one −4.8 %, for
222// +1,888 and +2,784 bytes of text.
223unsafe impl GlobalAlloc for RustyAlloc {
224    #[inline]
225    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
226        if layout.align() <= WORD {
227            rusty_alloc::alloc::malloc(layout.size())
228        } else if layout.align() > NATURAL_ALIGN {
229            // SAFETY: `Layout` guarantees a power-of-two alignment, the one
230            // precondition `malloc_aligned_pow2` adds over `malloc_aligned`.
231            unsafe { rusty_alloc::alloc::malloc_aligned_pow2(layout.size(), layout.align()) }
232        } else {
233            alloc_natural(layout.size())
234        }
235    }
236
237    #[inline]
238    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
239        // `free_inline_flags_first` (the body of `free_inline`, in the test
240        // order that keeps `__rust_dealloc` inlinable; see its doc), not
241        // `free`: `dealloc` IS a free and does nothing
242        // else, the case `free_inline` exists for (the LD_PRELOAD export is
243        // the other). Through `free` every Rust deallocation paid a `jmp`
244        // into it and its null test; `GlobalAlloc` never passes null, and the
245        // hint lets that test fold away.
246        // SAFETY: GlobalAlloc contract — ptr came from `alloc`, is non-null
247        // and is freed once.
248        unsafe {
249            core::hint::assert_unchecked(!ptr.is_null());
250            rusty_alloc::alloc::free_inline_flags_first(ptr)
251        }
252    }
253
254    #[inline]
255    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
256        if layout.align() <= WORD {
257            rusty_alloc::alloc::zalloc(layout.size())
258        } else if layout.align() <= NATURAL_ALIGN {
259            rusty_alloc::alloc::zalloc(layout.size().max(NATURAL_ALIGN))
260        } else {
261            rusty_alloc::alloc::zalloc_aligned(layout.size(), layout.align())
262        }
263    }
264
265    #[inline]
266    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
267        if layout.align() <= NATURAL_ALIGN {
268            // Up to `NATURAL_ALIGN` the size classes carry the alignment, so
269            // the in-place arm is open to these layouts too: a block that
270            // stays keeps its address, and a move lands in a class of at
271            // least two words. Before this, every realloc aligned above one
272            // word (a growing `Vec<u128>`, say) was an allocate-copy-free.
273            //
274            // `realloc_rust` takes the four values in the registers
275            // `__rust_realloc` holds them in, so a word-aligned layout — all
276            // but a handful of real ones — is one compare and a jump; the
277            // rare two-word layout pays its `max` on its own branch. As
278            // `realloc(ptr, select(new_size, max(new_size, 16)))` every
279            // realloc paid the select and the register move.
280            // SAFETY: GlobalAlloc contract — ptr live and non-null,
281            // invalidated on move; our realloc preserves min(old, new) bytes.
282            unsafe {
283                let p = core::ptr::NonNull::new_unchecked(ptr);
284                if layout.align() <= WORD {
285                    rusty_alloc::alloc::realloc_rust(p, layout.size(), layout.align(), new_size)
286                } else {
287                    rusty_alloc::alloc::realloc_rust(
288                        p,
289                        layout.size(),
290                        layout.align(),
291                        new_size.max(NATURAL_ALIGN),
292                    )
293                }
294            }
295        } else {
296            // Above `NATURAL_ALIGN`. The block already satisfies
297            // `layout.align()` and keeps it if it stays, so when the new size
298            // fits and at least half the block stays in use — `realloc`'s own
299            // in-place rule, which `mi_realloc_aligned` applies too — it
300            // stays. This arm used to allocate, copy and free every time,
301            // shrinks and fits included (bench/rust-globalalloc
302            // `overaligned`).
303            //
304            // "It stays" is answered HERE, with no frame, and everything
305            // else is a jump with the four arguments where `__rust_realloc`
306            // received them. As one body, the move's allocation, copy and
307            // free had the entry push five callee-saved registers before
308            // the first test, and pop them again to return the pointer it
309            // was handed.
310            // SAFETY: GlobalAlloc contract — ptr is a live, non-null block
311            // of ours.
312            unsafe {
313                let p = core::ptr::NonNull::new_unchecked(ptr);
314                match rusty_alloc::alloc::usable_size_plain(p) {
315                    Some(usable) => {
316                        if new_size <= usable && new_size >= usable / 2 {
317                            return ptr;
318                        }
319                        realloc_overaligned_move(ptr, layout.size(), layout.align(), new_size)
320                    }
321                    // A flagged page (an interior aligned block, a
322                    // single-block span): the general question.
323                    None => realloc_overaligned(ptr, layout.size(), layout.align(), new_size),
324                }
325            }
326        }
327    }
328}
329
330/// The move of an over-aligned `realloc`: allocate through the aligned path,
331/// copy the bytes the layout says are live, free. Out of line, with the
332/// arguments in `__rust_realloc`'s own registers, so the in-place answer in
333/// front of it carries no frame.
334///
335/// # Safety
336/// `GlobalAlloc::realloc`'s contract, with `align` above two words.
337#[inline(never)]
338unsafe fn realloc_overaligned_move(
339    ptr: *mut u8,
340    old_size: usize,
341    align: usize,
342    new_size: usize,
343) -> *mut u8 {
344    // SAFETY: forwarded GlobalAlloc contract; `align` came from a `Layout`.
345    unsafe {
346        let np = GlobalAlloc::alloc(
347            &RustyAlloc,
348            Layout::from_size_align_unchecked(new_size, align),
349        );
350        if !np.is_null() {
351            core::ptr::copy_nonoverlapping(ptr, np, old_size.min(new_size));
352            GlobalAlloc::dealloc(
353                &RustyAlloc,
354                ptr,
355                Layout::from_size_align_unchecked(old_size, align),
356            );
357        }
358        np
359    }
360}
361
362/// An over-aligned `realloc` of a block on a flagged page: its usable size
363/// is not its page's block size, so ask the general way, then stay or move.
364///
365/// # Safety
366/// As [`realloc_overaligned_move`].
367#[cold]
368#[inline(never)]
369unsafe fn realloc_overaligned(
370    ptr: *mut u8,
371    old_size: usize,
372    align: usize,
373    new_size: usize,
374) -> *mut u8 {
375    // SAFETY: forwarded contract; `ptr` is a live block of ours.
376    unsafe {
377        let usable = rusty_alloc::alloc::usable_size(ptr);
378        if new_size <= usable && new_size >= usable / 2 {
379            return ptr;
380        }
381        realloc_overaligned_move(ptr, old_size, align, new_size)
382    }
383}
384
385/// `GlobalAlloc::alloc` for an alignment above one word up to
386/// `NATURAL_ALIGN`, out of line. Inline, this arm was a SECOND copy of the
387/// malloc fast path in every `__rust_alloc`, which kept the method too big for
388/// LLVM to inline into its callers. See `NATURAL_ALIGN`: a class of two words
389/// or more is already aligned this far, so only a one-word request needs
390/// raising.
391#[inline(never)]
392fn alloc_natural(size: usize) -> *mut u8 {
393    rusty_alloc::alloc::malloc(size.max(NATURAL_ALIGN))
394}