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}