1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 //! Memory allocation APIs
13 #![stable(feature = "alloc_module", since = "1.28.0")]
19 use ptr::{self, NonNull};
20 use num::NonZeroUsize;
22 /// Represents the combination of a starting address and
23 /// a total capacity of the returned block.
24 #[unstable(feature = "allocator_api", issue = "32838")]
26 pub struct Excess(pub NonNull<u8>, pub usize);
28 fn size_align<T>() -> (usize, usize) {
29 (mem::size_of::<T>(), mem::align_of::<T>())
32 /// Layout of a block of memory.
34 /// An instance of `Layout` describes a particular layout of memory.
35 /// You build a `Layout` up as an input to give to an allocator.
37 /// All layouts have an associated non-negative size and a
38 /// power-of-two alignment.
40 /// (Note however that layouts are *not* required to have positive
41 /// size, even though many allocators require that all memory
42 /// requests have positive size. A caller to the `Alloc::alloc`
43 /// method must either ensure that conditions like this are met, or
44 /// use specific allocators with looser requirements.)
45 #[stable(feature = "alloc_layout", since = "1.28.0")]
46 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
47 #[lang = "alloc_layout"]
49 // size of the requested block of memory, measured in bytes.
52 // alignment of the requested block of memory, measured in bytes.
53 // we ensure that this is always a power-of-two, because API's
54 // like `posix_memalign` require it and it is a reasonable
55 // constraint to impose on Layout constructors.
57 // (However, we do not analogously require `align >= sizeof(void*)`,
58 // even though that is *also* a requirement of `posix_memalign`.)
63 /// Constructs a `Layout` from a given `size` and `align`,
64 /// or returns `LayoutErr` if either of the following conditions
67 /// * `align` must not be zero,
69 /// * `align` must be a power of two,
71 /// * `size`, when rounded up to the nearest multiple of `align`,
72 /// must not overflow (i.e. the rounded value must be less than
74 #[stable(feature = "alloc_layout", since = "1.28.0")]
76 pub fn from_size_align(size: usize, align: usize) -> Result<Self, LayoutErr> {
77 if !align.is_power_of_two() {
78 return Err(LayoutErr { private: () });
81 // (power-of-two implies align != 0.)
83 // Rounded up size is:
84 // size_rounded_up = (size + align - 1) & !(align - 1);
86 // We know from above that align != 0. If adding (align - 1)
87 // does not overflow, then rounding up will be fine.
89 // Conversely, &-masking with !(align - 1) will subtract off
90 // only low-order-bits. Thus if overflow occurs with the sum,
91 // the &-mask cannot subtract enough to undo that overflow.
93 // Above implies that checking for summation overflow is both
94 // necessary and sufficient.
95 if size > usize::MAX - (align - 1) {
96 return Err(LayoutErr { private: () });
100 Ok(Layout::from_size_align_unchecked(size, align))
104 /// Creates a layout, bypassing all checks.
108 /// This function is unsafe as it does not verify the preconditions from
109 /// [`Layout::from_size_align`](#method.from_size_align).
110 #[stable(feature = "alloc_layout", since = "1.28.0")]
112 pub unsafe fn from_size_align_unchecked(size: usize, align: usize) -> Self {
113 Layout { size_: size, align_: NonZeroUsize::new_unchecked(align) }
116 /// The minimum size in bytes for a memory block of this layout.
117 #[stable(feature = "alloc_layout", since = "1.28.0")]
119 pub fn size(&self) -> usize { self.size_ }
121 /// The minimum byte alignment for a memory block of this layout.
122 #[stable(feature = "alloc_layout", since = "1.28.0")]
124 pub fn align(&self) -> usize { self.align_.get() }
126 /// Constructs a `Layout` suitable for holding a value of type `T`.
127 #[stable(feature = "alloc_layout", since = "1.28.0")]
129 pub fn new<T>() -> Self {
130 let (size, align) = size_align::<T>();
131 // Note that the align is guaranteed by rustc to be a power of two and
132 // the size+align combo is guaranteed to fit in our address space. As a
133 // result use the unchecked constructor here to avoid inserting code
134 // that panics if it isn't optimized well enough.
135 debug_assert!(Layout::from_size_align(size, align).is_ok());
137 Layout::from_size_align_unchecked(size, align)
141 /// Produces layout describing a record that could be used to
142 /// allocate backing structure for `T` (which could be a trait
143 /// or other unsized type like a slice).
144 #[stable(feature = "alloc_layout", since = "1.28.0")]
146 pub fn for_value<T: ?Sized>(t: &T) -> Self {
147 let (size, align) = (mem::size_of_val(t), mem::align_of_val(t));
148 // See rationale in `new` for why this us using an unsafe variant below
149 debug_assert!(Layout::from_size_align(size, align).is_ok());
151 Layout::from_size_align_unchecked(size, align)
155 /// Creates a layout describing the record that can hold a value
156 /// of the same layout as `self`, but that also is aligned to
157 /// alignment `align` (measured in bytes).
159 /// If `self` already meets the prescribed alignment, then returns
162 /// Note that this method does not add any padding to the overall
163 /// size, regardless of whether the returned layout has a different
164 /// alignment. In other words, if `K` has size 16, `K.align_to(32)`
165 /// will *still* have size 16.
169 /// Panics if the combination of `self.size()` and the given `align`
170 /// violates the conditions listed in
171 /// [`Layout::from_size_align`](#method.from_size_align).
172 #[unstable(feature = "allocator_api", issue = "32838")]
174 pub fn align_to(&self, align: usize) -> Self {
175 Layout::from_size_align(self.size(), cmp::max(self.align(), align)).unwrap()
178 /// Returns the amount of padding we must insert after `self`
179 /// to ensure that the following address will satisfy `align`
180 /// (measured in bytes).
182 /// E.g. if `self.size()` is 9, then `self.padding_needed_for(4)`
183 /// returns 3, because that is the minimum number of bytes of
184 /// padding required to get a 4-aligned address (assuming that the
185 /// corresponding memory block starts at a 4-aligned address).
187 /// The return value of this function has no meaning if `align` is
188 /// not a power-of-two.
190 /// Note that the utility of the returned value requires `align`
191 /// to be less than or equal to the alignment of the starting
192 /// address for the whole allocated block of memory. One way to
193 /// satisfy this constraint is to ensure `align <= self.align()`.
194 #[unstable(feature = "allocator_api", issue = "32838")]
196 pub fn padding_needed_for(&self, align: usize) -> usize {
197 let len = self.size();
199 // Rounded up value is:
200 // len_rounded_up = (len + align - 1) & !(align - 1);
201 // and then we return the padding difference: `len_rounded_up - len`.
203 // We use modular arithmetic throughout:
205 // 1. align is guaranteed to be > 0, so align - 1 is always
208 // 2. `len + align - 1` can overflow by at most `align - 1`,
209 // so the &-mask wth `!(align - 1)` will ensure that in the
210 // case of overflow, `len_rounded_up` will itself be 0.
211 // Thus the returned padding, when added to `len`, yields 0,
212 // which trivially satisfies the alignment `align`.
214 // (Of course, attempts to allocate blocks of memory whose
215 // size and padding overflow in the above manner should cause
216 // the allocator to yield an error anyway.)
218 let len_rounded_up = len.wrapping_add(align).wrapping_sub(1)
219 & !align.wrapping_sub(1);
220 len_rounded_up.wrapping_sub(len)
223 /// Creates a layout describing the record for `n` instances of
224 /// `self`, with a suitable amount of padding between each to
225 /// ensure that each instance is given its requested size and
226 /// alignment. On success, returns `(k, offs)` where `k` is the
227 /// layout of the array and `offs` is the distance between the start
228 /// of each element in the array.
230 /// On arithmetic overflow, returns `LayoutErr`.
231 #[unstable(feature = "allocator_api", issue = "32838")]
233 pub fn repeat(&self, n: usize) -> Result<(Self, usize), LayoutErr> {
234 let padded_size = self.size().checked_add(self.padding_needed_for(self.align()))
235 .ok_or(LayoutErr { private: () })?;
236 let alloc_size = padded_size.checked_mul(n)
237 .ok_or(LayoutErr { private: () })?;
240 // self.align is already known to be valid and alloc_size has been
242 Ok((Layout::from_size_align_unchecked(alloc_size, self.align()), padded_size))
246 /// Creates a layout describing the record for `self` followed by
247 /// `next`, including any necessary padding to ensure that `next`
248 /// will be properly aligned. Note that the result layout will
249 /// satisfy the alignment properties of both `self` and `next`.
251 /// Returns `Some((k, offset))`, where `k` is layout of the concatenated
252 /// record and `offset` is the relative location, in bytes, of the
253 /// start of the `next` embedded within the concatenated record
254 /// (assuming that the record itself starts at offset 0).
256 /// On arithmetic overflow, returns `LayoutErr`.
257 #[unstable(feature = "allocator_api", issue = "32838")]
259 pub fn extend(&self, next: Self) -> Result<(Self, usize), LayoutErr> {
260 let new_align = cmp::max(self.align(), next.align());
261 let pad = self.padding_needed_for(next.align());
263 let offset = self.size().checked_add(pad)
264 .ok_or(LayoutErr { private: () })?;
265 let new_size = offset.checked_add(next.size())
266 .ok_or(LayoutErr { private: () })?;
268 let layout = Layout::from_size_align(new_size, new_align)?;
272 /// Creates a layout describing the record for `n` instances of
273 /// `self`, with no padding between each instance.
275 /// Note that, unlike `repeat`, `repeat_packed` does not guarantee
276 /// that the repeated instances of `self` will be properly
277 /// aligned, even if a given instance of `self` is properly
278 /// aligned. In other words, if the layout returned by
279 /// `repeat_packed` is used to allocate an array, it is not
280 /// guaranteed that all elements in the array will be properly
283 /// On arithmetic overflow, returns `LayoutErr`.
284 #[unstable(feature = "allocator_api", issue = "32838")]
286 pub fn repeat_packed(&self, n: usize) -> Result<Self, LayoutErr> {
287 let size = self.size().checked_mul(n).ok_or(LayoutErr { private: () })?;
288 Layout::from_size_align(size, self.align())
291 /// Creates a layout describing the record for `self` followed by
292 /// `next` with no additional padding between the two. Since no
293 /// padding is inserted, the alignment of `next` is irrelevant,
294 /// and is not incorporated *at all* into the resulting layout.
296 /// Returns `(k, offset)`, where `k` is layout of the concatenated
297 /// record and `offset` is the relative location, in bytes, of the
298 /// start of the `next` embedded within the concatenated record
299 /// (assuming that the record itself starts at offset 0).
301 /// (The `offset` is always the same as `self.size()`; we use this
302 /// signature out of convenience in matching the signature of
305 /// On arithmetic overflow, returns `LayoutErr`.
306 #[unstable(feature = "allocator_api", issue = "32838")]
308 pub fn extend_packed(&self, next: Self) -> Result<(Self, usize), LayoutErr> {
309 let new_size = self.size().checked_add(next.size())
310 .ok_or(LayoutErr { private: () })?;
311 let layout = Layout::from_size_align(new_size, self.align())?;
312 Ok((layout, self.size()))
315 /// Creates a layout describing the record for a `[T; n]`.
317 /// On arithmetic overflow, returns `LayoutErr`.
318 #[unstable(feature = "allocator_api", issue = "32838")]
320 pub fn array<T>(n: usize) -> Result<Self, LayoutErr> {
324 debug_assert!(offs == mem::size_of::<T>());
330 /// The parameters given to `Layout::from_size_align`
331 /// or some other `Layout` constructor
332 /// do not satisfy its documented constraints.
333 #[stable(feature = "alloc_layout", since = "1.28.0")]
334 #[derive(Clone, PartialEq, Eq, Debug)]
335 pub struct LayoutErr {
339 // (we need this for downstream impl of trait Error)
340 #[stable(feature = "alloc_layout", since = "1.28.0")]
341 impl fmt::Display for LayoutErr {
342 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
343 f.write_str("invalid parameters to Layout::from_size_align")
347 /// The `AllocErr` error indicates an allocation failure
348 /// that may be due to resource exhaustion or to
349 /// something wrong when combining the given input arguments with this
351 #[unstable(feature = "allocator_api", issue = "32838")]
352 #[derive(Clone, PartialEq, Eq, Debug)]
355 // (we need this for downstream impl of trait Error)
356 #[unstable(feature = "allocator_api", issue = "32838")]
357 impl fmt::Display for AllocErr {
358 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
359 f.write_str("memory allocation failed")
363 /// The `CannotReallocInPlace` error is used when `grow_in_place` or
364 /// `shrink_in_place` were unable to reuse the given memory block for
365 /// a requested layout.
366 #[unstable(feature = "allocator_api", issue = "32838")]
367 #[derive(Clone, PartialEq, Eq, Debug)]
368 pub struct CannotReallocInPlace;
370 #[unstable(feature = "allocator_api", issue = "32838")]
371 impl CannotReallocInPlace {
372 pub fn description(&self) -> &str {
373 "cannot reallocate allocator's memory in place"
377 // (we need this for downstream impl of trait Error)
378 #[unstable(feature = "allocator_api", issue = "32838")]
379 impl fmt::Display for CannotReallocInPlace {
380 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
381 write!(f, "{}", self.description())
385 /// A memory allocator that can be registered as the standard library’s default
386 /// though the `#[global_allocator]` attributes.
388 /// Some of the methods require that a memory block be *currently
389 /// allocated* via an allocator. This means that:
391 /// * the starting address for that memory block was previously
392 /// returned by a previous call to an allocation method
393 /// such as `alloc`, and
395 /// * the memory block has not been subsequently deallocated, where
396 /// blocks are deallocated either by being passed to a deallocation
397 /// method such as `dealloc` or by being
398 /// passed to a reallocation method that returns a non-null pointer.
404 /// use std::alloc::{GlobalAlloc, Layout, alloc};
405 /// use std::ptr::null_mut;
407 /// struct MyAllocator;
409 /// unsafe impl GlobalAlloc for MyAllocator {
410 /// unsafe fn alloc(&self, _layout: Layout) -> *mut u8 { null_mut() }
411 /// unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {}
414 /// #[global_allocator]
415 /// static A: MyAllocator = MyAllocator;
419 /// assert!(alloc(Layout::new::<u32>()).is_null())
426 /// The `GlobalAlloc` trait is an `unsafe` trait for a number of reasons, and
427 /// implementors must ensure that they adhere to these contracts:
429 /// * It's undefined behavior if global allocators unwind. This restriction may
430 /// be lifted in the future, but currently a panic from any of these
431 /// functions may lead to memory unsafety.
433 /// * `Layout` queries and calculations in general must be correct. Callers of
434 /// this trait are allowed to rely on the contracts defined on each method,
435 /// and implementors must ensure such contracts remain true.
436 #[stable(feature = "global_alloc", since = "1.28.0")]
437 pub unsafe trait GlobalAlloc {
438 /// Allocate memory as described by the given `layout`.
440 /// Returns a pointer to newly-allocated memory,
441 /// or null to indicate allocation failure.
445 /// This function is unsafe because undefined behavior can result
446 /// if the caller does not ensure that `layout` has non-zero size.
448 /// (Extension subtraits might provide more specific bounds on
449 /// behavior, e.g. guarantee a sentinel address or a null pointer
450 /// in response to a zero-size allocation request.)
452 /// The allocated block of memory may or may not be initialized.
456 /// Returning a null pointer indicates that either memory is exhausted
457 /// or `layout` does not meet allocator's size or alignment constraints.
459 /// Implementations are encouraged to return null on memory
460 /// exhaustion rather than aborting, but this is not
461 /// a strict requirement. (Specifically: it is *legal* to
462 /// implement this trait atop an underlying native allocation
463 /// library that aborts on memory exhaustion.)
465 /// Clients wishing to abort computation in response to an
466 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
467 /// rather than directly invoking `panic!` or similar.
469 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
470 #[stable(feature = "global_alloc", since = "1.28.0")]
471 unsafe fn alloc(&self, layout: Layout) -> *mut u8;
473 /// Deallocate the block of memory at the given `ptr` pointer with the given `layout`.
477 /// This function is unsafe because undefined behavior can result
478 /// if the caller does not ensure all of the following:
480 /// * `ptr` must denote a block of memory currently allocated via
483 /// * `layout` must be the same layout that was used
484 /// to allocated that block of memory,
485 #[stable(feature = "global_alloc", since = "1.28.0")]
486 unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
488 /// Behaves like `alloc`, but also ensures that the contents
489 /// are set to zero before being returned.
493 /// This function is unsafe for the same reasons that `alloc` is.
494 /// However the allocated block of memory is guaranteed to be initialized.
498 /// Returning a null pointer indicates that either memory is exhausted
499 /// or `layout` does not meet allocator's size or alignment constraints,
500 /// just as in `alloc`.
502 /// Clients wishing to abort computation in response to an
503 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
504 /// rather than directly invoking `panic!` or similar.
506 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
507 #[stable(feature = "global_alloc", since = "1.28.0")]
508 unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
509 let size = layout.size();
510 let ptr = self.alloc(layout);
512 ptr::write_bytes(ptr, 0, size);
517 /// Shink or grow a block of memory to the given `new_size`.
518 /// The block is described by the given `ptr` pointer and `layout`.
520 /// If this returns a non-null pointer, then ownership of the memory block
521 /// referenced by `ptr` has been transferred to this allocator.
522 /// The memory may or may not have been deallocated,
523 /// and should be considered unusable (unless of course it was
524 /// transferred back to the caller again via the return value of
527 /// If this method returns null, then ownership of the memory
528 /// block has not been transferred to this allocator, and the
529 /// contents of the memory block are unaltered.
533 /// This function is unsafe because undefined behavior can result
534 /// if the caller does not ensure all of the following:
536 /// * `ptr` must be currently allocated via this allocator,
538 /// * `layout` must be the same layout that was used
539 /// to allocated that block of memory,
541 /// * `new_size` must be greater than zero.
543 /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`,
544 /// must not overflow (i.e. the rounded value must be less than `usize::MAX`).
546 /// (Extension subtraits might provide more specific bounds on
547 /// behavior, e.g. guarantee a sentinel address or a null pointer
548 /// in response to a zero-size allocation request.)
552 /// Returns null if the new layout does not meet the size
553 /// and alignment constraints of the allocator, or if reallocation
556 /// Implementations are encouraged to return null on memory
557 /// exhaustion rather than panicking or aborting, but this is not
558 /// a strict requirement. (Specifically: it is *legal* to
559 /// implement this trait atop an underlying native allocation
560 /// library that aborts on memory exhaustion.)
562 /// Clients wishing to abort computation in response to a
563 /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
564 /// rather than directly invoking `panic!` or similar.
566 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
567 #[stable(feature = "global_alloc", since = "1.28.0")]
568 unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
569 let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
570 let new_ptr = self.alloc(new_layout);
571 if !new_ptr.is_null() {
572 ptr::copy_nonoverlapping(
575 cmp::min(layout.size(), new_size),
577 self.dealloc(ptr, layout);
583 /// An implementation of `Alloc` can allocate, reallocate, and
584 /// deallocate arbitrary blocks of data described via `Layout`.
586 /// Some of the methods require that a memory block be *currently
587 /// allocated* via an allocator. This means that:
589 /// * the starting address for that memory block was previously
590 /// returned by a previous call to an allocation method (`alloc`,
591 /// `alloc_zeroed`, `alloc_excess`, `alloc_one`, `alloc_array`) or
592 /// reallocation method (`realloc`, `realloc_excess`, or
593 /// `realloc_array`), and
595 /// * the memory block has not been subsequently deallocated, where
596 /// blocks are deallocated either by being passed to a deallocation
597 /// method (`dealloc`, `dealloc_one`, `dealloc_array`) or by being
598 /// passed to a reallocation method (see above) that returns `Ok`.
600 /// A note regarding zero-sized types and zero-sized layouts: many
601 /// methods in the `Alloc` trait state that allocation requests
602 /// must be non-zero size, or else undefined behavior can result.
604 /// * However, some higher-level allocation methods (`alloc_one`,
605 /// `alloc_array`) are well-defined on zero-sized types and can
606 /// optionally support them: it is left up to the implementor
607 /// whether to return `Err`, or to return `Ok` with some pointer.
609 /// * If an `Alloc` implementation chooses to return `Ok` in this
610 /// case (i.e. the pointer denotes a zero-sized inaccessible block)
611 /// then that returned pointer must be considered "currently
612 /// allocated". On such an allocator, *all* methods that take
613 /// currently-allocated pointers as inputs must accept these
614 /// zero-sized pointers, *without* causing undefined behavior.
616 /// * In other words, if a zero-sized pointer can flow out of an
617 /// allocator, then that allocator must likewise accept that pointer
618 /// flowing back into its deallocation and reallocation methods.
620 /// Some of the methods require that a layout *fit* a memory block.
621 /// What it means for a layout to "fit" a memory block means (or
622 /// equivalently, for a memory block to "fit" a layout) is that the
623 /// following two conditions must hold:
625 /// 1. The block's starting address must be aligned to `layout.align()`.
627 /// 2. The block's size must fall in the range `[use_min, use_max]`, where:
629 /// * `use_min` is `self.usable_size(layout).0`, and
631 /// * `use_max` is the capacity that was (or would have been)
632 /// returned when (if) the block was allocated via a call to
633 /// `alloc_excess` or `realloc_excess`.
637 /// * the size of the layout most recently used to allocate the block
638 /// is guaranteed to be in the range `[use_min, use_max]`, and
640 /// * a lower-bound on `use_max` can be safely approximated by a call to
643 /// * if a layout `k` fits a memory block (denoted by `ptr`)
644 /// currently allocated via an allocator `a`, then it is legal to
645 /// use that layout to deallocate it, i.e. `a.dealloc(ptr, k);`.
649 /// The `Alloc` trait is an `unsafe` trait for a number of reasons, and
650 /// implementors must ensure that they adhere to these contracts:
652 /// * Pointers returned from allocation functions must point to valid memory and
653 /// retain their validity until at least the instance of `Alloc` is dropped
656 /// * `Layout` queries and calculations in general must be correct. Callers of
657 /// this trait are allowed to rely on the contracts defined on each method,
658 /// and implementors must ensure such contracts remain true.
660 /// Note that this list may get tweaked over time as clarifications are made in
662 #[unstable(feature = "allocator_api", issue = "32838")]
663 pub unsafe trait Alloc {
665 // (Note: some existing allocators have unspecified but well-defined
666 // behavior in response to a zero size allocation request ;
667 // e.g. in C, `malloc` of 0 will either return a null pointer or a
668 // unique pointer, but will not have arbitrary undefined
670 // However in jemalloc for example,
671 // `mallocx(0)` is documented as undefined behavior.)
673 /// Returns a pointer meeting the size and alignment guarantees of
676 /// If this method returns an `Ok(addr)`, then the `addr` returned
677 /// will be non-null address pointing to a block of storage
678 /// suitable for holding an instance of `layout`.
680 /// The returned block of storage may or may not have its contents
681 /// initialized. (Extension subtraits might restrict this
682 /// behavior, e.g. to ensure initialization to particular sets of
687 /// This function is unsafe because undefined behavior can result
688 /// if the caller does not ensure that `layout` has non-zero size.
690 /// (Extension subtraits might provide more specific bounds on
691 /// behavior, e.g. guarantee a sentinel address or a null pointer
692 /// in response to a zero-size allocation request.)
696 /// Returning `Err` indicates that either memory is exhausted or
697 /// `layout` does not meet allocator's size or alignment
700 /// Implementations are encouraged to return `Err` on memory
701 /// exhaustion rather than panicking or aborting, but this is not
702 /// a strict requirement. (Specifically: it is *legal* to
703 /// implement this trait atop an underlying native allocation
704 /// library that aborts on memory exhaustion.)
706 /// Clients wishing to abort computation in response to an
707 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
708 /// rather than directly invoking `panic!` or similar.
710 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
711 unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr>;
713 /// Deallocate the memory referenced by `ptr`.
717 /// This function is unsafe because undefined behavior can result
718 /// if the caller does not ensure all of the following:
720 /// * `ptr` must denote a block of memory currently allocated via
723 /// * `layout` must *fit* that block of memory,
725 /// * In addition to fitting the block of memory `layout`, the
726 /// alignment of the `layout` must match the alignment used
727 /// to allocate that block of memory.
728 unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
730 // == ALLOCATOR-SPECIFIC QUANTITIES AND LIMITS ==
733 /// Returns bounds on the guaranteed usable size of a successful
734 /// allocation created with the specified `layout`.
736 /// In particular, if one has a memory block allocated via a given
737 /// allocator `a` and layout `k` where `a.usable_size(k)` returns
738 /// `(l, u)`, then one can pass that block to `a.dealloc()` with a
739 /// layout in the size range [l, u].
741 /// (All implementors of `usable_size` must ensure that
742 /// `l <= k.size() <= u`)
744 /// Both the lower- and upper-bounds (`l` and `u` respectively)
745 /// are provided, because an allocator based on size classes could
746 /// misbehave if one attempts to deallocate a block without
747 /// providing a correct value for its size (i.e., one within the
750 /// Clients who wish to make use of excess capacity are encouraged
751 /// to use the `alloc_excess` and `realloc_excess` instead, as
752 /// this method is constrained to report conservative values that
753 /// serve as valid bounds for *all possible* allocation method
756 /// However, for clients that do not wish to track the capacity
757 /// returned by `alloc_excess` locally, this method is likely to
758 /// produce useful results.
760 fn usable_size(&self, layout: &Layout) -> (usize, usize) {
761 (layout.size(), layout.size())
764 // == METHODS FOR MEMORY REUSE ==
765 // realloc. alloc_excess, realloc_excess
767 /// Returns a pointer suitable for holding data described by
768 /// a new layout with `layout`’s alginment and a size given
769 /// by `new_size`. To
770 /// accomplish this, this may extend or shrink the allocation
771 /// referenced by `ptr` to fit the new layout.
773 /// If this returns `Ok`, then ownership of the memory block
774 /// referenced by `ptr` has been transferred to this
775 /// allocator. The memory may or may not have been freed, and
776 /// should be considered unusable (unless of course it was
777 /// transferred back to the caller again via the return value of
780 /// If this method returns `Err`, then ownership of the memory
781 /// block has not been transferred to this allocator, and the
782 /// contents of the memory block are unaltered.
786 /// This function is unsafe because undefined behavior can result
787 /// if the caller does not ensure all of the following:
789 /// * `ptr` must be currently allocated via this allocator,
791 /// * `layout` must *fit* the `ptr` (see above). (The `new_size`
792 /// argument need not fit it.)
794 /// * `new_size` must be greater than zero.
796 /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`,
797 /// must not overflow (i.e. the rounded value must be less than `usize::MAX`).
799 /// (Extension subtraits might provide more specific bounds on
800 /// behavior, e.g. guarantee a sentinel address or a null pointer
801 /// in response to a zero-size allocation request.)
805 /// Returns `Err` only if the new layout
806 /// does not meet the allocator's size
807 /// and alignment constraints of the allocator, or if reallocation
810 /// Implementations are encouraged to return `Err` on memory
811 /// exhaustion rather than panicking or aborting, but this is not
812 /// a strict requirement. (Specifically: it is *legal* to
813 /// implement this trait atop an underlying native allocation
814 /// library that aborts on memory exhaustion.)
816 /// Clients wishing to abort computation in response to a
817 /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
818 /// rather than directly invoking `panic!` or similar.
820 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
821 unsafe fn realloc(&mut self,
824 new_size: usize) -> Result<NonNull<u8>, AllocErr> {
825 let old_size = layout.size();
827 if new_size >= old_size {
828 if let Ok(()) = self.grow_in_place(ptr, layout.clone(), new_size) {
831 } else if new_size < old_size {
832 if let Ok(()) = self.shrink_in_place(ptr, layout.clone(), new_size) {
837 // otherwise, fall back on alloc + copy + dealloc.
838 let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
839 let result = self.alloc(new_layout);
840 if let Ok(new_ptr) = result {
841 ptr::copy_nonoverlapping(ptr.as_ptr(),
843 cmp::min(old_size, new_size));
844 self.dealloc(ptr, layout);
849 /// Behaves like `alloc`, but also ensures that the contents
850 /// are set to zero before being returned.
854 /// This function is unsafe for the same reasons that `alloc` is.
858 /// Returning `Err` indicates that either memory is exhausted or
859 /// `layout` does not meet allocator's size or alignment
860 /// constraints, just as in `alloc`.
862 /// Clients wishing to abort computation in response to an
863 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
864 /// rather than directly invoking `panic!` or similar.
866 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
867 unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
868 let size = layout.size();
869 let p = self.alloc(layout);
871 ptr::write_bytes(p.as_ptr(), 0, size);
876 /// Behaves like `alloc`, but also returns the whole size of
877 /// the returned block. For some `layout` inputs, like arrays, this
878 /// may include extra storage usable for additional data.
882 /// This function is unsafe for the same reasons that `alloc` is.
886 /// Returning `Err` indicates that either memory is exhausted or
887 /// `layout` does not meet allocator's size or alignment
888 /// constraints, just as in `alloc`.
890 /// Clients wishing to abort computation in response to an
891 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
892 /// rather than directly invoking `panic!` or similar.
894 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
895 unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr> {
896 let usable_size = self.usable_size(&layout);
897 self.alloc(layout).map(|p| Excess(p, usable_size.1))
900 /// Behaves like `realloc`, but also returns the whole size of
901 /// the returned block. For some `layout` inputs, like arrays, this
902 /// may include extra storage usable for additional data.
906 /// This function is unsafe for the same reasons that `realloc` is.
910 /// Returning `Err` indicates that either memory is exhausted or
911 /// `layout` does not meet allocator's size or alignment
912 /// constraints, just as in `realloc`.
914 /// Clients wishing to abort computation in response to a
915 /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
916 /// rather than directly invoking `panic!` or similar.
918 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
919 unsafe fn realloc_excess(&mut self,
922 new_size: usize) -> Result<Excess, AllocErr> {
923 let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
924 let usable_size = self.usable_size(&new_layout);
925 self.realloc(ptr, layout, new_size)
926 .map(|p| Excess(p, usable_size.1))
929 /// Attempts to extend the allocation referenced by `ptr` to fit `new_size`.
931 /// If this returns `Ok`, then the allocator has asserted that the
932 /// memory block referenced by `ptr` now fits `new_size`, and thus can
933 /// be used to carry data of a layout of that size and same alignment as
934 /// `layout`. (The allocator is allowed to
935 /// expend effort to accomplish this, such as extending the memory block to
936 /// include successor blocks, or virtual memory tricks.)
938 /// Regardless of what this method returns, ownership of the
939 /// memory block referenced by `ptr` has not been transferred, and
940 /// the contents of the memory block are unaltered.
944 /// This function is unsafe because undefined behavior can result
945 /// if the caller does not ensure all of the following:
947 /// * `ptr` must be currently allocated via this allocator,
949 /// * `layout` must *fit* the `ptr` (see above); note the
950 /// `new_size` argument need not fit it,
952 /// * `new_size` must not be less than `layout.size()`,
956 /// Returns `Err(CannotReallocInPlace)` when the allocator is
957 /// unable to assert that the memory block referenced by `ptr`
958 /// could fit `layout`.
960 /// Note that one cannot pass `CannotReallocInPlace` to the `handle_alloc_error`
961 /// function; clients are expected either to be able to recover from
962 /// `grow_in_place` failures without aborting, or to fall back on
963 /// another reallocation method before resorting to an abort.
964 unsafe fn grow_in_place(&mut self,
967 new_size: usize) -> Result<(), CannotReallocInPlace> {
968 let _ = ptr; // this default implementation doesn't care about the actual address.
969 debug_assert!(new_size >= layout.size());
970 let (_l, u) = self.usable_size(&layout);
971 // _l <= layout.size() [guaranteed by usable_size()]
972 // layout.size() <= new_layout.size() [required by this method]
976 Err(CannotReallocInPlace)
980 /// Attempts to shrink the allocation referenced by `ptr` to fit `new_size`.
982 /// If this returns `Ok`, then the allocator has asserted that the
983 /// memory block referenced by `ptr` now fits `new_size`, and
984 /// thus can only be used to carry data of that smaller
985 /// layout. (The allocator is allowed to take advantage of this,
986 /// carving off portions of the block for reuse elsewhere.) The
987 /// truncated contents of the block within the smaller layout are
988 /// unaltered, and ownership of block has not been transferred.
990 /// If this returns `Err`, then the memory block is considered to
991 /// still represent the original (larger) `layout`. None of the
992 /// block has been carved off for reuse elsewhere, ownership of
993 /// the memory block has not been transferred, and the contents of
994 /// the memory block are unaltered.
998 /// This function is unsafe because undefined behavior can result
999 /// if the caller does not ensure all of the following:
1001 /// * `ptr` must be currently allocated via this allocator,
1003 /// * `layout` must *fit* the `ptr` (see above); note the
1004 /// `new_size` argument need not fit it,
1006 /// * `new_size` must not be greater than `layout.size()`
1007 /// (and must be greater than zero),
1011 /// Returns `Err(CannotReallocInPlace)` when the allocator is
1012 /// unable to assert that the memory block referenced by `ptr`
1013 /// could fit `layout`.
1015 /// Note that one cannot pass `CannotReallocInPlace` to the `handle_alloc_error`
1016 /// function; clients are expected either to be able to recover from
1017 /// `shrink_in_place` failures without aborting, or to fall back
1018 /// on another reallocation method before resorting to an abort.
1019 unsafe fn shrink_in_place(&mut self,
1022 new_size: usize) -> Result<(), CannotReallocInPlace> {
1023 let _ = ptr; // this default implementation doesn't care about the actual address.
1024 debug_assert!(new_size <= layout.size());
1025 let (l, _u) = self.usable_size(&layout);
1026 // layout.size() <= _u [guaranteed by usable_size()]
1027 // new_layout.size() <= layout.size() [required by this method]
1031 Err(CannotReallocInPlace)
1036 // == COMMON USAGE PATTERNS ==
1037 // alloc_one, dealloc_one, alloc_array, realloc_array. dealloc_array
1039 /// Allocates a block suitable for holding an instance of `T`.
1041 /// Captures a common usage pattern for allocators.
1043 /// The returned block is suitable for passing to the
1044 /// `alloc`/`realloc` methods of this allocator.
1046 /// Note to implementors: If this returns `Ok(ptr)`, then `ptr`
1047 /// must be considered "currently allocated" and must be
1048 /// acceptable input to methods such as `realloc` or `dealloc`,
1049 /// *even if* `T` is a zero-sized type. In other words, if your
1050 /// `Alloc` implementation overrides this method in a manner
1051 /// that can return a zero-sized `ptr`, then all reallocation and
1052 /// deallocation methods need to be similarly overridden to accept
1053 /// such values as input.
1057 /// Returning `Err` indicates that either memory is exhausted or
1058 /// `T` does not meet allocator's size or alignment constraints.
1060 /// For zero-sized `T`, may return either of `Ok` or `Err`, but
1061 /// will *not* yield undefined behavior.
1063 /// Clients wishing to abort computation in response to an
1064 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
1065 /// rather than directly invoking `panic!` or similar.
1067 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1068 fn alloc_one<T>(&mut self) -> Result<NonNull<T>, AllocErr>
1071 let k = Layout::new::<T>();
1073 unsafe { self.alloc(k).map(|p| p.cast()) }
1079 /// Deallocates a block suitable for holding an instance of `T`.
1081 /// The given block must have been produced by this allocator,
1082 /// and must be suitable for storing a `T` (in terms of alignment
1083 /// as well as minimum and maximum size); otherwise yields
1084 /// undefined behavior.
1086 /// Captures a common usage pattern for allocators.
1090 /// This function is unsafe because undefined behavior can result
1091 /// if the caller does not ensure both:
1093 /// * `ptr` must denote a block of memory currently allocated via this allocator
1095 /// * the layout of `T` must *fit* that block of memory.
1096 unsafe fn dealloc_one<T>(&mut self, ptr: NonNull<T>)
1099 let k = Layout::new::<T>();
1101 self.dealloc(ptr.cast(), k);
1105 /// Allocates a block suitable for holding `n` instances of `T`.
1107 /// Captures a common usage pattern for allocators.
1109 /// The returned block is suitable for passing to the
1110 /// `alloc`/`realloc` methods of this allocator.
1112 /// Note to implementors: If this returns `Ok(ptr)`, then `ptr`
1113 /// must be considered "currently allocated" and must be
1114 /// acceptable input to methods such as `realloc` or `dealloc`,
1115 /// *even if* `T` is a zero-sized type. In other words, if your
1116 /// `Alloc` implementation overrides this method in a manner
1117 /// that can return a zero-sized `ptr`, then all reallocation and
1118 /// deallocation methods need to be similarly overridden to accept
1119 /// such values as input.
1123 /// Returning `Err` indicates that either memory is exhausted or
1124 /// `[T; n]` does not meet allocator's size or alignment
1127 /// For zero-sized `T` or `n == 0`, may return either of `Ok` or
1128 /// `Err`, but will *not* yield undefined behavior.
1130 /// Always returns `Err` on arithmetic overflow.
1132 /// Clients wishing to abort computation in response to an
1133 /// allocation error are encouraged to call the [`handle_alloc_error`] function,
1134 /// rather than directly invoking `panic!` or similar.
1136 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1137 fn alloc_array<T>(&mut self, n: usize) -> Result<NonNull<T>, AllocErr>
1140 match Layout::array::<T>(n) {
1141 Ok(ref layout) if layout.size() > 0 => {
1143 self.alloc(layout.clone()).map(|p| p.cast())
1150 /// Reallocates a block previously suitable for holding `n_old`
1151 /// instances of `T`, returning a block suitable for holding
1152 /// `n_new` instances of `T`.
1154 /// Captures a common usage pattern for allocators.
1156 /// The returned block is suitable for passing to the
1157 /// `alloc`/`realloc` methods of this allocator.
1161 /// This function is unsafe because undefined behavior can result
1162 /// if the caller does not ensure all of the following:
1164 /// * `ptr` must be currently allocated via this allocator,
1166 /// * the layout of `[T; n_old]` must *fit* that block of memory.
1170 /// Returning `Err` indicates that either memory is exhausted or
1171 /// `[T; n_new]` does not meet allocator's size or alignment
1174 /// For zero-sized `T` or `n_new == 0`, may return either of `Ok` or
1175 /// `Err`, but will *not* yield undefined behavior.
1177 /// Always returns `Err` on arithmetic overflow.
1179 /// Clients wishing to abort computation in response to a
1180 /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
1181 /// rather than directly invoking `panic!` or similar.
1183 /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1184 unsafe fn realloc_array<T>(&mut self,
1187 n_new: usize) -> Result<NonNull<T>, AllocErr>
1190 match (Layout::array::<T>(n_old), Layout::array::<T>(n_new)) {
1191 (Ok(ref k_old), Ok(ref k_new)) if k_old.size() > 0 && k_new.size() > 0 => {
1192 debug_assert!(k_old.align() == k_new.align());
1193 self.realloc(ptr.cast(), k_old.clone(), k_new.size()).map(NonNull::cast)
1201 /// Deallocates a block suitable for holding `n` instances of `T`.
1203 /// Captures a common usage pattern for allocators.
1207 /// This function is unsafe because undefined behavior can result
1208 /// if the caller does not ensure both:
1210 /// * `ptr` must denote a block of memory currently allocated via this allocator
1212 /// * the layout of `[T; n]` must *fit* that block of memory.
1216 /// Returning `Err` indicates that either `[T; n]` or the given
1217 /// memory block does not meet allocator's size or alignment
1220 /// Always returns `Err` on arithmetic overflow.
1221 unsafe fn dealloc_array<T>(&mut self, ptr: NonNull<T>, n: usize) -> Result<(), AllocErr>
1224 match Layout::array::<T>(n) {
1225 Ok(ref k) if k.size() > 0 => {
1226 Ok(self.dealloc(ptr.cast(), k.clone()))