Fallible allocation (via Associated Error type)

[Ericson2314]

Following up from https://rust-lang.zulipchat.com/#narrow/stream/197181-t-libs.2Fwg-allocators/topic/Collections.20beyond.20box.2C.20allocation.20fallibility . I've done a preliminary rebase of rust-lang/rust#52420 at https://github.com/QuiltOS/rust/tree/allocator-error (old versions are https://github.com/QuiltOS/rust/tree/allocator-error-old, https://github.com/QuiltOS/rust/tree/allocator-error-old-1, etc.)

---

If we add an associated Err type to Alloc, we can set it to ! to indicate allocation is infallible (panics, aborts, etc). Allocators should be written with a non-empty Alloc::Err, but a AbortAdapter<A> is provided which calls handle_alloc_error so for<A: Alloc> <AbortAdapter<A> as Alloc>::Err = !.

This has many benefits.

1. We get try_ and traditional versions of every collections method that supports fallibility it for no extra cost! This is done by threading the abstract error type. We don't need to duplicate the original method, but can simply do:

   struct Collection<T, A: Alloc = AbortAdaptor<Global>> { ... }
   
   impl<T, A> Collection<T, A> {
     fn try_foo(&self) -> Result<T, A::Err> {
       ...
     }
   }
   
   impl<T> Collection<T> { // A::Err = !
     fn foo(&self) -> T {
       let Ok(x) = self.try_foo();
       x
     }
   }

   The legacy version would just call the non-try_ version and panic-free unwrap the Result<T, !>. Yes we have twice as many methods, but don't have any duplicated logic.

2. Any container (or individual method on the container) that can not handle fallible allocation can require Err = ! so as not to hold back the alloc-parameterization and fallible-allocation-recovery of the other containers. I.e. this proposal reduces the risk of refactoring the collection in that there's no all-or-nothing bifurcation of outcomes.

3. Polymorphism all the way up. Just as collections are fallibility-polymorphic with the try_methods (perhaps they should be renamed to indicate the are not always fallible), other crates using collections can also use A::Err to also be fallibility-polymorphic. This avoids an ecosystem split between those that want and don't want to manually deal with allocation failure.

Note that this seems to impose a downside of each collection having to commit to a fallibility up front. But since AbortAdapter can be #[repr(transparent)], we can freely cast/borrow between the two.

---

Original unclear version for posterity:

If we add an associated Err type to Alloc, we can set it to ! to indicate allocation is infallible (panics, aborts, etc). This has two purposes:

1. We instantly get try_ versions of every method that supports it for free by threading a non-empty error type. The legacy version would just call the non-try_ version and unwrap the Result<T, !>. Yes we have twice as many methods, but don't have any duplicated logic.

2. Any container (or individual method on the container) that can not handle fallible allocation can require Err = ! so as not to hold back the alloc-parameterization and fallible-allocation-recovery of the other containers.

[glandium]

The current methods don't return a Result, how do you propose to reconcile this?

[Ericson2314]

@glandium See the first point: make a bunch of try_* versions that do. I don't consider this much of a cost, because no plan to support fallible allocation without race conditions and with backwards compat will avoid new methods.

[glandium]

The first point kind of was not clear about what it means.

[TimDiekmann]

Where the try_ methods would be defined? In an extension trait? Or change the whole Alloc trait to add the methods?

[scottjmaddox]

I'm not sure how best to go about doing it, but I strongly support Rust adding some support for fallible allocation.

Has there already been discussion about different approaches? Would something like a FallibleAlloc trait make sense? And Alloc could be blanket implemented for FallibleAlloc<Error=!>?

[TimDiekmann]

Has there already been discussion about different approaches?

I know there are some discussions floating around on github and internals.rlo on fallible allocation, but I cannot provide a link atm., those threads are pretty long and spread all over the platforms.

Would something like a FallibleAlloc trait make sense? And Alloc could be blanket implemented for FallibleAlloc<Error=!>?

To me this makes sense, however I'd name them Alloc<Error = ??> and InfallibleAlloc. Then you provide an Alloc implementation and InfallibleAlloc is provided for Alloc<Error = !>.

[scottjmaddox]

To me this makes sense, however I'd name them Alloc<Error = ??> and InfallibleAlloc. Then you provide an Alloc implementation and InfallibleAlloc is provided for Alloc<Error = !>.

Yeah, that would probably be preferable. Has that ship already sailed, though? I think I saw discussions about Alloc being stabilized. Maybe not yet, though.

[TimDiekmann]

The alloc crate has been stabilized. The Alloc trait is gated behind allocator_api and is likely to be changed this way or that.

[SimonSapin]

The Alloc trait (currently unstable) is already fallible: most methods return a Result.

The try_* methods mentioned above refer not to methods of the Alloc trait, but to methods of e.g. collections that internally use heap allocation. For example Vec::try_push that returns an Err instead of aborting the process when allocation fails. We have an accepted RFC for this (tracking issue: rust-lang/rust#48043) that proposes try_reserve and try_reserve_exact on variable-size collections. This is implemented, but still unstable mostly because of uncertainty around what the error type should be. This RFC discusses options for extending this pattern to other APIs such as try_push, recognizing that what’s there is a the bare minimum (e.g. you can do vec.try_reserve(1)?; vec.push(x)) but is not ergonomic, but does not propose a concrete solution.

---

Separately, for implementing APIs like Vec::push that are infallible (they don’t return a Result), code like this is a very common pattern:

let some_layout = Layout::from_size_align(…);
let ptr = some_allocator
    .alloc(some_layout)
    .unwrap_or_else(|_| std::alloc::handle_alloc_error(some_layout));

To simplify such code, there was discussion in at least https://internals.rust-lang.org/t/pre-rfc-changing-the-alloc-trait/7487 to have APIs like the Alloc trait (possibly as another trait that can be implemented for the same types, or as a wrapper type) for infallible allocation. The alloc method would return NonNull<u8> without a Result, and that API would call handle_alloc_error itself on allocation failure.

---

While adding an Err associated type in the Alloc trait is something we can do, it’s not clear to my why that would be interesting. In particular, for the two topics discussed above:

• Fallible APIs for collections might want a different error type than the Alloc trait:

  When handling an allocation error, some useful information to have is the layout (or at least the size) of the allocation request that failed. (This is why std::alloc::handle_alloc_error takes a Layout parameter.) In Vec::try_push or HashMap::try_insert, that information should be part of the error type so that the called doesn’t have to guess at the collection’s allocation strategy. In Alloc::alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> however, the caller already knows what Layout value it just passed, and having a zero-size error type is nice as it keeps the entire Result pointer-sized.

• For the ergonomics of implementing infallible collections APIs, Result<T, !> is barely an improvement over some other Result. You’d still need .unwrap() or some future API of Result<T, !> in order to get at the T value. So an associated error type does not remove the ergonomic need for an InfallibleAlloc API.

[TimDiekmann]

Fallible APIs for collections might want a different error type than the Alloc trait

Allocators may provide additional information, why an allocation failed. For example a stack allocator could return, that the stack is full, and only N bytes are free to be used.

For the ergonomics of implementing infallible collections APIs, Result<T, !> is barely an improvement over some other Result. You’d still need .unwrap() or some future API of Result<T, !> in order to get at the T value.

Result<T, !>::unwrap() is a noop while Result<T, AllocErr>::unwrap() requires a branch.

[SimonSapin]

This unwrap is a noop in optimized machine code, but it still needs to be present in source code so it’s less convenient than an API that returns a bare T (or doesn’t return).

[gnzlbg]

We instantly get try_ versions of every method that supports it for free by threading a non-empty error type. The legacy version would just call the non-try_ version and unwrap the Result<T, !>. Yes we have twice as many methods, but don't have any duplicated logic.

@Ericson2314 Alternatively, instead of duplicating all methods again as try_, an associated AllocHandle::Err type allows implementors to provide different handles with different error types. For example, for a given allocator like Jemalloc, we can provide two handles, a JemallocFallibleHandle, that properly reports errors, and a JemallocInfallibleHandle that has Err = !.

This allows users to pick whatever they need when they need it, without having to hope that collections and such properly use try_.