Repository: rust
Issue: Allocator traits and std::heap
Labels: B-RFC-approved,A-allocators,T-lang,T-libs-api,B-unstable,C-tracking-issue,Libs-Tracked,S-tracking-needs-summary

📢  **This feature has a dedicated working group**, please direct comments and concerns to [the working group's repo](https://github.com/rust-lang/wg-allocators).

The remainder of this post is no longer an accurate summary of the current state; see that dedicated working group instead.

<details>
<summary>Old content</summary>

Original Post:

-----

FCP proposal: https://github.com/rust-lang/rust/issues/32838#issuecomment-336957415
FCP checkboxes: https://github.com/rust-lang/rust/issues/32838#issuecomment-336980230

---

Tracking issue for rust-lang/rfcs#1398 and the `std::heap` module.

- [x] land `struct Layout`, `trait Allocator`, and default implementations in `alloc` crate (https://github.com/rust-lang/rust/pull/42313)
- [x] decide where parts should live (e.g. default impls has dependency on `alloc` crate, but `Layout`/`Allocator` _could_ be in `libcore`...) (https://github.com/rust-lang/rust/pull/42313)
- [ ] fixme from source code: audit default implementations (in `Layout` for overflow errors, (potentially switching to overflowing_add and overflowing_mul as necessary).
- [x] decide if `realloc_in_place` should be replaced with `grow_in_place` and `shrink_in_place` ([comment](https://github.com/rust-lang/rust/issues/32838#issuecomment-208141759)) (https://github.com/rust-lang/rust/pull/42313)
- [ ] review arguments for/against associated error type (see subthread [here](https://github.com/rust-lang/rfcs/pull/1398#issuecomment-204561446))
- [ ] determine what the requirements are on the alignment provided to `fn dealloc`. (See discussion on [allocator rfc](https://github.com/rust-lang/rfcs/pull/1398#issuecomment-198584430) and [global allocator rfc](https://github.com/rust-lang/rfcs/pull/1974#issuecomment-302789872) and  [trait `Alloc` PR](https://github.com/rust-lang/rust/pull/42313#issuecomment-306202489).)
  * Is it required to deallocate with the exact `align` that you allocate with? [Concerns have been raised](https://github.com/rust-lang/rfcs/pull/1974#issuecomment-302789872) that allocators like jemalloc don't require this, and it's difficult to envision an allocator that does require this. ([more discussion](https://github.com/rust-lang/rfcs/pull/1398#issuecomment-198584430)). @ruuda and @rkruppe look like they've got the most thoughts so far on this.
- [ ] should `AllocErr` be `Error` instead? ([comment](https://github.com/rust-lang/rust/pull/42313#discussion_r122580471))
- [x] Is it required to deallocate with the *exact* size that you allocate with? With the `usable_size` business we may wish to allow, for example, that you if you allocate with `(size, align)` you must deallocate with a size somewhere in the range of `size...usable_size(size, align)`. It appears that jemalloc is totally ok with this (doesn't require you to deallocate with a *precise* `size` you allocate with) and this would also allow `Vec` to naturally take advantage of the excess capacity jemalloc gives it when it does an allocation. (although actually doing this is also somewhat orthogonal to this decision, we're just empowering `Vec`). So far @Gankro has most of the thoughts on this. (@alexcrichton believes this was settled in https://github.com/rust-lang/rust/pull/42313 due to the definition of "fits")
- [ ] similar to previous question: Is it required to deallocate with the *exact* alignment that you allocated with? (See comment from [5 June 2017](https://github.com/rust-lang/rust/pull/42313#issuecomment-306202489))
- [x] OSX/`alloc_system` is buggy on *huge* alignments (e.g.  an align of `1 << 32`) https://github.com/rust-lang/rust/issues/30170 #43217
- [ ] should `Layout` provide a `fn stride(&self)` method? (See also https://github.com/rust-lang/rfcs/issues/1397, https://github.com/rust-lang/rust/issues/17027 )
- [x] `Allocator::owns` as a method? https://github.com/rust-lang/rust/issues/44302

State of `std::heap` after https://github.com/rust-lang/rust/pull/42313:

```rust
pub struct Layout { /* ... */ }

impl Layout {
    pub fn new<T>() -> Self;
    pub fn for_value<T: ?Sized>(t: &T) -> Self;
    pub fn array<T>(n: usize) -> Option<Self>;
    pub fn from_size_align(size: usize, align: usize) -> Option<Layout>;
    pub unsafe fn from_size_align_unchecked(size: usize, align: usize) -> Layout;

    pub fn size(&self) -> usize;
    pub fn align(&self) -> usize;
    pub fn align_to(&self, align: usize) -> Self;
    pub fn padding_needed_for(&self, align: usize) -> usize;
    pub fn repeat(&self, n: usize) -> Option<(Self, usize)>;
    pub fn extend(&self, next: Self) -> Option<(Self, usize)>;
    pub fn repeat_packed(&self, n: usize) -> Option<Self>;
    pub fn extend_packed(&self, next: Self) -> Option<(Self, usize)>;
}

pub enum AllocErr {
    Exhausted { request: Layout },
    Unsupported { details: &'static str },
}

impl AllocErr {
    pub fn invalid_input(details: &'static str) -> Self;
    pub fn is_memory_exhausted(&self) -> bool;
    pub fn is_request_unsupported(&self) -> bool;
    pub fn description(&self) -> &str;
}

pub struct CannotReallocInPlace;

pub struct Excess(pub *mut u8, pub usize);

pub unsafe trait Alloc {
    // required
    unsafe fn alloc(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn dealloc(&mut self, ptr: *mut u8, layout: Layout);

    // provided
    fn oom(&mut self, _: AllocErr) -> !;
    fn usable_size(&self, layout: &Layout) -> (usize, usize);
    unsafe fn realloc(&mut self,
                      ptr: *mut u8,
                      layout: Layout,
                      new_layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<*mut u8, AllocErr>;
    unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr>;
    unsafe fn realloc_excess(&mut self,
                             ptr: *mut u8,
                             layout: Layout,
                             new_layout: Layout) -> Result<Excess, AllocErr>;
    unsafe fn grow_in_place(&mut self,
                            ptr: *mut u8,
                            layout: Layout,
                            new_layout: Layout) -> Result<(), CannotReallocInPlace>;
    unsafe fn shrink_in_place(&mut self,
                              ptr: *mut u8,
                              layout: Layout,
                              new_layout: Layout) -> Result<(), CannotReallocInPlace>;

    // convenience
    fn alloc_one<T>(&mut self) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn dealloc_one<T>(&mut self, ptr: Unique<T>)
        where Self: Sized;
    fn alloc_array<T>(&mut self, n: usize) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn realloc_array<T>(&mut self,
                               ptr: Unique<T>,
                               n_old: usize,
                               n_new: usize) -> Result<Unique<T>, AllocErr>
        where Self: Sized;
    unsafe fn dealloc_array<T>(&mut self, ptr: Unique<T>, n: usize) -> Result<(), AllocErr>
        where Self: Sized;
}

/// The global default allocator
pub struct Heap;

impl Alloc for Heap {
    // ...
}

impl<'a> Alloc for &'a Heap {
    // ...
}

/// The "system" allocator
pub struct System;

impl Alloc for System {
    // ...
}

impl<'a> Alloc for &'a System {
    // ...
}
```
</details>