1//! Memory allocation APIs
2
3use core::{
4 fmt,
5 ptr::{self, NonNull},
6};
7
8#[cfg(feature = "alloc")]
9mod global;
10
11#[cfg(feature = "std")]
12mod system;
13
14pub use core::alloc::{GlobalAlloc, Layout, LayoutError};
15
16#[cfg(feature = "alloc")]
17pub use self::global::Global;
18
19#[cfg(feature = "std")]
20pub use self::system::System;
21
22#[cfg(feature = "alloc")]
23pub use alloc_crate::alloc::{alloc, alloc_zeroed, dealloc, realloc};
24
25#[cfg(all(feature = "alloc", not(no_global_oom_handling)))]
26pub use alloc_crate::alloc::handle_alloc_error;
27
28/// The `AllocError` error indicates an allocation failure
29/// that may be due to resource exhaustion or to
30/// something wrong when combining the given input arguments with this
31/// allocator.
32#[derive(Copy, Clone, PartialEq, Eq, Debug)]
33pub struct AllocError;
34
35#[cfg(feature = "std")]
36impl std::error::Error for AllocError {}
37
38// (we need this for downstream impl of trait Error)
39impl fmt::Display for AllocError {
40 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
41 f.write_str(data:"memory allocation failed")
42 }
43}
44
45/// An implementation of `Allocator` can allocate, grow, shrink, and deallocate arbitrary blocks of
46/// data described via [`Layout`][].
47///
48/// `Allocator` is designed to be implemented on ZSTs, references, or smart pointers because having
49/// an allocator like `MyAlloc([u8; N])` cannot be moved, without updating the pointers to the
50/// allocated memory.
51///
52/// Unlike [`GlobalAlloc`][], zero-sized allocations are allowed in `Allocator`. If an underlying
53/// allocator does not support this (like jemalloc) or return a null pointer (such as
54/// `libc::malloc`), this must be caught by the implementation.
55///
56/// ### Currently allocated memory
57///
58/// Some of the methods require that a memory block be *currently allocated* via an allocator. This
59/// means that:
60///
61/// * the starting address for that memory block was previously returned by [`allocate`], [`grow`], or
62/// [`shrink`], and
63///
64/// * the memory block has not been subsequently deallocated, where blocks are either deallocated
65/// directly by being passed to [`deallocate`] or were changed by being passed to [`grow`] or
66/// [`shrink`] that returns `Ok`. If `grow` or `shrink` have returned `Err`, the passed pointer
67/// remains valid.
68///
69/// [`allocate`]: Allocator::allocate
70/// [`grow`]: Allocator::grow
71/// [`shrink`]: Allocator::shrink
72/// [`deallocate`]: Allocator::deallocate
73///
74/// ### Memory fitting
75///
76/// Some of the methods require that a layout *fit* a memory block. What it means for a layout to
77/// "fit" a memory block means (or equivalently, for a memory block to "fit" a layout) is that the
78/// following conditions must hold:
79///
80/// * The block must be allocated with the same alignment as [`layout.align()`], and
81///
82/// * The provided [`layout.size()`] must fall in the range `min ..= max`, where:
83/// - `min` is the size of the layout most recently used to allocate the block, and
84/// - `max` is the latest actual size returned from [`allocate`], [`grow`], or [`shrink`].
85///
86/// [`layout.align()`]: Layout::align
87/// [`layout.size()`]: Layout::size
88///
89/// # Safety
90///
91/// * Memory blocks returned from an allocator must point to valid memory and retain their validity
92/// until the instance and all of its clones are dropped,
93///
94/// * cloning or moving the allocator must not invalidate memory blocks returned from this
95/// allocator. A cloned allocator must behave like the same allocator, and
96///
97/// * any pointer to a memory block which is [*currently allocated*] may be passed to any other
98/// method of the allocator.
99///
100/// [*currently allocated*]: #currently-allocated-memory
101pub unsafe trait Allocator {
102 /// Attempts to allocate a block of memory.
103 ///
104 /// On success, returns a [`NonNull<[u8]>`][NonNull] meeting the size and alignment guarantees of `layout`.
105 ///
106 /// The returned block may have a larger size than specified by `layout.size()`, and may or may
107 /// not have its contents initialized.
108 ///
109 /// # Errors
110 ///
111 /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet
112 /// allocator's size or alignment constraints.
113 ///
114 /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
115 /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
116 /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
117 ///
118 /// Clients wishing to abort computation in response to an allocation error are encouraged to
119 /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
120 ///
121 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
122 fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;
123
124 /// Behaves like `allocate`, but also ensures that the returned memory is zero-initialized.
125 ///
126 /// # Errors
127 ///
128 /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet
129 /// allocator's size or alignment constraints.
130 ///
131 /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
132 /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
133 /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
134 ///
135 /// Clients wishing to abort computation in response to an allocation error are encouraged to
136 /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
137 ///
138 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
139 #[inline(always)]
140 fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
141 let ptr = self.allocate(layout)?;
142 // SAFETY: `alloc` returns a valid memory block
143 unsafe { ptr.cast::<u8>().as_ptr().write_bytes(0, ptr.len()) }
144 Ok(ptr)
145 }
146
147 /// Deallocates the memory referenced by `ptr`.
148 ///
149 /// # Safety
150 ///
151 /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator, and
152 /// * `layout` must [*fit*] that block of memory.
153 ///
154 /// [*currently allocated*]: #currently-allocated-memory
155 /// [*fit*]: #memory-fitting
156 unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);
157
158 /// Attempts to extend the memory block.
159 ///
160 /// Returns a new [`NonNull<[u8]>`][NonNull] containing a pointer and the actual size of the allocated
161 /// memory. The pointer is suitable for holding data described by `new_layout`. To accomplish
162 /// this, the allocator may extend the allocation referenced by `ptr` to fit the new layout.
163 ///
164 /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been
165 /// transferred to this allocator. Any access to the old `ptr` is Undefined Behavior, even if the
166 /// allocation was grown in-place. The newly returned pointer is the only valid pointer
167 /// for accessing this memory now.
168 ///
169 /// If this method returns `Err`, then ownership of the memory block has not been transferred to
170 /// this allocator, and the contents of the memory block are unaltered.
171 ///
172 /// # Safety
173 ///
174 /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.
175 /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).
176 /// * `new_layout.size()` must be greater than or equal to `old_layout.size()`.
177 ///
178 /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.
179 ///
180 /// [*currently allocated*]: #currently-allocated-memory
181 /// [*fit*]: #memory-fitting
182 ///
183 /// # Errors
184 ///
185 /// Returns `Err` if the new layout does not meet the allocator's size and alignment
186 /// constraints of the allocator, or if growing otherwise fails.
187 ///
188 /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
189 /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
190 /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
191 ///
192 /// Clients wishing to abort computation in response to an allocation error are encouraged to
193 /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
194 ///
195 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
196 #[inline(always)]
197 unsafe fn grow(
198 &self,
199 ptr: NonNull<u8>,
200 old_layout: Layout,
201 new_layout: Layout,
202 ) -> Result<NonNull<[u8]>, AllocError> {
203 debug_assert!(
204 new_layout.size() >= old_layout.size(),
205 "`new_layout.size()` must be greater than or equal to `old_layout.size()`"
206 );
207
208 let new_ptr = self.allocate(new_layout)?;
209
210 // SAFETY: because `new_layout.size()` must be greater than or equal to
211 // `old_layout.size()`, both the old and new memory allocation are valid for reads and
212 // writes for `old_layout.size()` bytes. Also, because the old allocation wasn't yet
213 // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is
214 // safe. The safety contract for `dealloc` must be upheld by the caller.
215 unsafe {
216 ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_ptr().cast(), old_layout.size());
217 self.deallocate(ptr, old_layout);
218 }
219
220 Ok(new_ptr)
221 }
222
223 /// Behaves like `grow`, but also ensures that the new contents are set to zero before being
224 /// returned.
225 ///
226 /// The memory block will contain the following contents after a successful call to
227 /// `grow_zeroed`:
228 /// * Bytes `0..old_layout.size()` are preserved from the original allocation.
229 /// * Bytes `old_layout.size()..old_size` will either be preserved or zeroed, depending on
230 /// the allocator implementation. `old_size` refers to the size of the memory block prior
231 /// to the `grow_zeroed` call, which may be larger than the size that was originally
232 /// requested when it was allocated.
233 /// * Bytes `old_size..new_size` are zeroed. `new_size` refers to the size of the memory
234 /// block returned by the `grow_zeroed` call.
235 ///
236 /// # Safety
237 ///
238 /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.
239 /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).
240 /// * `new_layout.size()` must be greater than or equal to `old_layout.size()`.
241 ///
242 /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.
243 ///
244 /// [*currently allocated*]: #currently-allocated-memory
245 /// [*fit*]: #memory-fitting
246 ///
247 /// # Errors
248 ///
249 /// Returns `Err` if the new layout does not meet the allocator's size and alignment
250 /// constraints of the allocator, or if growing otherwise fails.
251 ///
252 /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
253 /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
254 /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
255 ///
256 /// Clients wishing to abort computation in response to an allocation error are encouraged to
257 /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
258 ///
259 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
260 #[inline(always)]
261 unsafe fn grow_zeroed(
262 &self,
263 ptr: NonNull<u8>,
264 old_layout: Layout,
265 new_layout: Layout,
266 ) -> Result<NonNull<[u8]>, AllocError> {
267 debug_assert!(
268 new_layout.size() >= old_layout.size(),
269 "`new_layout.size()` must be greater than or equal to `old_layout.size()`"
270 );
271
272 let new_ptr = self.allocate_zeroed(new_layout)?;
273
274 // SAFETY: because `new_layout.size()` must be greater than or equal to
275 // `old_layout.size()`, both the old and new memory allocation are valid for reads and
276 // writes for `old_layout.size()` bytes. Also, because the old allocation wasn't yet
277 // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is
278 // safe. The safety contract for `dealloc` must be upheld by the caller.
279 unsafe {
280 ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_ptr().cast(), old_layout.size());
281 self.deallocate(ptr, old_layout);
282 }
283
284 Ok(new_ptr)
285 }
286
287 /// Attempts to shrink the memory block.
288 ///
289 /// Returns a new [`NonNull<[u8]>`][NonNull] containing a pointer and the actual size of the allocated
290 /// memory. The pointer is suitable for holding data described by `new_layout`. To accomplish
291 /// this, the allocator may shrink the allocation referenced by `ptr` to fit the new layout.
292 ///
293 /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been
294 /// transferred to this allocator. Any access to the old `ptr` is Undefined Behavior, even if the
295 /// allocation was shrunk in-place. The newly returned pointer is the only valid pointer
296 /// for accessing this memory now.
297 ///
298 /// If this method returns `Err`, then ownership of the memory block has not been transferred to
299 /// this allocator, and the contents of the memory block are unaltered.
300 ///
301 /// # Safety
302 ///
303 /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.
304 /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).
305 /// * `new_layout.size()` must be smaller than or equal to `old_layout.size()`.
306 ///
307 /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.
308 ///
309 /// [*currently allocated*]: #currently-allocated-memory
310 /// [*fit*]: #memory-fitting
311 ///
312 /// # Errors
313 ///
314 /// Returns `Err` if the new layout does not meet the allocator's size and alignment
315 /// constraints of the allocator, or if shrinking otherwise fails.
316 ///
317 /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
318 /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
319 /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
320 ///
321 /// Clients wishing to abort computation in response to an allocation error are encouraged to
322 /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
323 ///
324 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
325 #[inline(always)]
326 unsafe fn shrink(
327 &self,
328 ptr: NonNull<u8>,
329 old_layout: Layout,
330 new_layout: Layout,
331 ) -> Result<NonNull<[u8]>, AllocError> {
332 debug_assert!(
333 new_layout.size() <= old_layout.size(),
334 "`new_layout.size()` must be smaller than or equal to `old_layout.size()`"
335 );
336
337 let new_ptr = self.allocate(new_layout)?;
338
339 // SAFETY: because `new_layout.size()` must be lower than or equal to
340 // `old_layout.size()`, both the old and new memory allocation are valid for reads and
341 // writes for `new_layout.size()` bytes. Also, because the old allocation wasn't yet
342 // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is
343 // safe. The safety contract for `dealloc` must be upheld by the caller.
344 unsafe {
345 ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_ptr().cast(), new_layout.size());
346 self.deallocate(ptr, old_layout);
347 }
348
349 Ok(new_ptr)
350 }
351
352 /// Creates a "by reference" adapter for this instance of `Allocator`.
353 ///
354 /// The returned adapter also implements `Allocator` and will simply borrow this.
355 #[inline(always)]
356 fn by_ref(&self) -> &Self
357 where
358 Self: Sized,
359 {
360 self
361 }
362}
363
364unsafe impl<A> Allocator for &A
365where
366 A: Allocator + ?Sized,
367{
368 #[inline(always)]
369 fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
370 (**self).allocate(layout)
371 }
372
373 #[inline(always)]
374 fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
375 (**self).allocate_zeroed(layout)
376 }
377
378 #[inline(always)]
379 unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout) {
380 // SAFETY: the safety contract must be upheld by the caller
381 unsafe { (**self).deallocate(ptr, layout) }
382 }
383
384 #[inline(always)]
385 unsafe fn grow(
386 &self,
387 ptr: NonNull<u8>,
388 old_layout: Layout,
389 new_layout: Layout,
390 ) -> Result<NonNull<[u8]>, AllocError> {
391 // SAFETY: the safety contract must be upheld by the caller
392 unsafe { (**self).grow(ptr, old_layout, new_layout) }
393 }
394
395 #[inline(always)]
396 unsafe fn grow_zeroed(
397 &self,
398 ptr: NonNull<u8>,
399 old_layout: Layout,
400 new_layout: Layout,
401 ) -> Result<NonNull<[u8]>, AllocError> {
402 // SAFETY: the safety contract must be upheld by the caller
403 unsafe { (**self).grow_zeroed(ptr, old_layout, new_layout) }
404 }
405
406 #[inline(always)]
407 unsafe fn shrink(
408 &self,
409 ptr: NonNull<u8>,
410 old_layout: Layout,
411 new_layout: Layout,
412 ) -> Result<NonNull<[u8]>, AllocError> {
413 // SAFETY: the safety contract must be upheld by the caller
414 unsafe { (**self).shrink(ptr, old_layout, new_layout) }
415 }
416}
417