Tracking issue for RFC #2116: fallible collection allocation

[aturon]

This is a tracking issue for the try_reserve part of the RFC "fallible collection allocation" (rust-lang/rfcs#2116).

Steps:

• Implement the RFC #48648
  • Add HashSet::try_reserve?
• Adjust documentation (see instructions on forge)
• Stabilization PR (see instructions on forge)

API:

impl /* each of String, Vec<T>, VecDeque<T> */ {
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {…}
    pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {…}
}

impl<T> HashMap<T> {
    pub fn try_reserve(&mut self, additional: usize) -> Result<(), CollectionAllocErr> {…}
}

/// Augments `AllocErr` with a CapacityOverflow variant.
#[derive(Clone, PartialEq, Eq, Debug)]
pub enum CollectionAllocErr {
    /// Error due to the computed capacity exceeding the collection's maximum
    /// (usually `isize::MAX` bytes).
    CapacityOverflow,
    /// Error due to the allocator (see the `AllocErr` type's docs).
    AllocErr,
}

impl From<AllocErr> for CollectionAllocErr {
    fn from(AllocErr: AllocErr) -> Self { CollectionAllocErr::AllocErr }
}

impl From<LayoutErr> for CollectionAllocErr {
    fn from(_: LayoutErr) -> Self { CollectionAllocErr::CapacityOverflow }
}

[snf]

Hi, this feature will require oom and try_reserve to be implemented. I'm needing try_reserve and I'm willing to work (slowly) on it if noone else does.
I see that the previous commit by @Gankro is here and seems to match the RFC description.
Is there anything else I should consider before rebasing that PR?

[snf]

I can use some mentorship on what's the best way to implement oom=panic/abort . Should I emit a global variable through rustc depending on this case?

I was taking inspiration from #32900 but there might be an easier way to emit a boolean global variable.

[aturon]

cc @Gankro, can you help mentor?

[SimonSapin]

try_reserve methods are implemented in Nightly, but the accepted RFC also includes the ability to make allocation failure cause a panic rather than abort and that part is not implemented. Unfortunately the RFC does not discuss how this would be implemented, other than being controlled by a flag in Cargo.toml. It’s not clear to me how this can work.

[glandium]

Unfortunately the RFC does not discuss how this would be implemented, other than being controlled by a flag in Cargo.toml. It’s not clear to me how this can work.

We've been talking about panic::set_hook-like hooking for the new oom lang item in #49668, this could be how this works.

[SimonSapin]

@alexcrichton, how does #51041 fit with the goal of implementing some way to opt into oom=panic?

[alexcrichton]

@SimonSapin we'd decide that the regression is acceptable, and we'd revert the change.

[SimonSapin]

You use a conditional tense, but oom=panic is already in an accepted RFC (though the implementation strategy is not quite settled).

[alexcrichton]

Ok sure, we can figure it out in the implementation details? AFAIK there's no need to revert the change as it has basically no benefit today. It's a trivial change to revert as well, it's one line in the standard library

[3n-mb]

This example in playground asks for 1024*1024*1024*1000 bytes on a server, via v.try_reserve(len)? without giving an error.

Is this RFC implementation is not at the point, at which errors in such cases will start to show up?
Or, is this a gross over-commit by underlying OS, and this state of affairs will stay like this?
Can try_reserve in principle reserve only realistic things?

[SimonSapin]

When an error is returned is entirely dependent of the underlying allocator. As far as I know Linux usually overcommits, Windows doesn’t.

https://play.rust-lang.org/?gist=aa668f38117983d1951b58307df04880&version=nightly allocates 120 PB but fails at 130 PB, it is exhausting 48 bits of address space.

Even on Linux though, this API can be useful for 32-bit programs when exhausting the address space is much more realistic.

[SimonSapin]

#43596 was the pre-RFC feature request for oom=panic. I’ve repurposed it as the tracking issue for that feature, since it and try_reserved are likely to be stabilized at different times. This leaves this issue as tracking only try_reserve.

[snf]

#52420 will change CollectionAllocErr to CollectionAllocErr<AllocError>

[SimonSapin]

Will, or would. I’ve comment there that such a change in public API design merits being discussed separately from a large PR.

[Ericson2314]

Yeah definitely. Even if it weren't for the 2018 delaying considering these things, I wouldn't expect it to be merged quick. I just make the PR to prove the feasibility and make my ideas clearer to / interactive for others.

Ignoring the benefits of allocator polymorphism itself (that would be #42774), I see 4 big benefits:

• Self discipline: Applications can prevent themselves statically from forgetting to handled allocations failures.

• Race freedom: allocation divergence due to try_reserving insufficient space are statically prevented.

• Expressiveness: Unclear how to do try_reserve-like things for "deep" data structures (those containing indirecation).

• Library flexibility: Implement functionality just once with a parameteric error type, and you get fallibility polymorphism: downstream can instantiate with ! to get today's divergence, or AllocError to allow them to be explicitly handled.

I thus advocating going with error polymorphism and abandoning try_reverve (I rather reuse try_ for the Result<(), E> copies of every method we'll need for backwards compat). (But, my PR keeps the existing meaning of try_reserve so as to allow a transition period where people can try both approaches.)

[SimonSapin]

Firefox needs try_reserve badly enough that they forked Vec and HashMap over it. It’d be nice to stabilize.

Some of the discussion above is about oom=panic whose tracking has moved to #43596. This leaves two unresolved question:

• Whether CollectionAllocErr should gain a type parameter, with the AllocErr variant holding a value of that type, in preparation for future allocation traits having an associated type for errors. I think we can still make that change after stabilization, if the type parameter has a default. @rust-lang/libs, does that sound accurate?

• @Ericson2314, it sounds like you’re objecting to having try_reserve at all, because instead we should have try_* variations of every existing method that allocates. However reserve is such a method so this proposal is a subset of yours, not contradictory. Am I missing something?

[Ericson2314]

@SimonSapin Yes if things were done my way Firefox wouldn't be try_reserving or reserving at all, but just fallibly allocate the memory they need when they need it. That's much simpler and more robust.

(There's also the more minor quibble that under the simplest version of my plan, the Self types are different and try_reseve wouldn't be callable for the regular infallible collections. But that can be changed at the cost of more associated type magic.)

The libs team paused associated allocators to prioritize the 2018 edition. That's fine with me, but then I think it only fair that Firefox wait too. I promise as soon as the gates are open I'll rush to revive @glandium's and my PRs.

[SimonSapin]

Right, try_insert for example would be preferable to try_reserve + insert, but it doesn’t exist yet. You know as well as I do that large changes or additions are harder to get through the process, rust-lang/rfcs#2116 was designed deliberately to be minimal.

I think it only fair that Firefox wait too

It’s not about who gets candy first. RFC 2116 was submitted 14 months ago and accepted 8 months ago. The try_reserve part has been implemented 7 months ago, stabilizing it now can be a matter of flipping a switch. Allocator-generic collections however are still in the design phase with a number of open questions, they are still gonna take significant work from multiple people.

That said, there is no real urgency for try_reserve. Firefox using a forked HashMap is unfortunate in my opinion, but it works. Stabilizing try_reserve only seems to me like easy incremental improvement.

[Ericson2314]

Well it sounds like we are in something closer to agreement than usual. :)

Allocator-generic collections however are still in the design phase with a number of open questions

The code has been written and if I recall correctly works (there was one ancillary issue with trying to make default impls work well, but it is not fundamental and I believe I found a workaround beyond just requiring more boilerplate). It just needs to be read and debated.

[alexcrichton]

@SimonSapin it's been awhile since I took a look at this, but is the idea that (in the long run) every fallible method on a collection returns CollectionAllocErr<T> and the T is specialized per-method to be the "most appropriate"? In the meantime, though, we're only thinking of the try_reserve methods which would effectively return CollectionAllocErr<()> and you're thinking that we can add <T = ()> to the enum definition later?

One possible alternative to this is to avoid defining this type at all I think? For example unlike as we may have originally though AllocErr wasn't stabilized with global allocators. To that end it increases the surface area of what's to be stabilized to stabilize this feature, and it also means we're not necessarily sold on having AllocErr yet. These methods could, perhaps, return a bool for whether they succeeded or not. (this sort of depends if we think it's crucial to switch on why reservation failed, allocation and/or capacity)

I think I'd personally lean towards what you're thinking @SimonSapin by having CollectionAllocErr with a defaulted type parameter later on, if necessary. I might also advocate, as well, having either a non-exhaustive enum or an opaque struct with boolean accessors.

[SimonSapin]

Oh, I forgot that AllocErr was not stable yet. I’m fine with changing CollectionAllocErr to an opaque type for now. (A struct with a private field, to leave us more options later.) Even zero-size, though I’d still prefer Result<(), _> over bool even if they are semantically equivalent.

At the moment I don’t really have an opinion on whether CollectionAllocErr should have a type parameter. I was only responding to #48043 (comment) by saying we’ll still be able to do that later if we want. (With the RFC process hat on, to make sure possible objections are not ignored.)

This sort of depends if we think it's crucial to switch on why reservation failed, allocation and/or capacity

It looks like at least some of the code paths in Firefox track the size (and alignment) of the allocation request that failed, so the current enum might be insufficient anyway.

Alright, on further thought it may not make sense to pursue this just yet, until we figure out the rest of the story for allocation traits and error types.

[Ericson2314]

@alexcrichton So in https://github.com/rust-lang/rust/pull/52420/files I did make a CollectionAllocErr, but that's not really the important part, the associated error type (which would be the parameter) is.

Honestly, I'm not even sure CollectionAllocErr is worth it. It creates two axis with the associated type: do we hide allocation errors, and do we hide size errors? I can't imagine a case where one should cause an panic/abort and the other shouldn't. I rather have just AllocErr as is, or have AllocErr have both variants (In the memory hierarchy we can imagine that at any layer some collection/allocator gets too big, or it cannot get memory from it's backing allocator).

All this another reason, and one I initially forgot (but now remember thinking of when I rebased my PR over try_reserve was added), that stabilizing try_reserve now will tie our hands later.

[snf]

I think this is a feature that we need semi-urgently. There are projects out there that require try_reserve and this is not something that can be quickly replaced by a custom crate.
I like the idea of CollectionAllocErr with a private field but I'd like to know if anyone can think of a limitation before proceeding in implementing it.