Skip to main content

rusty_alloc_api/
allocator.rs

1//! [`core::alloc::Allocator`] for the global handle and for first-class heaps.
2//!
3//! The trait is stable from Rust 1.100, so this module sits behind the
4//! `allocator-api` feature and the crate's own minimum Rust version does not
5//! move. With it, the standard collections that take an allocator can live in
6//! this allocator directly:
7//!
8//! ```
9//! use rusty_alloc_api::{Heap, RustyAlloc};
10//!
11//! // One collection on rusty_alloc, whatever the program's global allocator is.
12//! let mut v = Vec::new_in(RustyAlloc);
13//! v.extend([1u64, 2, 3]);
14//!
15//! // Collections inside a first-class heap. They borrow it, so none of them
16//! // can outlive it, and dropping the heap releases whatever is left.
17//! let heap = Heap::new_destroyable();
18//! let mut names = Vec::new_in(&heap);
19//! names.push(Box::new_in(7u32, &heap));
20//! assert_eq!(**names.last().unwrap(), 7);
21//! ```
22//!
23//! A collection in a heap is tied to the heap's thread, as the heap is:
24//!
25//! ```compile_fail,E0277
26//! use rusty_alloc_api::Heap;
27//! fn must_be_send<T: Send>(_: T) {}
28//! let heap = Heap::new();
29//! must_be_send(Vec::<u8, &Heap>::new_in(&heap));
30//! ```
31//!
32//! and it cannot outlive the heap it borrows:
33//!
34//! ```compile_fail,E0597
35//! use rusty_alloc_api::Heap;
36//! let v = {
37//!     let heap = Heap::new_destroyable();
38//!     Vec::<u8, &Heap>::new_in(&heap)
39//! };
40//! drop(v);
41//! ```
42//!
43//! # How each rule of the trait's contract is met
44//!
45//! * **Zero-sized layouts** never reach the allocator: `allocate` answers an
46//!   aligned dangling pointer of length 0 and `deallocate` ignores it, the
47//!   arrangement `std::alloc::Global` uses.
48//! * **The length returned is the length asked for.** The trait allows a
49//!   larger one, but `Vec` in 1.100 discards it, so reporting the size class
50//!   would cost a lookup on every allocation and buy nothing. A layout
51//!   therefore *fits* a block exactly when it is the layout that made it.
52//! * **A block stays valid until it is deallocated, or its heap is dropped.**
53//!   [`RustyAlloc`] has no state, so its blocks live until they are freed.
54//!   Dropping a [`Heap`] invalidates the blocks of a destroyable heap, which
55//!   the contract allows of an allocator's destructor; a collection reaches a
56//!   heap through `&Heap`, so the borrow checker rules that out in safe code.
57//! * **Equivalence.** Every `RustyAlloc` is equivalent to every other. A
58//!   `Heap` is equivalent only to itself (and, as the standard library
59//!   defines, to references to it). A block is never to be handed to a
60//!   different heap or to `RustyAlloc`, even where the allocator underneath
61//!   would cope.
62//! * **Nothing unwinds.** Allocation failure is `Err`, and the allocator's own
63//!   failure paths abort the process. That leaves the panics the compiler
64//!   puts in: the allocator indexes its own tables, and a release build of
65//!   it has a bounds check the optimiser could not remove on some of the
66//!   paths these methods reach (`tools/no-unwind-scan.sh` counts them from
67//!   the machine code and holds the count to a baseline). None can fire
68//!   while the allocator's state is intact, but "cannot fire" is not what
69//!   the contract asks, so every method runs under a guard that turns an
70//!   unwind into an abort, in every build. Measured, callgrind, the
71//!   collection work of `bench/rust-globalalloc/src/alloc_work.rs`: the guard
72//!   costs 27.6 instructions per step on `Vec::new_in(RustyAlloc)` (2,507.89
73//!   to 2,535.48, where the same work through `#[global_allocator]` is
74//!   2,533.37) and 6.7 inside a `Heap`: a call that was a jump before. It
75//!   goes when the scan reads zero.
76//! * **`grow` and `shrink` may change the alignment**, which
77//!   `GlobalAlloc::realloc` cannot: an equal alignment goes to the in-place
78//!   reallocation, a different one is an allocate, copy and free.
79//! * **A failed `grow` or `shrink` leaves the old block as it was**: the new
80//!   block is allocated before the old one is touched.
81
82use core::alloc::{AllocError, Allocator, GlobalAlloc, Layout};
83use core::ptr::NonNull;
84
85use crate::{Heap, NATURAL_ALIGN, RustyAlloc, WORD};
86
87/// Armed for the length of one trait method. It is forgotten on the way out,
88/// so its destructor runs only if the method is unwinding, and a panic raised
89/// during an unwind aborts the process.
90struct AbortOnUnwind;
91
92impl Drop for AbortOnUnwind {
93    fn drop(&mut self) {
94        panic!("rusty_alloc: an Allocator method must not unwind; aborting");
95    }
96}
97
98/// Run one trait method's body such that it cannot unwind into the caller.
99///
100/// The contract forbids it, and the standard library relies on that. What
101/// could unwind is a `debug_assert!` in a debug build and, in any build, a
102/// bounds check on one of the allocator's own tables (see the module docs).
103/// Either firing is a bug in the allocator or its state already destroyed,
104/// and it must stop the process, not unwind through a half-updated `Vec`.
105/// With `panic = "abort"` nothing unwinds and this is the body alone.
106#[inline(always)]
107fn no_unwind<R>(body: impl FnOnce() -> R) -> R {
108    let guard = AbortOnUnwind;
109    let out = body();
110    core::mem::forget(guard);
111    out
112}
113
114/// What a zero-sized layout is given: aligned, dangling, length 0.
115#[inline]
116fn zero_sized(layout: Layout) -> NonNull<[u8]> {
117    let p = core::ptr::without_provenance_mut::<u8>(layout.align());
118    // SAFETY: an alignment is a power of two, so it is not zero.
119    let p = unsafe { NonNull::new_unchecked(p) };
120    NonNull::slice_from_raw_parts(p, 0)
121}
122
123/// A raw result as the trait wants it: null is the allocation failing.
124#[inline]
125fn block(p: *mut u8, size: usize) -> Result<NonNull<[u8]>, AllocError> {
126    match NonNull::new(p) {
127        Some(p) => Ok(NonNull::slice_from_raw_parts(p, size)),
128        None => Err(AllocError),
129    }
130}
131
132/// Allocate `new`, copy `keep` bytes across, free the old block: the
133/// reallocation of last resort, and the only one that can change an alignment.
134/// The old block is untouched when the allocation fails.
135///
136/// # Safety
137/// `ptr` is a live block of `a` made with `old`, `old.size()` is not zero and
138/// `keep` is at most both sizes.
139#[inline]
140unsafe fn move_block<A: Allocator>(
141    a: &A,
142    ptr: NonNull<u8>,
143    old: Layout,
144    new: Layout,
145    keep: usize,
146) -> Result<NonNull<[u8]>, AllocError> {
147    let moved = a.allocate(new)?;
148    // SAFETY: both blocks are live and at least `keep` bytes long, and a
149    // fresh block cannot overlap a live one; then the old block is freed
150    // once, with the layout that made it.
151    unsafe {
152        core::ptr::copy_nonoverlapping(ptr.as_ptr(), moved.cast::<u8>().as_ptr(), keep);
153        a.deallocate(ptr, old);
154    }
155    Ok(moved)
156}
157
158/// Zero `block[from..]`, the part of a grown block the caller has not seen.
159///
160/// # Safety
161/// `block` is a live allocation and `from` is at most its length.
162#[inline]
163unsafe fn zero_tail(block: NonNull<[u8]>, from: usize) {
164    // SAFETY: per contract the range is inside one live allocation.
165    unsafe {
166        block
167            .cast::<u8>()
168            .as_ptr()
169            .add(from)
170            .write_bytes(0, block.len() - from);
171    }
172}
173
174// SAFETY: the blocks come from the same paths as `GlobalAlloc for RustyAlloc`,
175// which satisfy the layout's size and alignment, are disjoint, and stay valid
176// until freed: the handle has no state, so neither dropping it nor moving it
177// touches a block, and every `RustyAlloc` frees what any other allocated.
178// Zero-sized layouts are answered here and never reach the allocator. No
179// method unwinds: allocation failure is `Err`, and the allocator's own
180// failure paths abort. See the module docs for the contract clause by clause.
181unsafe impl Allocator for RustyAlloc {
182    #[inline]
183    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
184        no_unwind(|| {
185            if layout.size() == 0 {
186                return Ok(zero_sized(layout));
187            }
188            // SAFETY: the size is not zero, `GlobalAlloc::alloc`'s one demand.
189            block(unsafe { GlobalAlloc::alloc(self, layout) }, layout.size())
190        })
191    }
192
193    #[inline]
194    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
195        no_unwind(|| {
196            if layout.size() == 0 {
197                return Ok(zero_sized(layout));
198            }
199            // SAFETY: the size is not zero.
200            block(
201                unsafe { GlobalAlloc::alloc_zeroed(self, layout) },
202                layout.size(),
203            )
204        })
205    }
206
207    #[inline]
208    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
209        no_unwind(|| {
210            if layout.size() != 0 {
211                // SAFETY: a block of a non-zero layout came from `allocate` and
212                // friends, so it is a live block of this allocator, freed once.
213                unsafe { GlobalAlloc::dealloc(self, ptr.as_ptr(), layout) }
214            }
215        })
216    }
217
218    #[inline]
219    unsafe fn grow(
220        &self,
221        ptr: NonNull<u8>,
222        old_layout: Layout,
223        new_layout: Layout,
224    ) -> Result<NonNull<[u8]>, AllocError> {
225        no_unwind(|| {
226            if old_layout.size() == 0 {
227                return self.allocate(new_layout);
228            }
229            if old_layout.align() == new_layout.align() {
230                // SAFETY: `ptr` is a live block made with `old_layout`, and the
231                // new size is at least the old one, so it is not zero; a valid
232                // `new_layout` bounds it as `realloc` requires. On failure
233                // `realloc` returns null and leaves the block alone.
234                let p = unsafe {
235                    GlobalAlloc::realloc(self, ptr.as_ptr(), old_layout, new_layout.size())
236                };
237                return block(p, new_layout.size());
238            }
239            // SAFETY: forwarded contract; a grow keeps the whole old block.
240            unsafe { move_block(self, ptr, old_layout, new_layout, old_layout.size()) }
241        })
242    }
243
244    #[inline]
245    unsafe fn grow_zeroed(
246        &self,
247        ptr: NonNull<u8>,
248        old_layout: Layout,
249        new_layout: Layout,
250    ) -> Result<NonNull<[u8]>, AllocError> {
251        no_unwind(|| {
252            if old_layout.size() == 0 {
253                return self.allocate_zeroed(new_layout);
254            }
255            // SAFETY: forwarded contract.
256            let grown = unsafe { self.grow(ptr, old_layout, new_layout)? };
257            // SAFETY: `grown` is `new_layout.size()` long, at least the old size.
258            unsafe { zero_tail(grown, old_layout.size()) };
259            Ok(grown)
260        })
261    }
262
263    #[inline]
264    unsafe fn shrink(
265        &self,
266        ptr: NonNull<u8>,
267        old_layout: Layout,
268        new_layout: Layout,
269    ) -> Result<NonNull<[u8]>, AllocError> {
270        no_unwind(|| {
271            if new_layout.size() == 0 {
272                // SAFETY: forwarded contract: the old block is freed once.
273                unsafe { self.deallocate(ptr, old_layout) };
274                return Ok(zero_sized(new_layout));
275            }
276            if old_layout.align() == new_layout.align() {
277                // SAFETY: as `grow`; the new size was just seen to be non-zero.
278                let p = unsafe {
279                    GlobalAlloc::realloc(self, ptr.as_ptr(), old_layout, new_layout.size())
280                };
281                return block(p, new_layout.size());
282            }
283            // SAFETY: forwarded contract; a shrink keeps the new size's worth.
284            unsafe { move_block(self, ptr, old_layout, new_layout, new_layout.size()) }
285        })
286    }
287}
288
289impl Heap {
290    /// Reallocate inside this heap at an unchanged alignment. Null is the
291    /// allocation failing, with the old block left alone.
292    ///
293    /// # Safety
294    /// `ptr` is a live block of this heap made with a layout of `old_size`
295    /// bytes and `align`; `new_size` is not zero and is a valid size for
296    /// `align`.
297    #[inline]
298    unsafe fn realloc_same_align(
299        &self,
300        ptr: NonNull<u8>,
301        old_size: usize,
302        align: usize,
303        new_size: usize,
304    ) -> *mut u8 {
305        if align <= NATURAL_ALIGN {
306            // The size classes carry these alignments (see `NATURAL_ALIGN`),
307            // provided a request above one word is at least two words long,
308            // the same raise `Heap::alloc` applies.
309            let size = if align <= WORD {
310                new_size
311            } else {
312                new_size.max(NATURAL_ALIGN)
313            };
314            // SAFETY: the heap is live and this is its thread (`Heap` is
315            // neither `Send` nor `Sync`); `ptr` is a live block.
316            return unsafe { rusty_alloc::alloc::heap_realloc_fast(self.hb, ptr, size) };
317        }
318        // Above `NATURAL_ALIGN` only the aligned path can make the block, so a
319        // move has to go back through it. The block keeps its alignment if it
320        // stays, and it stays under the allocator's own in-place rule: the new
321        // size fits and at least half the block remains in use.
322        // SAFETY: `ptr` is a live block.
323        let usable = unsafe { rusty_alloc::alloc::usable_size(ptr.as_ptr()) };
324        if new_size <= usable && new_size >= usable / 2 {
325            return ptr.as_ptr();
326        }
327        // SAFETY: heap live on its thread; `align` came from a `Layout`.
328        let moved =
329            unsafe { rusty_alloc::alloc::heap_malloc_aligned_at(self.hb, new_size, align, 0) };
330        if !moved.is_null() {
331            // SAFETY: both blocks are live and hold the bytes copied; the old
332            // one is then freed once.
333            unsafe {
334                core::ptr::copy_nonoverlapping(ptr.as_ptr(), moved, old_size.min(new_size));
335                rusty_alloc::alloc::free(ptr.as_ptr());
336            }
337        }
338        moved
339    }
340}
341
342// SAFETY: the blocks come from `Heap::alloc`, which satisfies the layout, and
343// stay valid until they are freed or the heap is dropped; dropping is the
344// allocator's destructor running, which the contract lets invalidate. `Heap`
345// has no `&mut` API and is not `Clone`, so nothing else invalidates a block,
346// and a block is only ever returned to the heap that made it. `Heap` is
347// neither `Send` nor `Sync`, which keeps every call on the owning thread.
348// Zero-sized layouts never reach the heap, and no method unwinds. See the
349// module docs for the contract clause by clause.
350unsafe impl Allocator for Heap {
351    #[inline]
352    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
353        no_unwind(|| {
354            if layout.size() == 0 {
355                return Ok(zero_sized(layout));
356            }
357            match self.alloc(layout) {
358                Some(p) => Ok(NonNull::slice_from_raw_parts(p, layout.size())),
359                None => Err(AllocError),
360            }
361        })
362    }
363
364    #[inline]
365    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
366        no_unwind(|| {
367            if layout.size() == 0 {
368                return Ok(zero_sized(layout));
369            }
370            match self.alloc_zeroed(layout) {
371                Some(p) => Ok(NonNull::slice_from_raw_parts(p, layout.size())),
372                None => Err(AllocError),
373            }
374        })
375    }
376
377    #[inline]
378    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
379        no_unwind(|| {
380            if layout.size() != 0 {
381                // SAFETY: a block of a non-zero layout is a live block of this
382                // heap, freed once.
383                unsafe { self.dealloc(ptr) }
384            }
385        })
386    }
387
388    #[inline]
389    unsafe fn grow(
390        &self,
391        ptr: NonNull<u8>,
392        old_layout: Layout,
393        new_layout: Layout,
394    ) -> Result<NonNull<[u8]>, AllocError> {
395        no_unwind(|| {
396            if old_layout.size() == 0 {
397                return self.allocate(new_layout);
398            }
399            if old_layout.align() == new_layout.align() {
400                // SAFETY: `ptr` is a live block of this heap made with
401                // `old_layout`; the new size is at least the old, so not zero.
402                let p = unsafe {
403                    self.realloc_same_align(
404                        ptr,
405                        old_layout.size(),
406                        new_layout.align(),
407                        new_layout.size(),
408                    )
409                };
410                return block(p, new_layout.size());
411            }
412            // SAFETY: forwarded contract; a grow keeps the whole old block.
413            unsafe { move_block(self, ptr, old_layout, new_layout, old_layout.size()) }
414        })
415    }
416
417    #[inline]
418    unsafe fn grow_zeroed(
419        &self,
420        ptr: NonNull<u8>,
421        old_layout: Layout,
422        new_layout: Layout,
423    ) -> Result<NonNull<[u8]>, AllocError> {
424        no_unwind(|| {
425            if old_layout.size() == 0 {
426                return self.allocate_zeroed(new_layout);
427            }
428            // SAFETY: forwarded contract.
429            let grown = unsafe { self.grow(ptr, old_layout, new_layout)? };
430            // SAFETY: `grown` is `new_layout.size()` long, at least the old size.
431            unsafe { zero_tail(grown, old_layout.size()) };
432            Ok(grown)
433        })
434    }
435
436    #[inline]
437    unsafe fn shrink(
438        &self,
439        ptr: NonNull<u8>,
440        old_layout: Layout,
441        new_layout: Layout,
442    ) -> Result<NonNull<[u8]>, AllocError> {
443        no_unwind(|| {
444            if new_layout.size() == 0 {
445                // SAFETY: forwarded contract: the old block is freed once.
446                unsafe { self.deallocate(ptr, old_layout) };
447                return Ok(zero_sized(new_layout));
448            }
449            if old_layout.align() == new_layout.align() {
450                // SAFETY: as `grow`; the new size was just seen to be non-zero.
451                let p = unsafe {
452                    self.realloc_same_align(
453                        ptr,
454                        old_layout.size(),
455                        new_layout.align(),
456                        new_layout.size(),
457                    )
458                };
459                return block(p, new_layout.size());
460            }
461            // SAFETY: forwarded contract; a shrink keeps the new size's worth.
462            unsafe { move_block(self, ptr, old_layout, new_layout, new_layout.size()) }
463        })
464    }
465}
466
467#[cfg(test)]
468mod tests {
469    use super::no_unwind;
470
471    /// A panic inside a guarded body ends the process; it does not unwind to
472    /// the caller. Run in a child, since the point is that it does not return.
473    #[test]
474    #[cfg_attr(miri, ignore = "spawns a process")]
475    fn an_unwind_out_of_a_method_aborts() {
476        const CHILD: &str = "RA_NO_UNWIND_CHILD";
477        if std::env::var_os(CHILD).is_some() {
478            no_unwind(|| panic!("deliberate: the guard must abort on this"));
479        }
480        let exe = std::env::current_exe().expect("the test binary's own path");
481        let out = std::process::Command::new(exe)
482            .args([
483                "--exact",
484                "allocator::tests::an_unwind_out_of_a_method_aborts",
485            ])
486            .env(CHILD, "1")
487            .output()
488            .expect("spawn the child");
489        assert!(
490            !out.status.success(),
491            "the child survived a panic in a guarded body"
492        );
493        // 101 is the test harness reporting a caught panic: the unwind got out.
494        assert_ne!(
495            out.status.code(),
496            Some(101),
497            "the panic unwound to the harness instead of aborting"
498        );
499    }
500}