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