text:
fallible collection allocation 1.0

Add minimal support for fallible allocations to the standard collection APIs. This is done in two ways:

For users with unwinding, an oom=panic configuration is added to make global allocators panic on oom.
For users without unwinding, a try_reserve() -> Result<(), CollectionAllocErr> method is added.

The former is sufficient to unwinding users, but the latter is insufficient for the others (although it is a decent 80/20 solution). Completing the no-unwinding story is left for future work.
Rendered

Updated link:
Rendered

I'm really sorry this isn't perfect. I am just deeply exhausted with working on this problem right now, and need to push out what I have just to get it out there and focus on something else for a bit.
I'm not 100% convinced with all my "don't rock the boat" rationales for CollectionAllocErr, and could probably be very easily convinced to change that. It's just that my default stance on this kinda stuff is "don't touch anything, because the Servo team probably is relying on it in 17 different ways that will make me sad".

I think the plan for unwinding is terrible. I could support try_reserve as a stop-gap measure on the way to full support.

Similar to the embedded case, handling allocation failure at the granularity of tasks is ideal for quality-of-implementation purposes. However, unlike embedded development, it isn't considered practical (in terms of cost) to properly take control of everything and ensure allocation failure is handled robustly.

There is no evidence of this not being considered practical.
More in general, the server use case seems a little thin. I've already mentioned in the internals thread that there's a lot more to be considered there: servers come in different shapes and sizes. Considering one of Rust's 2017 goals is “Rust should be well-equipped for writing robust, high-scale servers” I think this use case (or, I'd like to argue, use cases) should be explored in more detail.
Depending on unwinding for error handling is a terrible idea and entirely contrary to Rust best practices. Besides being counteridiomatic, recovering from unwinding doesn't work well in at least three cases:

Platforms without unwinding support. Not really any need to go into detail here, as the RFC describes it pretty well.
FFI. Unwinding is not supported across FFI boundaries. Allocation errors now result in a relatively clean abort. With this RFC, with unwinding from allocation errors through FFI can result in weird/non-deterministic/undefined behavior.
Synchronization primitives You can't use any of the standard synchronization primitives such as Mutex, Once, RwLock, if you expect your code to unwind because of the possibility of lock poisoning. This was also already mentioned in the internals thread.

Using unwinding to contain errors at task granularity is completely idiomatic. It's why Rust bothers to have unwinding at all. Allowing OOMs to panic in addition to their current behavior is totally in line with this. It's not a full solution, but it is a necessary part of one.

@rpjohnst I don't know why you :-1:ed me, in your comment you seem to a gree with me?

I suggest that the filename for this RFC be changed to something that isn't quite so subtle.
(The current filename, "alloc-me-like-one-of-your-french-girls.md", is a quote/meme from the movie "Titanic"; I infer that reference is meant to bring to mind "fallibility", but I needed some help along the way.)

Using unwinding to contain errors at task granularity is completely idiomatic.

Only as a last resort, such that that one assertion failure doesn't take down your whole process accidentally. Unwinding should not be used for errors that are more or less expected and you know how to deal with. https://doc.rust-lang.org/stable/book/second-edition/ch09-03-to-panic-or-not-to-panic.html

Yes, precisely. In many situations, allocation failure is unexpected and has no meaningful response at a granularity smaller than a task. This is a reason to support oom=panic rather than just abort.

@Gankro Thanks for all the hard work!
However, I also don't like unwinding as error handling. Unwinding should only happen when I have signaled that I don't have anything to do to help; IMHO, it is damage control, rather than error handling.
Have there been any proposals to add some sort of set_oom_handler to the allocator interface? I am imagining something like the following:
enum OOMOutcome {
    Resolved(*const u8), // OOM was resolved and here is the allocation

    // Could not resolve the OOM, so do what you have to
    #[cfg(oom=panic)]
    Panic,
    #[cfg(oom=abort)]
    Abort,
}

fn set_oom_handler<H>(handler: H)
    where H: Fn(/* failed operation args... */) -> OOMOutcome;

You would then call set_oom_handler with your handler at the beginning of your program. Your handler can then choose what it wants to happen, including triggering a GC or whatever...
The benefit of this approach is that the existing interface doesn't have to change at all, and applications don't have choose to use try_reserve vs the existing things.
An alternate approach would be to make the oom_handler a language item or something (but that seems more suitable for the global allocator than collection allocators).
Yet another approach would be to make the OOM handler a type that implements a trait. Allocators would then be generic over their OOMHandler type.

Great idea, @mark-i-m. In a server app, I'd grab a chunk of memory on startup, then in my OOM handler:

set max_inflight_requests = inflight_requests - 1
send back-pressure/notify the monitoring, traffic and instance manager
resolve the allocation using some of the chunk, so the request can succeed

On operating systems that error on allocation as opposed to access, this would remove the need to manually tune the app for request load as a function of memory consumption.
Thanks @Gankro for your work on this RFC.

@Gankro I have mixed feelings about this RFC. I think this is a design, it provides me with the ability to write a VecAllocExt trait that gives me try_push and friends that would be ergonomic enough to provide a short path to an eventual stability, and these are the parts that I like. It's useful! But also, it's very imperfect, and (without going into details) I would like to see most of the internals to be completely redone before it's stabilized.
Still, it's much better than the current situation, and it doesn't have any drawbacks I can see as long as the guts are unstable (taking into account that application/firmware code will be written against this), so I'm favor of merging this even as-is.

Perhaps this could be an experimental RFC until we get experience with what doesn't work so well? That's seemed to work well in the past for the allocator interfaces...

Given the constraints, I'd say this is good enough.
I have only one question, what are the semantics of try_reserve on a HashMap ? That is, If I want to insert an element into a HashMap and I do something like hash_map.try_reserve(hash_map.len() + 1) am I guaranteed that on insertion the HasMap won't try to allocate?

@gnzlbg that's implementation detail. The stdlib version, for example, is able guarantee room for any item in advance. Some variants though can't 100% guarantee room without knowing the dataset. Hopscotch and cuckoo hash tables come to my mind as examples.

@arthurprs IIUC the whole point of try_reserve is to let you use std::collections without panic!ing on OOM. With the guarantee that "if try_reserve(N) succeeds, the collection will grow up to size N without allocating new memory", avoiding panics is "possible";  neithert good, nor ergonomic, nor reliable, but if you are careful, still doable.
However, if try_reserve doesn't guarantee this, then I cannot avoid OOM even if I am careful. That is, why would I actually call try_reserve instead of reserve if I can get an OOM panic! anyway?
So... to me this guarantee is not an implementation detail of try_reserve, but its reason for existing. Without this guarantee, I really don't see how the method can be used to do anything useful (*).
(*) unless we add try_... variants of other insertion methods.

I don't disagree with your overall idea, I'm just saying that it can't be done for ALL data structures.

I don't disagree with your overall idea, I'm just saying that it can't be done for ALL data structures.

@arthurprs This is why I was asking, I agree with you on this.

I'm going to answer @RalfJung's question on i.r-l.o here to keep the discussion in one place:

@RalfJung wrote

@jethrogb wrote
Unwinding is not a panacea. Depending on unwinding for continuity makes it so that you can’t use std::sync::{Mutex, Once, RwLock} anywhere in your code because of std::sync::PoisonError.

Could you elaborate? Poisoning actually helps dealing with unwinding; if it wasn’t for poisoning, unwinding would be much more likely to introduce subtle bugs into programs. So it actually seems to me like especially when you do unwinding should you use concurrency primitives that do poisoning.
If you don’t do unwinding, things will never be poisoned anyway.

(Sorry, this turned into quite a long post. Please bear with me)
The problem with unwinding is that “handler”-level is not the right place to handle errors. Throughout the rest of this post, keep in mind that while just like it's possible to write correct code in C++, I understand that it's possible to write correct code in Rust using unwinding. It's just not a good way in the sense that it's a giant footgun.
Here's a simple implementation of a synchronous stack:
struct SyncStack<T> {
    vec: Mutex<Vec<T>>
}

impl<T> SyncStack<T> {
    fn push(&self, t: T) {
        match self.vec.lock() {
            Ok(ref mut vec) => vec.push(t),
            Err(poison) => (/* what do I do here? is `inner` even valid? */)
        }
    }
}

Now I'm sure you (Ralf) have a proof somewhere that if any code in the Vec implementation panics, its internal invariants have all been upheld. That's great! But what about user's invariants?
struct Worker { /* ... */ }
struct Pool {
    // always `Some` when `Mutex` is not locked
    worker: Mutex<Option<Worker>>
}
impl Pool {
    /// N.B. `F` must not panic
    fn do_work<F: FnOnce(Worker) -> Worker>(&self, work: F) {
        let mut worker = self.worker.lock().unwrap();
        *worker = Some(work(worker.take().unwrap(/* oops, could have been `None`! */)));
    }
}

If my work contains any kind of allocation, and failed allocations would panic, this would now panic where it wouldn't before. Even if this example would be written to check for None in the PoisonError case, where would the Pool get a new Worker from? The previous one was dropped in the unwind. Moreover, even if we'd use catch_unwind here, the Worker was moved to the closure and we're never getting it back! If we used idiomatic error handling instead of unwinding, you would return (Result<...>, Worker) or something like that, and there wouldn't be a problem.
Let's look at Once. Well, we're looking at some other construct that uses Once internally for extra non-obviousness:
struct Certificate { /*...*/ }

fn get_certificates() -> Box<Iterator<Item=Certificate>> {
    unimplemented!()
}

lazy_static! {
    static ref ROOT_CERTS: Vec<Certificate> = get_certificates().collect();
}

If the collect runs out of memory, there is no way to recover from this situation. The lazy_static initializer runs inside of a Once::call_once closure, and once that panics, every future call to call_once also panics, and every time you're trying to dereference ROOT_CERTS, your thread will panic.
As I said at the beginning,  ost of these situations (but not all, see the Worker example) could be “handled” by sprinkling catch_unwind all over your code, but I surely hope no one is advertising for that. The typical usecase people apparently have in mind for catch_unwind is task-level isolation. However, as I've hopefully shown here, trying to handle poison errors at that level is basically impossible. Yes, it's certainly no worse than just aborting on OOM as is done now, but it doesn't really get us closer to graceful handling of OOM either.

The reserve API sounds like a great idea. Just the examples of reserving just 1 element seem like an overly conservative use. I imagine this being used with a total upper bound estimate at a beginning of a function (or internally in collections when they double their buffer).

I'm super happy about oom=panic being included! 💯
I create many large vectors from .collect() and I don't see a way to use try_ methods. Maybe try_collect() trait? (but I'm happy to rely on panic in the meantime).

@jethrogb

But what about user's invariants?
[...]
However, as I've hopefully shown here, trying to handle poison errors at that level is basically impossible.

Thanks for this detailed answer! Certainly, if a stack internally uses a lock, it has to gurantee that if push returns without panicking, the element must indeed have been pushed. This will ensure that user invariants hold. The fact that poisoning happened must not be observable. This may not be an easy gurantee to uphold, but it is not made harder by lock poisoning. In doubt, you can always fall back to mutex.lock().unwrap() and "propagate" the failure if you cannot handle it.
Remember, my initial question is about your statement that I read as "poisoning (specifically std::sync::PoisonError) makes using unwinding harder". I still do not understand how that should be the case.
What I do agree with is that locks (no matter whether they have a mechanism such as std::sync::PoisonError or not) make using unwinding for task isolation harder. If a task fails while it holds the lock, that lock is now "infected" by the failure, and if unwrap() is used as suggested above, other tasks accessing the lock will now also fail. This is an inherent problem with shared mutable state; if you want your tasks to be isolated also in terms of failure, you must only share read-only state between them. (As usual, there are exceptions, like transparent caching/memoization or so.) And maybe that is what you wanted to say and I just misunderstood you?
If locks wouldn't have poisoning, the situation would not be any better -- it would indeed be worse! You would implicitly rely on invariants being uphold in the middle of a critical section, and you may not even notice that you are doing this. Lock poisoning makes it so that you have to think about this case, and that can only improve the result.

What I do agree with is that locks (no matter whether they have a mechanism such as std::sync::PoisonError or not) make using unwinding for task isolation harder.

I think this is pretty close to the point I'm trying to make. Indeed the mechanism doesn't really matter. When encountering a poison error I'd say it's probably to late to do anything useful. You need to handle these errors where they come up. So unless you want to combine every use of lock with catch_unwind (which I think is a terrible idea), unwinding for error handling is not a good idea.

@jethrogb
But it's not like using Result instead of panics for all these random failure modes will make failure handling easier.
Through I suppose you could have a way to "turn off" panicking in a lock guard for some operation. Maybe have it take the lock guard by &Self and require it contents to be AssertUnwindSafe?

But it's not like using Result instead of panics for all these random failure modes will make failure handling easier

What do you mean? Rust's ease of doing error handling soundly and accurately through the Result system is one of the key strengths of the language.

Unwinding has always been in Rust explicitly for task-granularity error recovery, and it's not going away. If that doesn't work for your use case, great- use the try_ functions and Result, that's the primary purpose of this RFC.
But if you a) don't use (a lot of) shared state, or b) are okay with even an even coarser granularity of failure (e.g. the set of threads that use a Mutex), then unwinding on OOM is useful. There is no reason to force everyone to use either oom=abort or fallible allocation everywhere.

The lock poisoning is a red herring. It is a difficulty, but it's not a new problem, and it's not even specific to OOM handling. In Rust already every vec[x] can do the same. And Rust already provides multiple ways of dealing with it, from graceful checks on locks to aborting.

Summary so far
Just to summarize the unresolved discussions so far so that it's easier for folks to catch up and participate.
The main concern is "depending on unwinding for Rust error handling is counter to Rust principles". An alternate proposal to oom=panic is to have the ability to register custom oom hooks which yield the strategy to be used.
The rebuttal to that concern is that panics in Rust are for last-resort things you wish to catch at the task boundary, and for many OOMs are just that (see also).
Another point brought up was that the semantics of reserve() on hashmaps are not straightforward. In the current implementation it's always possible to fit an entry if we have capacity; however in a general hashmap implementation this may depend on the actual key to be used. The current RFC only proposes try_reserve, which wouldn't be enough in such a case (for an alternate implementation of HashMap).
Finally, related to the "we shouldn't panic" concern, there was a discussion about panics discouraging mutexes, and some discussion about poisoning.
(let me know if I missed something)

@rfcbot fcp merge

@rfcbot fcp cancel
removing lang team

Thanks, @Gankro, for the epic amount of careful work here! The libs team wants to push this to a full review process:
@rfcbot fcp merge

Wow, that was a record-fast team review (probably due to the extensive prior discussions @Gankro had with all involved stakeholders). Thanks all.
If you're coming into this thread for FCP, have a look at @Manishearth's summary comment, which lays out the major tradeoffs discussed in the thread.

I'm surprised by the proposal to merge. This RFC does nothing to improve the ergonomics of out of memory errors. It just adds some niche features, barely solving a limited set of use cases, and not at all solving the problem in general. I think we should take a step back and evaluate alternatives that people would actually be able to use all the time. This RFC presents those alternatives as "future work" instead, but I think we should shoot for one of those immediately.

This should be an eRFC. More trial and error is needed.

@jethrogb @Ericson2314
The actual proposal in this RFC is tiny: API-wise, it's just adding a method to try a reservation tentatively. That makes it an extremely conservative addition, in the sense that it does not tie us to any particular long-term approach.
@jethrogb, I feel like your comment in particular is, frankly, pretty over the top:

This RFC does nothing to improve the ergonomics of out of memory errors. It just adds some niche features, barely solving a limited set of use cases, and not at all solving the problem in general.

The RFC doesn't claim to fully solve the general problem, but it does give an extensive analysis of a number of use-cases derived from discussion with stakeholders. That is, it most definitely solves a real problem, and does so in a way that is carefully designed to have minimal impact and represent minimal commitment. I struggle to see the downsides of taking this step, even if it doesn't solve the problem you're most interested in. Am I missing something here?
Separately, it seems fine to continue discussion around the more general problem and potential approaches to it elsewhere, with an eye toward an eventual RFC on that basis.

@aturon

@jethrogb, I feel like your comment in particular is, frankly, pretty over the top:

This RFC does nothing to improve the ergonomics of out of memory errors. It just adds some niche features, barely solving a limited set of use cases, and not at all solving the problem in general.

The RFC doesn't claim to fully solve the general problem, but it does give an extensive analysis of a number of use-cases derived from discussion with stakeholders. That is, it most definitely solves a real problem, and does so in a way that is carefully designed to have minimal impact and represent minimal commitment.

Maybe I'm just peeved that my particular use-case is not addressed, resulting in the use of strong language. But your comment is pretty much exactly in line with my statement you quoted: the RFC is designed to solve exactly a limited set of problems, derived from discussions with some stakeholders (not including those in the server space†).

I struggle to see the downsides of taking this step, even if it doesn't solve the problem you're most interested in. Am I missing something here?

We know there the possibility for a better/general solution. A lot of Rust's RFCs see a lot of churn in search for the best possible solution of particular problems. I just think we can do better on this one.

The “1.0” in the name of the RFC suggests that this design is ready for mass consumption. But this is really 0.1. I agree with @Ericson2314 that this should be an eRFC instead. I don't think try_reserve should ever be stabilized, only the abstractions that will be built on top. I also think panicking should be reserved for unrecoverable errors, and I'm convinced there are cases where OOM is not unrecoverable.

† Others and I have tried to address the server use-case several times, but it seems to be either ignored (it appears the RFC author did not research this use-case as well as the others) or downplayed with arguments such as “same as the embedded”, “fool's errand”, “not practical”, and “overcommit”. I'd much rather think in terms of the solutions that Rust might enable than the problems no one has been able to solve in the past. There are environments without overcommit. It is possible to take a holistic view of memory management and do it correctly. This is exactly the kind of low-level control that Rust promises.

@jethrogb
These downsides seem rather thin. It seems fine to s/1.0/0.1/ -- the RFC title isn't really meaningful. And yes, it's true that a lot of RFCs iterate significantly, but this is usually due to difficulty in taking an incremental approach to building the feature. (Though, in fact, a large number of RFCs succeed precisely by cutting scope to a conservative score.)
To reiterate, this RFC takes a maximally-conservative stance on the problem, proposing an API that leaves the door open to a wide variety of more comprehensive solutions down the line. But in the meantime, it makes a small, easy step that will address some existing needs. And it's not like the proposed API is deeply problematic or complex; it's very straightforward.
I really don't understand the call for an eRFC here. We already have an extensive process for review on nightly prior to stabilization. The eRFC process is intended for cases where there is a lot up in the air on the details, and where the only realistic way to resolve the questions is by trying it out. By contrast, the details of this approach are crystal clear, as are their relation to the particular use-cases they're trying to address.
We all aspire to the highest quality in Rust, which is part of what makes it such a great language. But we have to not let the perfect be the enemy of the good -- and when there is a chance to ship something that addresses some real needs with essentially no technical downsides and a tiny API surface -- IMO, we should take that opportunity.

@jethrogb: I'm also interested in the server case and annoyed by Linux-centric assumptions, but I think this RFC goes a long way towards making servers usable.
In thread-per-request servers you will be able to isolate OOM panics now, and for other cases, even where you don't use Vec directly, it opens up a rough hack:
let _ = Vec::new().try_reserve(max_needed_mem_estimate)?;

@aturon

The actual proposal in this RFC is tiny: API-wise, it's just adding a method to try a reservation tentatively.

I am strongly against merging this RFC in its current state. I agree that the try_reserve API is "tiny", but am against because it does not solve the problem that it is supposed to solve and arguably it can even be considered dangerous in its current state.
As specified by the RFC, the success path of a try_reserve call does not guarantee that a subsequent insertion of elements, that does not exceed the collection's capacity, will not fail.
This means that try_reserve cannot be used to avoid OOM panics or abort calls yet IIUC this is the whole purpose of the try_reserve API. I asked: What is the purpose of try_reserve then? This question remains unanswered.
I would be in favor of merging this RFC if we either:

remove the try_reserve API (and move it to another RFC)
fix the try_reserve API (the solution might be as simple as specifying that calling try_reserve  guarantees that the collection will grow up to the capacity allocated by try_reserve without OOM failures; and that collections that cannot guarantee this should not implement it).

FWIW, I think that the problem try_reserve attempts to solve is a problem worth solving, but as specified by the RFC the method is completely useless.

As specified by the RFC, the success path of a try_reserve call does not guarantee that a subsequent insertion of elements, that does not exceed the collection's capacity, will not fail.

Where in the RFC is this specified? I can't find it.
I do recall an open question about HashMap not being able to reliably implement try_reserve depending on implementation strategy. It appears this was never resolved (if grepping this discussion and the RFC text doesn't betray me). This is related and should be addressed in some way before the RFC is merged.

@rkruppe

Where in the RFC is this specified? I can't find it.

That's correct, it is not specified anywhere, which is the problem. try_reserve does not requires insertion up to the capacity to succeed, so users cannot rely on this being the case, which raises the question, why would they call try_reserve instead of reserve in the first place.

Yeah this is just a first step to kick of further experimentation and unblock servo. It doesn't really constitute a clean API, regardless of its size, on its own.

@gnzlbg @rkruppe I just checked in with @Gankro, and all of the collections try_reserve would be added to support a strong guarantee for its behavior (along the lines that @gnzlbg is asking for). Notably missing from the list is BTreeMap, which cannot support such a guarantee.
It is true that, if we wish to always make such a guarantee, we are imposing some restrictions on the possible algorithm used for HashMap.
I'd be happy to update the RFC text to state a more clear-cut guarantee on the success path.

@aturon The RFC does not add try_reserve to BTreeMap so I think adding the guarantee sounds great.
The RFC should explicitly list for which types try_reserve is added, and for which types try_reserve_exact is added (IIRC try_reserve_exact only makes sense for the types that implement reserve_exact).
About HashMap... If by constraining the implementation it is meant that implementations that we will never consider for HashMap won't be able to support try_reserve then it does not really matter. It might matter in other cases, but we will be able to make a more informed decision about this after the implementation. Maybe this should be listed as an unresolved question to resolve before stabilization?

I'd like to see the OomHandler as suggested by @mark-i-m included in this RFC, for two reasons:

It allows for OOM handling without changing any kind of code that didn't yet care about OOM. For web servers this means that you can continue using existing unchanged web frameworks which allocate all over the place and make them OOM-safe by plugging in clever strategies like the one suggested by
@elahn. Note that this plug-in-OOM-safety works for other stuff like game engines or OS kernels as well.
It avoids API symmetry problems and allows for an orthogonal solution to the same problem.

Now, what do I mean by orthogonal solution? OomHandler is more comparable to having a GC. It works behind the scenes and just cares about freeing whichever memory for whichever allocation. Functions like try_reserve on the other hand allow for handling specific allocation issues, like allocating memory for user inputs. Imagine you feed a 4GiB source file into a JSON parser of your fancy web app. Here you are likely to prefer try_reserve OOM handling: The user was propably sending garbage data or trying to DoS your server, so just abort parsing and report an error back. And what if your fancy web app needs to allocate some memory for some internal computations, far away from user inputs? E.g. buffers for DB transactions or whatever, I'm no web dev. In that case you just expect stuff to work, so OomHandler will kick in instead, applying some @elahn magic, while you just call your classic reserve functions.
And what do I mean by API symmetry problems? For me, the big question for this RFC is: "Where do we stop?" Do we keep it low and just provide fallible alternatives for reserve and with_capacity and stuff like that which's sole purpose is to allocate? Or do we provide try_ alternatives to everything that potentially allocates? Box::try_new, Vec::try_push, String::try_from, Rc::try_new, Cow::try_to_mut,...? If we have Vec::try_reserve, then there might later be people asking for Cow::try_to_mut as well, applying that try_-symmetry to every allocating and panicing function in the long run. And while we are at it, why not add try_-alternatives to all the functions that could panic!, no matter whether they panic due to allocation failures or broken invariants?
That might sound like I'm slightly against adding tons of try_-functions everywhere with arbitrary limits where we might stop adding them, but I'm actually fine with that. I just like to see an explicit limit and the inclusion of OomHandler as an additional strategy.

@Evrey I have a similar position. But isn't it a strict superset of this? (Meaning it can be added with backwards compatibility in a 2.0 RFC).

@Evrey

"Where do we stop?" Do we keep it low and just provide fallible alternatives for reserve and with_capacity and stuff like that which's sole purpose is to allocate? Or do we provide try_ alternatives to everything that potentially allocates? Box::try_new, Vec::try_push,

One thing I don't understand is, e.g., on a Vec::push(value), which consumes the value, how does the OomHandler allow me to recover value and continue program execution.

@arthurprs Yes, indeed. I just wanted to make this superset explicit, so that we either maybe propably add that superset to this RFC or to a 2.0 version, instead of later having an RFC for Cow::try_to_mut, an other one for Box::try_new, and yet an other one for whatever else panics, resulting in half a dozen RFCs basically asking for the same thing.
@gnzlbg Well, value won't be consumed before having handled an OOM error. Look at the implementation of Vec::push(value). It is something like this:
impl<T> Vec<T> {
    pub fn push(&mut self, value: T) {
        if self.len() >= self.capacity() {
            self.gimme_moah_capacity();
            // ^-- this is where `OomHandler` kicks in, freeing memory for more allocation
        }
        self.put_one_past_end(value);
        // ^-- this is where `value` is consumed - after `OomHandler` is done applying magic
    }
}

To consume value, your <insert collection type here> has to put it into its unused region of free memory. OOM handling kicks in to get that free region of memory in the first place. Until then value is patiently waiting inside your CPU registers or stack frame. So the OomHandler doesn't have to care about any state to recover at all, as there is no state to be recovered.

Keep in mind that OomHandler should not be a single global handler. It's more like an event that can have any number of listeners, or at least a chain of handlers.
PHP made this mistake a few times with global handlers, and frameworks, libraries and apps ended up fighting for the global shared handlers.

value won't be consumed before having handled an OOM error.

As far as the type system is concerned, the value has been consumed. What @gnzlbg refers to is that try_push should have a signature like fn(&mut self, elem: T) -> Result<(), T>, i.e., in the error case, ownership of the element is moved back to the caller.

@RalfJung indeed, but I was trying to let them explain how OomHandler works in those situations. FWIW, I do not think that it can work since neither @mark-i-m nor @Evrey  nor @pornel has explained how OomHandler solves the following problem:
fn foo(vec: &mut Vec<Foo>) {
  let value: Foo = ...;
  vec.push(value); // fails, value is move
  free_some_memory();

  vec.push(value); // ERROR: use of moved value

  // if fails again:
  allocation_free_log!("cannot insert value {:?} in vector", value);
}

How does OomHandler allow me to write this kind of code ?

@aturon
Even if we can make try_reserve not useless, I think we should not provide it.
Right before 1.0 we took the following decision (which I strongly disagreed with): "if you are using the Rust standard library, OOM errors are irrecoverable".
Users are guaranteed that functions in core do not allocate memory. But every single function in std can potentially change in the future to allocate some memory on the heap; try_reserve adds a second API to a single std function, but this is not an 80% solution like the RFC says, but more like a 0.001% solution.
Users that care about handling OOM currently have two 100% reliable options (AFAIK):

use oom=panic and panic handlers to handle oom exception/try/catch-style
write their whole stack up from lib core with OOM handling in mind

For those that use oom=panic + panic handlers, try_reserve does not solve any new problem. For those that compile with panic=abort, try_reserve does not solve any problem either, because they still have to worry about the other 99.999% of the APIs in std potentially aborting on OOM.
IMO we should just prune try_reserve. If somebody cares enough about handling OOM with the std library while using panic=abort they should write another RFC because that's a huge topic on its own. IMO, those users are just better off not using the std library at all, and Rust has great support for this already using no_std.

@gnzlbg OomHandler doesn't allow you to write this code, try_push does. OomHandler works differently and allows you to write this kind of code:
fn foo(vec: &mut Vec<Foo>) {
    let value: Foo = ...;
    vec.push(value);
    // ^-- Oh noez, `Vec::push` needs to `Alloc::alloc`!
    //     ^-- Oh more noez, `Alloc::alloc` failed, now our chain of `OomHandler`s is called.
    //         ^-- An `OomHandler` succeeds in freeing up enough memory.
    //     ^-- `Alloc::alloc` can now try again to allocate, succeeds, and returns new memory.
    // ^-- `Vec::push` got its new memory without ever knowing what happened.
}

Note that unlike origially suggested, OomHandlers in this call chain only report whether or not they succeeded in freeing up some memory. The second allocation attempt should be done by Alloc::alloc. Why? So that an OomHandler cannot simply return some random pointer to some random memory, possibly static, possibly allocated by a whole other allocator, resulting in a lot of pain when de-allocating stuff.
If a handler within a chain fails, the next one will be used. Whether or not all handlers fail, Alloc::alloc can try allocating memory again. If it fails this second time as well, the error is returned.
Using try_push, your example would look somewhat like this:
if let Err((value, _err)) = vec.try_push(value) {
    free_some_memory();
    // This time, forward the error to the caller.
    vec.try_push(value)?;
}

The nice thing is that try_push might also result in invoking the OomHandler chain, so the whole if let might be redundant. Orthogonal solution 'n' stuff.
But now, considering your second part, addressed at @aturon: What problem do try_reserve and its gazillion friends solve that cannot be solved by OomHandler + panic! on failure? I.e., what's the use case of having this besides adding an other formatting case and more Result return values?
/// Appends some `Foo` to your `vec`.
///
/// This function does not panic, yay! However, in case of an OOM, there is nothing we could do.
/// All OOM handlers failed, so... yeah.
pub fn foo(vec: &mut Vec<Foo>) -> Result<(), (Foo, AllocError)> {
    let value: Foo = ...;
    vec.try_push(value)
}

I'm thinking about things like web servers which don't want to crash but instead block incoming connections until a bunch of requests have finally been handled. And thus I think that try_push 'n' friends are useful additions to use_std applications. (Embedded stuff might need nothing more than a single good OOM handler, and be it an infinite loop to trigger the watchdog reset timer.) This is still an edge use case, however, so this won't justify adding all those functions to the existing types directly. Opting them in via extension traits or a crate infallible_alloc might be more attractive solutions. On the other hand, putting this stuff right into the existing types might help keeping the amount of code low, like this: #[inline] pub fn push(&mut self, val: T) { self.try_push(val).expect("Noez, OOM!") } Reducing code size the other way around requires catch_unwind, which doesn't work on all compilation targets, as some might abort() on panic!. On the plus side: Keeping code size small like this also reduces the amount of code to bug-check.

If you have try_reserve then you can implement try_push yourself (e.g. vec.try_reserve(1)?; vec.push(val)).
iter.collect() can also be made faillible by using vec.try_reserve(expected_size)?; vec.extend(iter).
So try_reserve is a more general solution eliminating need for most other try_* functions on Vec.

For those that can use oom=panic + panic handlers, try_reserve does not solve any problem.

It does — improves performance (since fewer threads and catch_unwinds are needed) and increases chance of having more graceful error handling. Panic is still necessary to handle all errors (in unexpected places/3rd party code), but try_reserve still improves situation for your own code and obvious offenders.

@Evrey Thanks, that explanation did make the purpose of OomHandler click.

What problem do try_reserve and its gazillion friends solve that cannot be solved by

Just to clarify I wasn't saying that these methods solve no purpose at all, but rather that:

try_reserve alone is not enough, and that
providing a try_ version of all possibly-allocating std library functions is also not enough.

For this approach to be enough:

all the libraries in the ecosystem would need to use the try_ methods and expose try_ alternatives of their APIs, and
users would need to inspect every library they use to make sure it does not use a non-try_ method anywhere.

To prevent everybody from having to deal with OOM errors, the std library took the design decision of making OOM irrecoverable. By bolting this on we get the worst of all worlds: two different imperfect and confusing ways of handling OOM:

the oom=panic which basically makes panics an error-handling mechanism for OOM errors that do not allow recovering consumed values on OOM
the try_ method which duplicates API surface and would need some sort of static analysis to become useful (e.g. to not forget calling try_push instead of push in some library).

If we wanted to go the "try_ everything way" we should rewrite the std library API to use Rust's error handling mechanisms (that is, Result) for OOM, which would make adding oom=panic unnecessary which is a good thing: oom=panic makes panic an error handling mechanism and that is not what panics are designed for.
Needless to say, going down this try_-everything route would be a spectacularly huge breaking change. So here we are.
I think that oom=panic makes the most sense for Rust as it currently is. The try_...-approach leads to a different ecosystem that, if desired by some particular community, can be built on top of core.

@pornel

If you have try_reserve then you can implement try_push yourself (e.g. vec.try_reserve(1)?; vec.push(val)).

The problem is not push, or reserve, but the other 99.9999% of the functions in the standard library. Here is a trivial example:
vec.try_reserve(1)?;
vec.push(a);  // never fails: guaranteed by vec docs
vec.get(0)  // OOM?

Nowhere in the standard library documentation says that get has complexity O(1) and that get does not allocate any memory. That is, changing the implementation of get to allocate some memory is a backward compatible change to the current standard library implementation. Doing so would make no sense, but that is not the point. The point is: 99.999% of the functions in the standard library do not specify whether they allocate memory or not. If you are in the small niche group of users that must handle OOM errors, this is a nightmare, because every single call to every single library function in the whole Rust ecosystem can allocate some memory or be changed to do so and you have no way to tell, and in 99% of the cases you don't have a try_ API either.
This is what I mean with "just adding try_reserve to the standard library and calling it a day is not enough", and this is why making try_reserve useful is a huge amount of work (not only in the standard library but also in the Rust ecosystem).

Note that with oom=panic + a panic handler you get 100% reliable OOM error handling module double panics.

@gnzlbg I'm not sure what you're advocating for. Just having oom=panic and no try_reserve at all?
I agree with you that it's infeasible to check for allocations in all std functions, and that's why I strongly argued in favor of oom=panic.
However, I don't see downsides to having both try_reserve and oom=panic. As I've mentioned previously, one is useful for performance and less dramatic error handling in easy cases, and the other is necessary to cover remaining cases.

However, I don't see downsides to having both try_reserve and oom=panic. As I've mentioned previously, one is useful for performance and less dramatic error handling in easy cases, and the other is necessary to cover remaining cases.

The main downsides I see are that:

try_reserve introduces monadic error handling for OOM in the std library which is something the std library was explicitly designed against. This is not that bad, because panics were designed not to be an error handling mechanism yet this is what oom=panic makes them.
try_reserve's purpose is to allow handling OOM errors when compiling with panic=abort. It is a step in that direction, but it is a very tiny step, and to me at least it is unclear whether this direction is the correct one.

I'm not sure what you're advocating for.

I am advocating for moving try_reserve to its own RFC about handling OOM errors when panic=abort. This RFC should at least provide a path forward, e.g., what would entail to go the try_reserve-way (both workwise, API-wise, complexity-wise, etc.).

@gnzlbg @pornel You are misunderstanding the scope of this RFC.

Users are guaranteed that functions in core do not allocate memory. But every single function in std can potentially change in the future to allocate some memory on the heap (the std library does not guarantee what it does not guarantee); try_reserve adds a second API to a single std function, but this is not an 80% solution like the RFC says, but more like a 0.001% solution.

False. try_reserve adds a second API to a single liballoc function, which is completely different. As an example, for all I know libstd is an implementation detail of rustc, I do not use it any of my current projects.

Embedded stuff might need nothing more than a single good OOM handler, and be it an infinite loop to trigger the watchdog reset timer.

False. Embedded use cases are a core motivation for this RFC. In firmware you would typically guard every single heap allocation (so #[deny(infallible_alloc)]) and have a meaningful error path (aborting the request, or even something more complex such as dropping caches). This is stricter than servers, where you are taking some things for granted; per-process setup code does not need to handle OOM gracefully.

@whitequark

False. try_reserve adds a second API to a single liballoc function, which is completely different. As an example, for all I know libstd is an implementation detail of rustc, I do not use it any of my current projects.

Can you be more specific about what exactly is false?

@gnzlbg That this isn't a 80% solution (to something). It is indeed not a 80% solution to libstd missing fallible allocation functions (libstd will never have them), but it is a 80% solution to liballoc missing fallible allocation functions (and a 100% solution here is not far away, IIUC).

Oh, a good example of how this RFC provides a benefit for servers too: you can embed non-libstd-using programs in libstd-using-programs. E.g. a resource-intensive but IO-free computational core that has all allocations fallible, wrapped in resource-light interface to the OS.

Nowhere in the standard library documentation says that get has complexity O(1) and that get does not allocate any memory. That is, changing the implementation of get to allocate some memory is a backward compatible change to the current standard library implementation. Doing so would make no sense, but that is not the point.

Assuming that the authors of every library you use are actively malicious does not seem like a fun way to develop software.

@whitequark

but it is a 80% solution to liballoc missing fallible allocation functions (and a 100% solution here is not far away, IIUC).

What about Box, Rc, Arc, what about even Vec::append ? These are all part of liballoc. Do we know how many functions in liballoc do allocate memory?
This RFC says that try_reserve-like APIs is how panic=abort users  should handle OOM errors in their Rust programs, it adds 4x try_reserve functions (HashMap, Vec, String, and VecDeque) to liballoc which is shipped with std, and concludes with:

Completing the no-unwinding story is left for future work.

Sorry that I am not convinced that this is how panic=abort users should handle OOM errors, but this RFC has little to zero exploration of the design space, the APIs that would need to be provided, etc.

@sfackler

Assuming that the authors of every library you use are actively malicious does not seem like a fun way to develop software.

This is why I use Rust. In most of the cases I care the Rust compiler verifies things for me so that I don't have to.
And you don't need to be malicious to insert a memory allocation in a program:
    println!("DEBUG REMOVE THIS: {:?}", value); // landed on master by mistake

println! doesn't allocate memory. Accidental additions to a method seem totally unrelated to what guarantees they document, anyway.
[T]::get is defined in libcore which doesn't have access to allocation.
[T]::get's documentation doesn't guarantee that it doesn't spend a millisecond mining Bitcoin every time it's called. Are you equally concerned about that?

println! doesn't allocate memory.

println! needs to format that string, which can be arbitrarily long, depending on what Debug for that particular type does.

Are you equally concerned about that?

If I want to handle all OOM errors in a panic=unwind program I am concerned that I cannot tell the functions that can abort the program on OOM from those that cannot without manually inspecting all the code.

What about Box, Rc, Arc, what about even Vec::append ? These are all part of liballoc.

I thought it was clear that Vec::try_reserve in this RFC is a "proving ground" for this concept. In the end, every function in liballoc that can transitively allocate should have such a variant.
@Gankro Could you make this more clear in the text? Also, I'm starting to conclude that calling this 1.0 is a bit early (although this does not affect my opinion on actual adoption or anything)

Do we know how many functions in liballoc do allocate memory?

We'll need the infallible_alloc lint anyway for this API to be ergonomic, so that'll handle liballoc for us too.

println! needs to format that string, which can be arbitrarily long, depending on what Debug for that particular type does.

It does need to format the string, but there's no intermediary String involved. It is line buffered and otherwise streamed directly out.

@sfackler I think the idea is this:
struct X;
impl fmt::Debug for X {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        Vec::new(); Ok(())
    }
}

@whitequark

This is not an argument against this RFC.

It was only an argument against the usefulness of try_reserve. It is supposed to solve the fallible allocation problem for panic=abort users, but it doesn't. The only way to do that using a try_reserve-like methodology would be to reimplement a different Rust ecosystem that treats OOM as first-class errors, and to use that ecosystem instead.
Is this how we want panic=abort users to handle OOM ?

try_ everything in the standard library and the whole Rust ecosystem?

That's my concern as well. It doest scale, not at all. Although that's how people do it in C, checking for malloc results all over the place :woman_shrugging:

It is supposed to solve 80% of the fallible allocation problem for panic=abort users, but it doesn't.

As someone working on a project in that space; I think you misunderstand what at least some of us need.
Not everyone needs complete infallibility. You're making it out so that the panic=abort users are in an "infallible or bust" situation, which isn't true. It might be true for some of them, but not all of them.
At least for Firefox we don't want every allocation to be infallible; we don't do that in the C++ code either. We need the ability to make specific allocations infallible because we know which are the contentious ones. In general the user running out of memory due to an arbitrary allocation is not a problem we can reasonably handle; but if there are some large/common allocations we can add graceful shutdown or other handling mechanisms to those specifically.

@Manishearth
That makes sense. I've never considered the "some degree of infallability" situation because I am in a different space.
The only thing I've often needed to handle are all OOMs within a certain region of my program (e.g. initialization):
{  // CRITICAL: handle all OOM in this scope:
  image_buffer.try_reserve(length)?;
  load(&mut image_buffer);
  process(&mut image_buffer);
  write(&image_buffer);
}

try_reserve isn't enough for me because load/process/write can all potentially allocate and fail. The way I've solved this till now is by "being careful" and owning all the code that gets called, but this is extremely brittle (once I left some debug code that allocated inside one of the functions by mistake). I would need to either have a way to ensure that load/process/write do not allocate any memory, or that they do so in an infallible way propagating errors.

try_ everything in the standard library and the whole Rust ecosystem?

That's my concern as well. It doest scale, not at all.
Although that's how people do it in C{++}, checking for malloc/new results all over the place and propagating that

Except Rust makes it easy, just put a couple ? in and you're mostly done.

@jethrogb I think the "doesn't scale" concern is that you need try_-named variants of every API that allocates (or could potentially allocate in the future).
Right now whether an API allocates or not is often an implementation detail but the try_-everything approach requires this information to be very visibile (probably up to the point that the compiler should prevent you from calling functions that infallibly allocate in certain parts of your code).

@gnzlbg What you're saying is internally inconsistent. It is exactly when you start caring about allocations failing that they stop being an implementation detail! In more academically-minded languages these go into function signatures as effects, though I don't think anyone is trying to pull that off in Rust.

It is exactly when you start caring about allocations failing that they stop being an implementation detail!

If this isn't what I said it is what I meant, I think we both agree here.

In more academically-minded languages these go into function signatures as effects, though I don't think anyone is trying to pull that off in Rust.

The RFC does mention effect-system as an alternative design decision at the end, and Rust used to have one.

Note that even if Rust had an effect system, adding allocations where there were none would be a breaking API change, so the concern of visibility is unfounded.

Since fallible allocations are observable, adding allocations where there were none are an API breaking change even iff Rust does not have an effect system. Having an effect system (that can handle this kind of effects) would make this API breaking change a type error.

Having an effect system (that can handle this kind of effects) would make this API breaking change a type error.

Can't you get the same outcome today by changing the result type?

@whitequark what do you mean?

Can't you get the same outcome today by changing the result type, and without splitting the function?

Sure, but since we cannot break backwards compatibility for std APIs, this isn't really an option there.

The existing APIs could remain (and panic on OOM): the new apis would have the new signature where OOMs can be indicated.

One think missing:
a simple way to detect if a panic was because of oom
If oom always throws the same non-string struct as a panic we could use downcast
to check it, if it's a string we could use downcast+string compare.
Generally it might be the best to provide a function like std::panic::is_oom_panic_error(Box<Any+Send>)
and optimally another one like std::thread::oom_panicking()

Details:
is_oom_panic_error basally knows about the error format and uses downcast (+compare if necessary, e.g. on String errors) to check if it's a error like the ones thrown by oom().
oom_panicking is like panicking  + a check if it is cause by oom.  The implementation would require to either add a bit flag to the panic  count and with this slightly change the signature of update_panic_count etc. Or add another thread local (or get access to the payload, which is tricky).
The motivation behind this is that you often want to be very clear about wether or not it failed because of oom or some other reason which might be e.g. a Bug causing a out of bound check or similar. E.g. when parsing a big file a oom panic could lead to telling the user that this wont do with the given amount of memory, while a different panic is most likely a bug and should lead to a different kind of user feedback.

wrt. OOMHandler:
some form of OOMHandler doesn't sound so bad for the use-case where you e.g. have some big caches you can clear up at (nearly) any point, folled by then e.g. retrying the allocation. But it doesn't cover the
"I try to allocate something big hope there is space"  case. I think instead of replacing this proposal a OOMHandler might be worth as an additional feature being called inside the allocators alloc functions. (So that the allocator can directly retry after freeing resources).
=> conclusion: you can implement it with a custom allocator which wrapps another allocator

One think missing:
a simple way to detect if a panic was because of oom
If oom always throws the same non-string struct as a panic we could use downcast
to check it, if it's a string we could use downcast+string compare.
Generally it might be the best to provide a function like std::panic::is_oom_panic_error(Box<Any+Send>)
and optimally another one like std::thread::oom_panicking()

Details:
is_oom_panic_error basally knows about the error format and uses downcast (+compare if necessary, e.g. on String errors) to check if it's a error like the ones thrown by oom().
oom_panicking is like panicking  + a check if it is cause by oom.  The implementation would require to either add a bit flag to the panic  count and with this slightly change the signature of update_panic_count etc. Or add another thread local (or get access to the payload, which is tricky).
The motivation behind this is that you often want to be very clear about wether or not it failed because of oom or some other reason which might be e.g. a Bug causing a out of bound check or similar. E.g. when parsing a big file a oom panic could lead to telling the user that this wont do with the given amount of memory, while a different panic is most likely a bug and should lead to a different kind of user feedback.

wrt. OOMHandler:
some form of OOMHandler doesn't sound so bad for the use-case where you e.g. have some big caches you can clear up at (nearly) any point, folled by then e.g. retrying the allocation. But it doesn't cover the
"I try to allocate something big hope there is space"  case. I think instead of replacing this proposal a OOMHandler might be worth as an additional feature being called inside the allocators alloc functions. (So that the allocator can directly retry after freeing resources).
=> conclusion: you can implement it with a custom allocator which wrapps another allocator

I've missed rather a lot of conversation, but the intent behind OomHandler (when I proposed) it was to make error handling transparent to applications. If an allocation fails, try to do some stuff to make some room (e.g. GC) and if the allocation can succeed now that is great. Otherwise, there is nothing good to do, so just panic.
The goodness of such as a design hinges on the last part. So my question would be what should a system do if it cannot allocate memory even after trying to make more room? Is panicking good enough for most situations? What else could you do?

What else could you do?

For a network daemon? drop a single incoming request
For a different network daemon? finish work on a current request before proceeding with current one
Drop some in-memory cache
Run an in-app GC
Serialise some state to disk and free it from memory
For a sensor: reduce sampling rate

Some of the above cannot be done in a handler/callback: they may require returning to the main loop of the application.
Even if panicing is good enough for most situations, it's not reasonable for all. IMO whatever rust picks here should be generic.

@daurnimator  Thanks :)

Some of the above cannot be done in a handler/callback: they may require returning to the main loop of the application.

Even if panicing is good enough for most situations, it's not reasonable for all. IMO whatever rust picks here should be generic.

It seems like most of the things you listed could be implemented with a handler, though. What is the objection to making handler be the default and adding another (perhaps less general) path for cases that need it? That other path can be tailored to those specific needs; it doesn't need to be as general, so it avoids try_*. To me it seems like that approach would have the benefits of (a) not requiring try_* and not requiring code changes in most cases.

Today I finally girded myself to wade back into this thread :-)
To be honest, I think the key problem with this RFC is it's title. Failable allocation as a general topic has a huge set of stakeholders with divergent needs, and this RFC makes very clear that it is not trying to solve the general problem -- but its title perhaps suggests otherwise.
The fact of the matter is that try_reserve solves some problems for some people. This is indisputable, and should not be litigated further on this thread.
However, I think part of the frustration on the thread is that others feel they can see their way to a fully general solution that obviates the need for try_reserve, and serves a larger set of use-cases.
This is a classic situation in the Rust world. The danger, though, is that by always looking to the "more perfect" solution we never ship.
The classic way we handle this in Rust is by considering "forward compatibility". In this case: to what extent does try_reserve preclude "more perfect" solutions in the future? And the answer is clearly "it does not". At worst, we may eventually want to deprecate it in favor of something better.
Now, another concern is that try_reserve is the tip of the iceberg, and soon we will have try_XXX functions cropping up all over std. I agree that this would be an unfortunate outcome, but that goes back to the goals of this RFC. If you see the proposal here as specifically handling a sort of "best effort" situation for particular applications, we really only need this for a couple of core data structures (as proposed). @Gankro took great pains to limit the amount of API bloat needed.
By all means, let's discuss a more perfect solution-- on a separate RFC proposing it in detail. But in the meantime, let's ship a useful iteration that is forward-compatible, with the shared understanding that it's an imperfect approach that we don't want to apply universally across std.

@aturon

By all means, let's discuss a more perfect solution-- on a separate RFC proposing it in detail. But in the meantime, let's ship a useful iteration that is forward-compatible, with the shared understanding that it's an imperfect approach that we don't want to apply universally across std.

We agreed before that for try_push to be useful it would need to correctly report error on OOM and for try_reserve to be useful it would need to guarantee that subsequent calls to push that do not increase the capacity cannot fail.  You wrote:

all of the collections try_reserve would be added to support a strong guarantee for its behavior

But this is not true. Vec has no control over this at all: only Vecs allocator has a say on whether this can or can't work.
In my opinion, the best platform-agnostic guarantees that we can provide for Vec::try_{push,reserve} is something like this:

try_reserve: iff Vec's allocator commits memory on allocation then a successful try_reserve guarantees that subsequent calls to push that do not increase the Vec's capacity cannot fail; otherwise, the behavior of try_reserve is undefined.

try_push: iff Vec's allocator commits memory on allocation then try_push returns error if the allocation fails; otherwise, the behavior of try_push is undefined.

In particular, given that Vec cannot query whether its allocator overcommits memory or not (this is a problem that we might be able to fix though), these functions might need to be unsafe.
Also, revisiting the systems in which the System allocator guarantees that these functions work I can only find one answer: Windows. On Linux, MacOSX, and *BSD, they will generally not work unless the user changes the systems default settings to disable overcommit (terrible idea) or uses a Linux/*BSD distro tailored for being used with overcommit disabled.
On embedded and Linux/MacOSX/*BSDs the user can provide allocators that go both ways. As @whitequark correctly points out, in embedded it makes little sense in general for users to provide allocators that overcommit, but it is still something that can be done.
I've repeated many times that we should split try_xxx into its own RFC so that we can make progress on it without delaying progress on oom_panic, but since it seems that it is "all or nothing", in my opinion the quickest ways to stabilize this are:

make the Vec::try_xxx methods unsafe (we can always remove the unsafe keyword later on in a backwards compatible way)

expose them safely only behind a feature flag in the standard library that is enabled by default on windows and disabled otherwise (this allows users using xargo on embedded to enable these as well).

make them safe, but add an unstable method to the Allocator trait that returns true if the allocator overcommits and make the Vec::try_xxx methods unconditionally panic if this method returns true. We could set this method to return true by default and then on Windows we make it return false (and embedded users  to true by default). On embedded, those writing Allocators can specify whether their allocator overcommits or not.

I don't know. Hopefully others have better ideas but 3 doesn't look that bad to me. In particular because we could extend 3 in the future with const trait methods or use an associated const with associated const defaults and turn the run-time panic! into something better.

otherwise, the behavior of try_reserve is undefined.

This seems extreme. Adding UB to this case would not be helpful for the use cases mentioned in the original RFC. Firefox, for example, is okay with not being notified of OOMs that were delayed by overcommit, but wants to catch as many OOMs as possible.
Like, 32 bit systems exist, and even with overcommit there can be OOM-on-allocation on those pretty easily.
Hobbling an API completely just because it isn't perfect for some platforms in seems extreme to me.
Rather, it makes more sense to define it as "try_reserve is defined to reserve X memory. If the OS commits memory on allocation, try_reserve is guaranteed to produce an error when it is unable to allocate the memory. If not, it is guaranteed to produce an error in case the allocation operation somehow failed, but may succeed when there isn't actually enough memory to satisfy it"

@Manishearth makes sense, what about:

try_reserve: iff Vec's allocator commits memory on allocation then a successful try_reserve guarantees that subsequent calls to push that do not increase the Vec's capacity cannot fail. Otherwise, try_reserve might still fail, but it also might succeed. If it succeeds subsequent calls to push and try_push are not guaranteed to succeed.

Do you know how to remove the undefined behavior for try_push ? I think we actually should add it to push as well.  Without this, the API still pretty broken, because the only reason to call try_reserve is to insert something in the Vec afterwards :/

(We discussed this in IRC, @gnzlbg was misusing "undefined behavior")
Reasoning about the OOM killer is out of scope for Rust's safety model ; the OOM killer can kill a Rust program even when the Rust program wasn't allocating.
One could call this "implementation-defined behavior" but it's not even that; the OOM killer is out of scope for Rust, as is the robustness of Rust programs in presence of an attached debugger mutating the process, or /proc/self/mem, or kill -9.

@gnzlbg Quick clarification: the RFC does not propose to add try_push to std, it only notes that you can define it externally.
The specification you and @Manishearth are hashing out seems just fine to me; this entire enterprise is about a "best effort" API anyway.

@aturon I totally agree with the principle, except the "more perfect solution"'s difficulty is vastly overestimated. As soon as someone fixes the windows errors in https://github.com/rust-lang/rust/pull/47043 I am confident I can make most collections allocator- and fallibility- polymorphic in 2 weeks, tops, seeing that I already did a couple in two days.
At the very least, try_reserve should be deprecated as soon as a better solution is available. Its the equivalent of if and unwrap vs pattern matching for allocation: unergonomic and unreasonably difficult to write correct code with, yet easy to understand and so unreasonably attractive. So yes, don't let the perfect be the enemy of the good, but also keep in mind the inferior APIs by their mere existence can harm pedagogy and ergonomics.

This RFC has been merged; the tracking issue is here. See the summary here.

I was looking into changing some libraries to be oom=panic compatible and I expect it will be very error-prone to do.
Already a lot of people think that catching allocation errors in C++ and trying to recover is too error-prone and a security disaster, and that's with the language always supporting that kind of recovery.
In the case of Rust libraries and programs, they have been written with their security analysis assuming oom=abort. Thus, either an allocation succeeds or it's game over, so it's currently valid to create an inconsistent state in a program (e.g. have a memory-safety invariant left unsatisfied), do an allocation, and then restore the state (e.g. restore the memory-safety invariant) after the allocation. Any such code will be broken and (e.g. memory-unsafe) with oom=panic. Thus one can't assume any crate or any chunk of copy-pasta code is compatible with oom=panic without doing an analysis similar to analyzing unsafe { } code.
In other words, the oom=panic aspect of this will make some currently safe Rust code unsafe. I believe for this reason at a minimum that crates would have to indicate that they actually intend to be compatible with oom=panic and if a crate hasn't explicitly indicated that it supports oom=panic then it should be assumed that the entire crate is unsafe when the configuration is oom=panic. A crate could specify this with something like unsafe-oom-panic-compatible = true in its Cargo.toml; I suggest using unsafe in the name because this assertion is an unchecked claim regarding memory safety.

@briansmith I think I basically think I agree in thinking that as we get more try_ methods (or equivalent) the uses-cases for oom=panic will fast go away. I even expect unwinding to go away too as we get more tools to audit panics and thus ensure recovery paths exist by other means.

In other words, the oom=panic aspect of this will make some currently safe Rust code unsafe.

To make sure that I understand correctly, you mean that this will make existing sound unsafe code (i.e. code inside an unsafe block) unsound, right? If I have a crate consisting of entirely safe code (including expanded macros), then oom=panic could lead to logic errors (my code doesn't restore some logical invariant due to a panic from an allocation). However, I don't believe that it can lead to unsoundness, as injecting a panic (which is safe) into arbitrary purely-safe code can't lead to unsoundness.

To make sure that I understand correctly, you mean that this will make existing sound unsafe code (i.e. code inside an unsafe block) unsound, right? If I have a crate consisting of entirely safe code (including expanded macros),

Very few crates meet that criteria. For example, most use libstd and libstd has a lot of unsafe code within it. Is libstd itself memory-safe with oom=panic?

then oom=panic could lead to logic errors (my code doesn't restore some logical invariant due to a panic from an allocation). However, I don't believe that it can lead to unsoundness, as injecting a panic (which is safe) into arbitrary purely-safe code can't lead to unsoundness.

struct S<T> {
    ptr: *mut T,
}

impl<T> S<T> {
    fn foo(&mut self) {
        let saved = self.ptr;
        self.ptr = 12345678 as *mut _; // Invalidate invariant
        let _ = vec![0u8; 1_000_000];
        self.ptr = saved; // Restore invariant
    }
}

[Pretend there are 10,000 lines of code here]
impl<T> S<T> where T: Copy {
    fn bar(&self) -> T {
        unsafe { *self.ptr }
    }
}

The above code is safe for oom=abort, but unsafe for oom=panic. Note that there is no unsafe block in the block of code directly affected by oom=panic; the unsafe code that is affected is far, far away. This makes it very difficult to find all the places that are potentially affected.
At a minimum, we should audit libstd to make sure there are no such patterns within it. I think that will be a difficult project.

I agree that finding these kinds of issues is going to be very difficult. I just wanted to clarify that any memory safety issue will ultimately have to involve unsafe code in se way, just like with any other form of undefined behavior.

Once again the lack of "unsafe to touch" fields bites us.

I agree that finding these kinds of issues is going to be very difficult. I just wanted to clarify that any memory safety issue will ultimately have to involve unsafe code in se way, just like with any other form of undefined behavior.

That is true for memory safety, but it isn't true for all security invariants.
Consider an application that accepts requests with nonces. It appends each nonce it sees into a HashSet so that it never accepts the same nonce twice. Further, assume that it already uses catch_unwind to "gracefully" handle panics. With oom=abort, this would be safe until the application runs out of memory and dies. with oom=panic, any attempt to append to the HashSet becomes lossy, and the application will silently continue on without (perfectly) enforcing its unique nonce enforcement security guarantee.
This makes me think that the kind of panic that OOM would issue must be distinct from the kinds of panics that catch_unwind would catch:

catch_unwind would ignore OOM panics
A new unsafe fn catch_unwind_oom<R>(impl Fn() -> R + UnwindSafe, R) -> Result<R> would need to be used to catch OOM (and only OOM?).
Library crates should have to opt in to supporting oom=panic, e.g. unsafe-oom-panic=true in Cargo.toml. (This is an unverifiable assertion, thus why I suggest using "unsafe" in the name.) The build system should help enforce that only crates claiming to be oom=panic-safe should be used.
libstd shouldn't be considered oom=panic safe unless/until it is somehow verified.

@briansmith I think I basically think I agree in thinking that as we get more try_ methods (or equivalent) the uses-cases for oom=panic will fast go away. I even expect unwinding to go away too as we get more tools to audit panics and thus ensure recovery paths exist by other means.

I disagree, because I think the ecosystem shouldn't switch to using the try_ allocation mechanisms in general. The problem I am trying to solve is "How do I use Rust libraries that do memory allocation into a C application that doesn't want oom=abort semantics?" I don't think the right answer to that is "Rewrite all the crates to use only fallible memory allocation" as that creates a huge hinderance to all users to accommodate a small minority need. oom=panic looks attractive as a way to accommodate them if the safety issues can be addressed, as one would put catch_unwind/catch_unwind_oom at every FFI boundary and throw away the Rust library state (and potentially build new Rust library state) on OOM panics.

This makes me think that the kind of panic that OOM would issue must be distinct from the kinds of panics that catch_unwind would catch:

With oom=panic, some operations (in this case allocations) which used to be infallible can now panic.
Code may exist which relies on such operations to be infallible to maintain some program invariants.
Such invariants may be safety invariants, security invariants, or really anything.

In other words, there's nothing "special" about OOM panics, other than the fact that OOM didn't used to be a panic. For that reason, I don't think they should be a different kind of panic, since it would make a historical accident into a permanent distinction.
One could easily imagine that in the future there might be other operations that we'd want to make fallible, and that would have the same implications for program invariants, but we wouldn't want to keep introducing new kinds of panics.

I also think, that since oom=panic is an application-level decision, that an initial solution doesn't need to be perfectly automated - it would not be unreaonable to initially expect application authors to do some vetting of their dependencies before using such an option in a security critical context, and the "oom=panic" option could have some barriers/warnings to ensure that users are aware of this.
There is a huge space to explore here, but a new field in Cargo.toml that declares a crate "oom=panic" safe, and a badge on crates.io could be useful.

One could easily imagine that in the future there might be other operations that we'd want to make fallible, and that would have the same implications for program invariants, but we wouldn't want to keep introducing new kinds of panics.

I don't think the expectation is that Rust developers must guard against any standard library function being able to panic, now or in the future. In any case, people don't program that way. Actually, because we have "Panic" sections in documentation of the standard library, I think one may assume that outside the circumstances already described by the "Panic" section documentation, a standard library function won't panic. So I don't think it is reasonable to make existing APIs panic when they didn't before, unless a crate has opted into that breaking change.

unless a crate has opted into that breaking change.

By using oom=panic, an application crate has opted into that breaking change. For a library crate, if it doesn't declare that it supports oom=panic, then there's no expectation that it should work in such a configuration.

@briansmith

I disagree, because...

In the narrow case where C calls out to Rust in just a few place sure. But for more invasive "rewrite it in Rust" scenarios, that breaks down. Same for certain freestanding/embedded projects, e.g. for the Rust in the Linux kernel, catching panics would never have been accepted by upstream. I am not saying we all need to go rewrite the world with try_ right now. I am just predicting that will be the trend in the long-long term for important libraries, so we only need stop-gap solutions in the meantime.
This isn't supposed to be a doom prediction, but rather if the process goes slowly enough the cost will be amortized and not hurt :)

I am not saying we all need to go rewrite the world with try_ right now. I am just predicting that will be the trend in the long-long term for important libraries, so we only need stop-gap solutions in the meantime.

The reason I became interested in this issue is because there was a request to do exactly that for Rustls to get it to work according to Apache Web Server's coding rules, and I'm trying to find a solution that doesn't involve adding a giant number of new (untested) branches to Rustls. I did sketch what this would look like in the Rustls codebase and it got ugly really quickly so I'm trying to find alternatives.

I did sketch what this would look like in the Rustls codebase and it got ugly really quickly so I'm trying to find alternatives.

Did the issues stem from the fact that many functions would have to return a Result? Or was it more to do with the use of indirect allocations that you couldn't easily convert to a try_... form?
One possibility to address the former would be to translate reserve() into try_reserve().custom_unwrap() (where custom_unwrap panics with some custom panic payload indicating OOM) effectively giving you a crate-local oom=panic.

I did sketch what this would look like in the Rustls codebase and it got ugly really quickly so I'm trying to find alternatives.

How having a new error make your code a mess ? snafu or thiserror make it easy to handle error. Can you expand what problem do you encounter ?

How having a new error make your code a mess?

Every time we'd do an allocation, we have to branch on whether the allocation succeeds or fails. Usually this using ?. This becomes a problem in the many cases where the function previously didn't fail, as now we have to bubble up Results everywhere there wasn't one before. Further, either we have to resign ourselves to not testing most of these new branches (i.e. have low confidence in the correctness in the result) and assume everything is OK, or we have to implement fuzzing with an allocator that randomly fails and ensure it hits all these new branches. Experience with C shows that untested error paths are some of the most dangerous in terms of latent security issues, so having the new branches be untested seems irresponsible. Further, all of these branches make it much harder to reason abstractly about the correctness of the code. (One of the things I've been working towards in Rustls is eliminating as much branching as I can by using functional patterns.)

I don't have good solution for your case, since allocator is a global state is very hard to control, I don't think it's impossible but very hard and would require a lot of work. Even with fuse you can't test every possibility, that not because you test a branch that you test every possibility to go thought this branch.
I suggest on rustls case that anything that trigger a oom make an irrecoverable error state into the connection and make it impossible to use it again. Cause let's say you are a server that doesn't want to abort on oom, you have a client that somehow trigger an oom you want to kick this client. So any oom error from a connection you want to stop it. By having a "State Broken abort the ship" that the server will receive trying to use rustls this would prevent any inconsistency state and allow to not abort on oom.

eliminating as much branching as I can by using functional patterns.

I don't see how functional patterns remove any branch, functional pattern remove side effect not branch.

Experience with C shows that untested error paths are some of the most dangerous in terms of latent security issues

True but it's Rust here. It's not a 1 to 1 equivalent, Rust have must better tool to prevent bug.
But I think here we are a little off topic about this feature, your warning about oom=panic is valid but I think you are a little off topic about the rest.

@briansmith I get the pain of refactoring libs, but I don't understand that reason at all. Whether implemented as ? or panicked unwinding, the error control flow path still exists! And either way, it's untested without allocation failure fuzzing!
Now I understand the following is a matter of opinion, but I would much prefer explicit control flow to panicked control flow to audit. As we all know, Rust does error handling this much better than C, by virtue of having sum types, ? and must_use. This makes result-based error handling as "regular" as unwinding. Furthermore, being explicit, the type checker is there to help. Little tooling exists for complicated matters of "exception safety", whereas results or a lack there of have to be tracked conclusively, the type system won't let otherwise.

Brian seems to want all alloc failures to only abort, if I read their meaning properly. Which is certainly one way to maintain security, but maybe a poor user experience.

OK aborting is simpler, yes.

authors: Aaron1011 Diggsey Ericson2314 Evrey Gankra Gankro Lokathor Manishearth RalfJung Stargateur arielb1 arthurprs aturon briansmith dathinab daurnimator elahn gnzlbg jethrogb mark-i-m pnkfelix pornel rkruppe rpjohnst sfackler whitequark


text:
Redirect VC++ Build Tools link to landing page

We (finally!) have a landing page for the VC++ Build Tools. I'd like to redirect the link on downloads.html from my blog post to the landing page. Also, I'd like to remove the direct download link because it's 1) easy to find on the landing page and 2) can go stale as we update the Build Tools. Note that the next option--install Visual Studio Community--has no direct download link, so removing this adds consistency.

Thanks for the pull request, and welcome! The Rust team is excited to review your changes, and you should hear from @nikomatsakis (or someone else) soon.
If any changes to this PR are deemed necessary, please add them as extra commits. This ensures that the reviewer can see what has changed since they last reviewed the code. Due to the way GitHub handles out-of-date commits, this should also make it reasonably obvious what issues have or haven't been addressed. Large or tricky changes may require several passes of review and changes.
Please see the contribution instructions for more information.

Yay!

source: gharchive/pull-request

authors: AndrewPardoe alexcrichton rust-highfive

repo: rust-lang/rust-www

license_type: permissive

license_source: github-api


text:
rust fmt fails to format specific files.

https://user-images.githubusercontent.com/64436119/217716036-f3b2366f-80ad-4e5f-b7ee-1b98e697c31f.mp4
here is the repo:
https://github.com/dogunbound/PACRB
make sure you are on commit as this a rapidly changing repository: 0c5c7ec8717a930b5c0e021bedd0898f023d3f26
the problem files are src/hsv_selector/hsv_selector_content.rs and src/config_selector/config_selector.rs
If you put random whitespace in either of those files and try formatting or calling cargo fmt, cargo fmt will fail to run.

@dogunbound thanks for reaching out and including the video. Currently rustfmt doens't support formatting let-else statements, but it's actively being worked on! If you'd like you can follow the issue for let-else #4914

@ytmimi
Thanks for letting me know. Hope progress continues smoothly.

source: gharchive/issue

authors: dogunbound ytmimi

repo: rust-lang/rustfmt


text:
Don't bail out of formatting code blocks if lines are >100 chars

Today rustfmt bails when trying to handle a code block that, after
formatting, has lines >100 chars. The reasoning was that if there were
lines longer than 100 chars it wasn't clear if we failed to format or
that was the intended result, so to be cautious the handler would bail.
However, if formatting the snippet fails the code block formatter will
already have jumped out by the time this line-width check is done:
https://github.com/rust-lang/rustfmt/blob/ff57cc6293ce450380dbb6da6a1a3656dbae538d/src/formatting/util.rs#L81
So I am not sure that this check is needed, and removing it broke no
tests except one designed explicitly for it. NB w.r.t. that unit test,
formatting a code like
fn main() {
    let expected = "this_line_is_100_characters_long_xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx(x, y, z);";
}

would yield no change, so I believe it is also the expected result.
Closes #4325

Thank you 🎉

I am a bit worried about the side effect this PR may introduce

Yes, I agree. If/when we get an issue because of this change, then we can concretely point and say why this cannot be changed.

authors: ayazhafiz topecongiro


text:
Fix multiline comment indentation

Fix an issue in light_rewrite_comment() when formatting 2nd and following lines  that start with * in a multiline comment.  Currently, the function prefix it with the byte preceding the *, so it will be aligned with the comment opening /*, assuming this character is a space.  The problem is that the preceding byte may be a tab or even may not exist when the * starts the line.
This fix makes sure that the * is prefixed by a space character.

Remind me, this is the scenario when there's a hard tab within the start and end of a a multiline block comment correct?
Also, could you do a rebase on master to fix the i686 windows jobs?

Remind me, this is the scenario when there's a hard tab within the start and end of a a multiline block comment correct?
Also, could you do a rebase on master to fix the i686 windows jobs?

Remind me, this is the scenario when there's a hard tab within the start and end of a a multiline block comment correct?

The issue is when hard tab is preceding the * at the second (and following) line of a multiline comment. The previous code used the char preceding the * in the original code to align the * with the /* of the first line. When this char is hard tab indentation was to the next tab place and not just by one space.

could you do a rebase on master to fix the i686 windows jobs?

Done

Remind me, this is the scenario when there's a hard tab within the start and end of a a multiline block comment correct?

The issue is when hard tab is preceding the * at the second (and following) line of a multiline comment. The previous code used the char preceding the * in the original code to align the * with the /* of the first line. When this char is hard tab indentation was to the next tab place and not just by one space.

could you do a rebase on master to fix the i686 windows jobs?

Done

could you do a rebase on master to fix the i686 windows jobs?

Done

Hmmm. Something's not looking quite right here (note the commit count and file diffs). Could you please take another look? The associated commits are relatively new so I largely remember what's already been changed, but the jump in the diff size requires a bit more human effort to identify the actual changed bits.
Please also note that with the current commit set in the PR all the original authors have been tagged in and will get spammed with notifications from all updates/posts/etc. so if it's easier to just move the relatively small proposed changes to a new branch and PR that'd be alright in this case.

could you do a rebase on master to fix the i686 windows jobs?

Done

Hmmm. Something's not looking quite right here (note the commit count and file diffs). Could you please take another look? The associated commits are relatively new so I largely remember what's already been changed, but the jump in the diff size requires a bit more human effort to identify the actual changed bits.
Please also note that with the current commit set in the PR all the original authors have been tagged in and will get spammed with notifications from all updates/posts/etc. so if it's easier to just move the relatively small proposed changes to a new branch and PR that'd be alright in this case.

if it's easier to just move the relatively small proposed changes to a new branch and PR that'd be alright in this case.

Resubmitted the changes in PR #4658 and closing this issue.

Please also note that with the current commit set in the PR all the original authors have been tagged in and will get spammed with notifications from all updates/posts/etc.

The issue was cased because I did the rebase by git pull --rebase.  I was not aware of the side effects.

if it's easier to just move the relatively small proposed changes to a new branch and PR that'd be alright in this case.

Resubmitted the changes in PR #4658 and closing this issue.

Please also note that with the current commit set in the PR all the original authors have been tagged in and will get spammed with notifications from all updates/posts/etc.

The issue was cased because I did the rebase by git pull --rebase.  I was not aware of the side effects.

authors: calebcartwright davidBar-On