//! Memory allocation APIs

#![stable(feature = "alloc_module", since = "1.28.0")]

#[cfg(not(feature = "ferrocene_certified"))]

mod global;

mod layout;

#[stable(feature = "global_alloc", since = "1.28.0")]

#[cfg(not(feature = "ferrocene_certified"))]

pub use self::global::GlobalAlloc;

#[stable(feature = "alloc_layout", since = "1.28.0")]

pub use self::layout::Layout;

#[stable(feature = "alloc_layout", since = "1.28.0")]

#[deprecated(

    since = "1.52.0",

    note = "Name does not follow std convention, use LayoutError",

    suggestion = "LayoutError"

)]

#[allow(deprecated, deprecated_in_future)]

#[cfg(not(feature = "ferrocene_certified"))]

pub use self::layout::LayoutErr;

#[stable(feature = "alloc_layout_error", since = "1.50.0")]

#[cfg(not(feature = "ferrocene_certified"))]

pub use self::layout::LayoutError;

#[cfg(not(feature = "ferrocene_certified"))]

use crate::error::Error;

#[cfg(not(feature = "ferrocene_certified"))]

use crate::fmt;

#[cfg(not(feature = "ferrocene_certified"))]

use crate::ptr::{self, NonNull};

/// The `AllocError` error indicates an allocation failure

/// that may be due to resource exhaustion or to

/// something wrong when combining the given input arguments with this

/// allocator.

#[unstable(feature = "allocator_api", issue = "32838")]

#[derive(Copy, Clone, PartialEq, Eq, Debug)]

#[cfg(not(feature = "ferrocene_certified"))]

pub struct AllocError;

#[unstable(

    feature = "allocator_api",

    reason = "the precise API and guarantees it provides may be tweaked.",

    issue = "32838"

)]

#[cfg(not(feature = "ferrocene_certified"))]

impl Error for AllocError {}

// (we need this for downstream impl of trait Error)

#[unstable(feature = "allocator_api", issue = "32838")]

#[cfg(not(feature = "ferrocene_certified"))]

impl fmt::Display for AllocError {

    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {

        f.write_str("memory allocation failed")

    }

}

/// An implementation of `Allocator` can allocate, grow, shrink, and deallocate arbitrary blocks of

/// data described via [`Layout`][].

///

/// `Allocator` is designed to be implemented on ZSTs, references, or smart pointers.

/// An allocator for `MyAlloc([u8; N])` cannot be moved, without updating the pointers to the

/// allocated memory.

///

/// In contrast to [`GlobalAlloc`][], `Allocator` allows zero-sized allocations. If an underlying

/// allocator does not support this (like jemalloc) or responds by returning a null pointer

/// (such as `libc::malloc`), this must be caught by the implementation.

///

/// ### Currently allocated memory

///

/// Some of the methods require that a memory block is *currently allocated* by an allocator.

/// This means that:

///  * the starting address for that memory block was previously

///    returned by [`allocate`], [`grow`], or [`shrink`], and

///  * the memory block has not subsequently been deallocated.

///

/// A memory block is deallocated by a call to [`deallocate`],

/// or by a call to [`grow`] or [`shrink`] that returns `Ok`.

/// A call to `grow` or `shrink` that returns `Err`,

/// does not deallocate the memory block passed to it.

///

/// [`allocate`]: Allocator::allocate

/// [`grow`]: Allocator::grow

/// [`shrink`]: Allocator::shrink

/// [`deallocate`]: Allocator::deallocate

///

/// ### Memory fitting

///

/// Some of the methods require that a `layout` *fit* a memory block or vice versa. This means that the

/// following conditions must hold:

///  * the memory block must be *currently allocated* with alignment of [`layout.align()`], and

///  * [`layout.size()`] must fall in the range `min ..= max`, where:

///    - `min` is the size of the layout used to allocate the block, and

///    - `max` is the actual size returned from [`allocate`], [`grow`], or [`shrink`].

///

/// [`layout.align()`]: Layout::align

/// [`layout.size()`]: Layout::size

///

/// # Safety

///

/// Memory blocks that are [*currently allocated*] by an allocator,

/// must point to valid memory, and retain their validity until either:

///  - the memory block is deallocated, or

///  - the allocator is dropped.

///

/// Copying, cloning, or moving the allocator must not invalidate memory blocks returned from it.

/// A copied or cloned allocator must behave like the original allocator.

///

/// A memory block which is [*currently allocated*] may be passed to

/// any method of the allocator that accepts such an argument.

///

/// [*currently allocated*]: #currently-allocated-memory

#[unstable(feature = "allocator_api", issue = "32838")]

#[cfg(not(feature = "ferrocene_certified"))]

pub unsafe trait Allocator {

    /// Attempts to allocate a block of memory.

    ///

    /// On success, returns a [`NonNull<[u8]>`][NonNull] meeting the size and alignment guarantees of `layout`.

    ///

    /// The returned block may have a larger size than specified by `layout.size()`, and may or may

    /// not have its contents initialized.

    ///

    /// The returned block of memory remains valid as long as it is [*currently allocated*] and the shorter of:

    ///   - the borrow-checker lifetime of the allocator type itself.

    ///   - as long as the allocator and all its clones have not been dropped.

    ///

    /// [*currently allocated*]: #currently-allocated-memory

    ///

    /// # Errors

    ///

    /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet

    /// allocator's size or alignment constraints.

    ///

    /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or

    /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement

    /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)

    ///

    /// Clients wishing to abort computation in response to an allocation error are encouraged to

    /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.

    ///

    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html

    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError>;

    /// Behaves like `allocate`, but also ensures that the returned memory is zero-initialized.

    ///

    /// # Errors

    ///

    /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet

    /// allocator's size or alignment constraints.

    ///

    /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or

    /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement

    /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)

    ///

    /// Clients wishing to abort computation in response to an allocation error are encouraged to

    /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.

    ///

    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html

    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {

        let ptr = self.allocate(layout)?;

        // SAFETY: `alloc` returns a valid memory block

        unsafe { ptr.as_non_null_ptr().as_ptr().write_bytes(0, ptr.len()) }

        Ok(ptr)

    }

    /// Deallocates the memory referenced by `ptr`.

    ///

    /// # Safety

    ///

    /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator, and

    /// * `layout` must [*fit*] that block of memory.

    ///

    /// [*currently allocated*]: #currently-allocated-memory

    /// [*fit*]: #memory-fitting

    unsafe fn deallocate(&self, ptr: NonNull<u8>, layout: Layout);

    /// Attempts to extend the memory block.

    ///

    /// Returns a new [`NonNull<[u8]>`][NonNull] containing a pointer and the actual size of the allocated

    /// memory. The pointer is suitable for holding data described by `new_layout`. To accomplish

    /// this, the allocator may extend the allocation referenced by `ptr` to fit the new layout.

    ///

    /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been

    /// transferred to this allocator. Any access to the old `ptr` is Undefined Behavior, even if the

    /// allocation was grown in-place. The newly returned pointer is the only valid pointer

    /// for accessing this memory now.

    ///

    /// If this method returns `Err`, then ownership of the memory block has not been transferred to

    /// this allocator, and the contents of the memory block are unaltered.

    ///

    /// # Safety

    ///

    /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.

    /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).

    /// * `new_layout.size()` must be greater than or equal to `old_layout.size()`.

    ///

    /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.

    ///

    /// [*currently allocated*]: #currently-allocated-memory

    /// [*fit*]: #memory-fitting

    ///

    /// # Errors

    ///

    /// Returns `Err` if the new layout does not meet the allocator's size and alignment

    /// constraints of the allocator, or if growing otherwise fails.

    ///

    /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or

    /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement

    /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)

    ///

    /// Clients wishing to abort computation in response to an allocation error are encouraged to

    /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.

    ///

    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html

    unsafe fn grow(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        debug_assert!(

            new_layout.size() >= old_layout.size(),

            "`new_layout.size()` must be greater than or equal to `old_layout.size()`"

        );

        let new_ptr = self.allocate(new_layout)?;

        // SAFETY: because `new_layout.size()` must be greater than or equal to

        // `old_layout.size()`, both the old and new memory allocation are valid for reads and

        // writes for `old_layout.size()` bytes. Also, because the old allocation wasn't yet

        // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is

        // safe. The safety contract for `dealloc` must be upheld by the caller.

        unsafe {

            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_layout.size());

            self.deallocate(ptr, old_layout);

        }

        Ok(new_ptr)

    }

    /// Behaves like `grow`, but also ensures that the new contents are set to zero before being

    /// returned.

    ///

    /// The memory block will contain the following contents after a successful call to

    /// `grow_zeroed`:

    ///   * Bytes `0..old_layout.size()` are preserved from the original allocation.

    ///   * Bytes `old_layout.size()..old_size` will either be preserved or zeroed, depending on

    ///     the allocator implementation. `old_size` refers to the size of the memory block prior

    ///     to the `grow_zeroed` call, which may be larger than the size that was originally

    ///     requested when it was allocated.

    ///   * Bytes `old_size..new_size` are zeroed. `new_size` refers to the size of the memory

    ///     block returned by the `grow_zeroed` call.

    ///

    /// # Safety

    ///

    /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.

    /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).

    /// * `new_layout.size()` must be greater than or equal to `old_layout.size()`.

    ///

    /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.

    ///

    /// [*currently allocated*]: #currently-allocated-memory

    /// [*fit*]: #memory-fitting

    ///

    /// # Errors

    ///

    /// Returns `Err` if the new layout does not meet the allocator's size and alignment

    /// constraints of the allocator, or if growing otherwise fails.

    ///

    /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or

    /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement

    /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)

    ///

    /// Clients wishing to abort computation in response to an allocation error are encouraged to

    /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.

    ///

    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html

    unsafe fn grow_zeroed(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        debug_assert!(

            new_layout.size() >= old_layout.size(),

            "`new_layout.size()` must be greater than or equal to `old_layout.size()`"

        );

        let new_ptr = self.allocate_zeroed(new_layout)?;

        // SAFETY: because `new_layout.size()` must be greater than or equal to

        // `old_layout.size()`, both the old and new memory allocation are valid for reads and

        // writes for `old_layout.size()` bytes. Also, because the old allocation wasn't yet

        // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is

        // safe. The safety contract for `dealloc` must be upheld by the caller.

        unsafe {

            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), old_layout.size());

            self.deallocate(ptr, old_layout);

        }

        Ok(new_ptr)

    }

    /// Attempts to shrink the memory block.

    ///

    /// Returns a new [`NonNull<[u8]>`][NonNull] containing a pointer and the actual size of the allocated

    /// memory. The pointer is suitable for holding data described by `new_layout`. To accomplish

    /// this, the allocator may shrink the allocation referenced by `ptr` to fit the new layout.

    ///

    /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been

    /// transferred to this allocator. Any access to the old `ptr` is Undefined Behavior, even if the

    /// allocation was shrunk in-place. The newly returned pointer is the only valid pointer

    /// for accessing this memory now.

    ///

    /// If this method returns `Err`, then ownership of the memory block has not been transferred to

    /// this allocator, and the contents of the memory block are unaltered.

    ///

    /// # Safety

    ///

    /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator.

    /// * `old_layout` must [*fit*] that block of memory (The `new_layout` argument need not fit it.).

    /// * `new_layout.size()` must be smaller than or equal to `old_layout.size()`.

    ///

    /// Note that `new_layout.align()` need not be the same as `old_layout.align()`.

    ///

    /// [*currently allocated*]: #currently-allocated-memory

    /// [*fit*]: #memory-fitting

    ///

    /// # Errors

    ///

    /// Returns `Err` if the new layout does not meet the allocator's size and alignment

    /// constraints of the allocator, or if shrinking otherwise fails.

    ///

    /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or

    /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement

    /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)

    ///

    /// Clients wishing to abort computation in response to an allocation error are encouraged to

    /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.

    ///

    /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html

    unsafe fn shrink(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        debug_assert!(

            new_layout.size() <= old_layout.size(),

            "`new_layout.size()` must be smaller than or equal to `old_layout.size()`"

        );

        let new_ptr = self.allocate(new_layout)?;

        // SAFETY: because `new_layout.size()` must be lower than or equal to

        // `old_layout.size()`, both the old and new memory allocation are valid for reads and

        // writes for `new_layout.size()` bytes. Also, because the old allocation wasn't yet

        // deallocated, it cannot overlap `new_ptr`. Thus, the call to `copy_nonoverlapping` is

        // safe. The safety contract for `dealloc` must be upheld by the caller.

        unsafe {

            ptr::copy_nonoverlapping(ptr.as_ptr(), new_ptr.as_mut_ptr(), new_layout.size());

            self.deallocate(ptr, old_layout);

        }

        Ok(new_ptr)

    }

    /// Creates a "by reference" adapter for this instance of `Allocator`.

    ///

    /// The returned adapter also implements `Allocator` and will simply borrow this.

    #[inline(always)]

    fn by_ref(&self) -> &Self

    where

        Self: Sized,

    {

        self

    }

}

#[unstable(feature = "allocator_api", issue = "32838")]

#[cfg(not(feature = "ferrocene_certified"))]

unsafe impl<A> Allocator for &A

where

    A: Allocator + ?Sized,

{

    #[inline]

    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {

        (**self).allocate(layout)

    }

    #[inline]

    fn allocate_zeroed(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {

        (**self).allocate_zeroed(layout)

    }

    #[inline]

        // SAFETY: the safety contract must be upheld by the caller

    #[inline]

    unsafe fn grow(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        // SAFETY: the safety contract must be upheld by the caller

        unsafe { (**self).grow(ptr, old_layout, new_layout) }

    }

    #[inline]

    unsafe fn grow_zeroed(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        // SAFETY: the safety contract must be upheld by the caller

        unsafe { (**self).grow_zeroed(ptr, old_layout, new_layout) }

    }

    #[inline]

    unsafe fn shrink(

        &self,

        ptr: NonNull<u8>,

        old_layout: Layout,

        new_layout: Layout,

    ) -> Result<NonNull<[u8]>, AllocError> {

        // SAFETY: the safety contract must be upheld by the caller

        unsafe { (**self).shrink(ptr, old_layout, new_layout) }

    }

}