RFC: Add more support for fallible allocations in Vec

[dpaoliello]

Vec has many methods that may allocate memory (to expand the underlying storage, or shrink it down). Currently each of these method rely on "infallible" allocation, that is any failure to allocate will call the global OOM handler, which will (typically) panic. Even if the global OOM handler does not panic, the return type of these method don't provide a way to indicate the failure.

Currently Vec does have a try_reserve method that uses "fallible" allocation: if try_reserve attempts to allocate, and that allocation fails, then the return value of try_reserve will indicate that there was a failure, and the Vec is left unchanged (i.e., in a valid, usable state). We propose adding more of these try_ methods to Vec, specifically for any method that can allocate. However, unlike most RFCs, we are not suggesting that this proposal is the best among many alternatives (in fact we know that adding more try_ methods is undesirable in the long term), instead we are suggesting this as a way forward to unblock important work (see the "Motivations" section below) while we explore other alternatives.

Rendered

PR to add new methods

[programmerjake]

note that there are proposals (such as the Storages proposal) that change Vec to use something other than A: Allocator, so maybe there should be a comment to that effect somewhere so all of these don't get accidentally stabilized with stable A: Allocator arguments.

[ojeda]

Out of the given alternatives, it seems to me the one proposed by the RFC is the simplest (only new methods are added, no new compiler features needed, etc.) and the most flexible too (allows to mix fallible/infallible paths, can be used in all environments, etc.).

The "decision point for developers" drawback can be minimized by adding some documentation-level feature, such as grouping of methods (potentially collapsed by default) or having "alternative methods" of others, etc. This also makes it a future, orthogonal improvement, rather than an alternative ("Add a trait for the fallible allocation functions") that affects the design.

[jdahlstrom]

Another possible alternative: a light-weight fallible wrapper or view type that you could use at any point to opt-in to fallible allocation but still retain compatibility with APIs that take vanilla Vecs.

However, it also occurs to me that a fallible-alloc Vec may not want to be compatible with APIs that take infallible-alloc Vecs by move or &mut because said API might do things that cause allocations! APIs that take Vecs by shared ref would be fine, but those should be rare because taking a slice is the idiomatic way.

[Ericson2314]

Another possible alternative: a light-weight fallible wrapper or view type that you could use at any point to opt-in to fallible allocation but still retain compatibility with APIs that take vanilla Vecs.

That would be fine with me. Wrapping &Vec and &mut Vec does not have the downsides that wrapping Vec itself does.

However, it also occurs to me that a fallible-alloc Vec may not want to be compatible with APIs that take infallible-alloc Vecs by move or &mut because said API might do things that cause allocations! APIs that take Vecs by shared ref would be fine, but those should be rare because taking a slice is the idiomatic way.

That is what #[cfg(not(no_global_oom_handling))] is for, along with the Cargo feature that could replace it (https://github.com/rust-lang/rfcs/pull/3140).

It's very subtle to both allow enforcing a policy and avoid causing unnecessary ecosystem forks --- those goals a dangerously close to being contradictory.

With the aforementioned mechanisms, we move the goal posts slightly. Types prioritize not splitting the ecosystem, while cfg mechanism prioritize enforcing a policy. We've floated other solutions (e.g. associated error types on allocators), but the current method strikes me as easiest to wrap ones head around, with the type-level vs cfg-level division of labor.

[dpaoliello]

@m-ou-se Any comments on this RFC? I've like to get the Vec::try_ methods merged in, even if they never stabilize and are subsequently removed.

[jdahlstrom]

If these methods are added to Vec, it should be ensured that they do not clutter the docs and eg. IDE completions. Unfortunately, stddocs display unstable items in stable docs and there's no setting to toggle their visibility. If this is not feasible (without making them all #[doc(hidden)]) then IMO this is a large drawback of the proposal and should be mentioned in the RFC.

[Ericson2314]

@jdahlstrom

@dpaoliello wrote in https://github.com/rust-lang/rust/pull/95051#issuecomment-1146208051 that #[doc(hidden)] is a fine concession to make if it helps make this happen, and I agree.

[scottmcm]

That would be fine with me. Wrapping &Vec and &mut Vec does not have the downsides that wrapping Vec itself does.

This made me think. Anything that could possibly reallocate an existing Vec necessarily must be &mut self.

That means that one wrapper on &mut Vec<_>, with a convenience method, could be a nice way to split these into their own documentation page and emphasize them in the code. Like vec.checked_allocations().reserve(n), or something. (Probably with a much better name than that, because that's super-long.)

That would also give the possibility of a similar wrapper for use-existing-capacity versions. Because a major problem with try_push is that I might have thought it would never reallocate, but would instead fail if there wasn't available capacity. And then vec.existing_capacity().push(x) could be the way to spell that kind of fallibility. (Again under a better name than that one.)

[jdahlstrom]

That means that one wrapper on &mut Vec<_>, with a convenience method, could be a nice way to split these into their own documentation page and emphasize them in the code. Like vec.checked_allocations().reserve(n), or something. (Probably with a much better name than that, because that's super-long.)

Yes, this was pretty much what I had in mind. Or if you need to do multiple fallible operations in sequence, just let foo = vec.bikeshed() and NLL will give you the original Vec back once you're done.

[Ericson2314]

I hope we can reach a decision on this soon? Rust on Linux with a fork along these lines is inching closer to being accepted, and (even if it is post merge) I would really like to get them off a fork.

The bottom line to me is that whatever we end up stabilizing will be closer to the proposed interim solution here than the status quo. We're reworking the implementation (never mind the interface on top) in ways I think we're extremely unlikely to regret.

[BurntSushi]

Rust on Linux with a fork along these lines is inching closer to being accepted, and (even if it is post merge) I would really like to get them off a fork.

Do we have any Rust For Linux stakeholders that can confirm whether this RFC is sufficient to get them off of their fork?

[alex]

I think this would let us remove most of the methods we've added -- not sure about alloc.

@ojeda with no new methods, do you think the #[cfg(...)] would be enough to handle the other things we patch alloc for (IIRC it's removing other stuff, such as infalible allocs)?

[ojeda]

@BurntSushi It is too early to say how we will end up using alloc medium/long-term.

It is true that we added similar APIs, so if they were there, we would remove the custom ones. From a quick look, I think this would cover everything we added to Vec, but we have some bits for [T] and str too. See https://lore.kernel.org/lkml/[email protected]/ as an example of the delta.

However, even if this RFC covered everything at the moment, we could need something else soon, so I would keep the fork for a while even if there is no delta at all.

Not to mention other design concerns we are considering, e.g. passing flags to our try_* methods. It may be all doable with extension traits on top of an unmodified alloc, but we will have to see where we end up.

Also, since the merge was mentioned above: note that the kernel does not provide any stability guarantees for internal APIs, thus how or whether alloc is used may change in the future. It also means the merge does not really signify anything with respect to alloc.

[Ericson2314]

Yeah @BurntSushi the way I see it, for a variety of reasons some of which aren't even technical, there will be a copy of alloc vendored in Linux (post merge) for the foreseeable future, and Anything Could Happen. But at least in the meetings I attended long ago, it was discussed marking vendor with a "this is vendored, don't change it willy-nilly, we need to sync with upstream notice", as was done for other such vendored libraries already in the kernel tree (I think zstd was mentioned). More broadly, it was agreed that if Linux can avoid diverging from alloc where possible that would be Good Thing.

In the previous message, https://lore.kernel.org/lkml/[email protected]/, note it says

Eventually, the goal is to have everything the kernel needs in upstream alloc and drop it from the kernel tree.

Eventually is a key word; there is no deadline for when this might happen, but I hope this at least services as evidence there is agreement it would be a nice place to get to.

https://lore.kernel.org/lkml/[email protected]/

Note is the only such modification of the standard library. The PR corresponding to this RFC in fact grew out of an earlier version of this patch.

From a quick look, I think this would cover everything we added to Vec, but we have some bits for [T] and str too.

I would imagine any such missing parts have been to that patch since the PR (an its antecedents) was made. I am guessing @dpaoliello and I would be perfectly happy to add them to this PR / RFC too; they after all just more such try_ functions not conceptually different from the ones we already have.

[ojeda]

But at least in the meetings I attended long ago, it was discussed marking vendor with a "this is vendored, don't change it willy-nilly, we need to sync with upstream notice"

...and that is exactly what I wrote in the README.md that is committed into the tree [1], not just in a commit message:

+Please note that these files should be kept as close as possible to
+upstream. In general, only additions should be performed (e.g. new
+methods). Eventually, changes should make it into upstream so that,
+at some point, this fork can be dropped from the kernel tree.

[1] https://lore.kernel.org/lkml/[email protected]/#Z31rust:alloc:README.md

In fact, the rest of the file gives some more of context on those discussions you are referring to.

However, regardless of what I write in the README.md file, the kernel's needs and goals may change in the future, so we cannot really promise we can get off the fork with this RFC. In particular, I was replying to @BurntSushi who asked very concretely:

Do we have any Rust For Linux stakeholders that can confirm whether this RFC is sufficient to get them off of their fork?

to which the answer is simply "no, we cannot confirm that". This does not mean, of course, that we are not trying.

[BurntSushi]

@ojeda Aye thanks. And the reason why I asked that was because of what @Ericson2314 said above:

Rust on Linux with a fork along these lines is inching closer to being accepted, and (even if it is post merge) I would really like to get them off a fork.

And that specifically is important because of this text in the RFC (emphasis mine):

Unlike most RFCs, we are not suggesting that this proposal is the best among many alternatives (in fact we know that adding more try_ methods is undesirable in the long term: see the "Drawbacks" section below), instead we are suggesting this as a way forward to unblock important work (see the "Motivations" section below) while we explore other alternatives. We have no plans to stabilize this feature in its current form and fully expect that these methods will be removed in the future.

So the higher level question here is: who is this RFC for? What specific work is being unblocked? Who, exactly, is able to get away from forks with this RFC?

I'm not necessarily opposed to some practical trade off here where we add some unstable routines that we probably won't ever stabilize in order to get a bunch of people off of forks of alloc. But I want to know who is actually going to be able to get off of their fork. :)

[Ericson2314]

@BurntSushi The goal is to try to LInux and the Rust standard library drifting apart. The reason for this goal is:

1. To make Linux less unfamiliar for new kernel developers coming from Rust. (Something we all hope will be increasingly frequent.)

2. To make sharing code between Linux itself and other users easier. A goal of Rust that C doesn't have is highly reusable abstractions. Let's show that off!

3. Upgrading to a newer version of Rustc is harder if the Kernel is on a diverged copy.

4. Maintaining a diverged copy is extra work in general.

Neither side can fully commit to this solution, and that should be fine! Let's not make the perfect the enemy of the good. Here's what I am thinking:

1. If/when the Rust lib time wants to replace these functions for a new explicit-handling solution, it would behoove them to see whether a marquee project like Linux can work with the new solution. If it cannot, that might be a sign the new solution isn't as good.

2. If the patch of alloc is removed, that will give Linux developers great pause on changing thing: it's one thing to modify a library that's already diverged, it's another thing to do the first modification of a library that is currently included verbatim.

[Ericson2314]

@BurntSushi Also I think there might be confusion around the word "fork". The code being vendored in-tree != forking is constantly in progress. Yes, the kernel devs can do whatever they want with that copy, but we shouldn't just assume it's fait accompli that because there is a separate copy it will drift apart as a full-on fork.

Maybe it does drift apart. Maybe it starts to, and then someone complains when it comes time to upgrade the Rust compiler, "why do we have this stupid fork that makes this chore harder?". Maybe the Linux developers decide it is OK to depend on out-of-tree sources after all, and this and many other vendors are gotten rid of. Maybe Linux even starts using Cargo!

All of the above are future possibilities. I am personally choosing the cautiously optimistic prediction of "no one wants the current divergence, let's get rid of it and another is unlikely to occur". I don't want to compel everyone else to assume that prediction, but I equally don't want them to assume some pessimistic prediction in stead.

[randomPoison]

So the higher level question here is: who is this RFC for? What specific work is being unblocked? Who, exactly, is able to get away from forks with this RFC?

The Trusty secure OS in Android would also like to make use of the proposed additions. Similar to Linux, we're currently using a forked version of parts of the standard library where we've added fallible allocation support. We'd like to move away from maintaining our own fork and use upstream APIs instead, even if that means using unstable features for the time being. The additions proposed in this RFC meet our current needs and so would work fine as a stopgap until something else can be stabilized.

[Ericson2314]

Thanks for weighing in @randomPoison!

Two projects independently modifying the standard library to add the same functionality that cannot be implemented downstream feels like very strong motivation for me!

[ojeda]

@BurntSushi You're welcome!

who is this RFC for? What specific work is being unblocked?

For Rust for Linux, while we cannot promise it would get us off the fork, it would be useful to have the functions even if as unstable. At least at the moment, it would make life easier since the size of the fork would be reduced, although it doesn't "unblock" anything as such.

It is also very useful to be able to show that upstream alloc is working on trying to make that happen (and I want to thank @Ericson2314, @dpaoliello et al. for all the work they have done so far on this RFC and other issues/PRs).

[m-ou-se]

Some general thoughts about the problem this RFC is solving:

The problem with the Vec interface reminds me of lock poisoning of std's Mutex. For both Vec and Mutex there's a certain type of failure (allocation failure for Vec, poison for Mutex) that a large group of users does not want to handle. A default (e.g. just panic) works fine for many (most?) users.

For Mutex, we went for the most flexible but more verbose option of always returning a Result, which means that most users are writing .lock().unwrap() everywhere, which isn't great.

For Vec, we went with the less flexible and less verbose option of never returning a Result and just panicking, which is also not great.

In both situations, none of the possible solutions seem a good fit. We've discussed adding a second Mutex with a non-poisoning interface, and similarly, second Vec with a fallible allocation interface. But adding a new type for effectively the same thing isn't a great solution. An alternative is to duplicate most of the methods, like adding Mutex::lock_ignore_poison() and Vec::try_push() (this RFC), but that also has the potential tot quickly get out of hand.

It seems to me we're missing the right tool to deal with these situations. Some kind of way to have a different interface for the same type, or something like that. I'm wondering if there could be some elegant new language feature that could help us out.

[m-ou-se]

Some more concrete thought about this RFC:

I feel unsure about using the try_ prefix for this. We already have try_insert on some data structures, where try_ does not refer to allocation failures. I've also heard some ideas about a Vec::try_push method that tries to push only within the existing capacity, without ever reallocating. We've had more situations where the word try is inconsistent/ambiguous, and I'd be extra careful with that on a very widely used data structure like Vec.

Can all the proposed methods currently be implemented outside std? If so, it might make sense to first implement it all as an external crate (e.g. crates.io) that provides all these methods as an extension trait.

[phaylon]

@m-ou-se

It seems to me we're missing the right tool to deal with these situations. Some kind of way to have a different interface for the same type, or something like that. I'm wondering if there could be some elegant new language feature that could help us out.

I'm wondering if inherent traits, or at least the API surface discussions that happened there, would be of interest or relevance here? Grouping behavior seems like a trait thing to me.

[ojeda]

It seems to me we're missing the right tool to deal with these situations. Some kind of way to have a different interface for the same type, or something like that. I'm wondering if there could be some elegant new language feature that could help us out.

Agreed, this would benefit from a more general solution.

One approach I suggested in the past, from a documentation perspective, was allowing to tag/group methods together somehow (e.g. "Fallible allocation API"). rustdoc could use then that information to render them together.

Some more potential use cases for any such feature:

• Grouping together conceptually related methods, i.e. existing ones, especially if one can provide docs.

  • Some crate/type/module-level docs already do something similar, e.g. Vec with its "Indexing" and "Slicing" sections.
  • The C++ standard has something like that too, e.g. "modifiers" / [vector.modifiers], "capacity" / [vector.capacity]..., and some popular reference pages group things more or less accordingly, e.g. cppreference's vector.
  • This could be specially useful for big APIs like [T].
  • It could be a good place to explain e.g. what a prefix like try_ actually means, if we end up with several try_s around with different meanings.

• Grouping advanced, low-level, uncommon, unsafe... APIs, which could potentially be unexpanded by default.

• Being able to group methods without necessarily forcing them to start with the same prefix, e.g. wrapping_* on integers.

a different interface for the same type

Are you thinking about having the same name for different methods depending on which interface one picks? If so, and if one can change from one to another in different contexts or something like that, then one concern to have in mind is whether it would hurt readability / greppability.

[bjorn3]

The C++ standard has something like that too, e.g. "modifiers" / [vector.modifiers], "capacity" / [vector.capacity]..., and some popular reference pages group things more or less accordingly, e.g. cppreference's vector.

Rustdoc allows placing doc comments on an impl block. That seems similar to what the C++ standard does.

[m-ou-se]

One approach I suggested in the past, from a documentation perspective, was allowing to tag/group methods together somehow

We can already group methods by putting them in a separate impl block. Each impl block can have its own doc comment:

But I don't think that's a solution. We'd still end up with verbose or very ambiguous method names. E.g. what would a fallible-allocation variant of HashMap::try_insert() look like? try_try_insert()? ^^'

Same for lock poisoning: adding a .lock_or_panic_on_poison() method next to the .lock() isn't much of an improvement over .lock().unwrap().

It'd also be useful to disable or at least discourage a certain interface project/crate-wide. E.g. avoiding kernel (Rust) code from using Vec's panicking methods. Having rules like "never use push and always use try_push" (or the opposite) is 'social coordination', but I'd much prefer to make our tools responsible for that instead of having to keep track of such manually coordinated agreements.

The most obvious tool we currently have are types. A separate poisoning and non-poisoning Mutex type would make it hard to accidentally ignore poison when poisoning types are used. Same for Vec, if we had separate 'just panic' and 'return Result' types: you couldn't accidentally do a panicking operation if the type doesn't support that. But having two separate types is not great in many ways, since much of the types is similiar or identical. So this is not a great solution, or at least not a complete one.

I'm not sure what the solution is. But I feel like we might be missing the right tool.

Are you thinking about having the same name for different methods depending on which interface one picks?

Maybe. Then in places like the kernel, v.push() would return a Result, without needing try_ all over the place. That might be a bad idea, but Rust is strict enough about types that an identically named method returning () or Result<..> in different projects isn't something that's accidentally ignored, potentially making it okay. Not sure. How this interacts with dependencies is an interesting question. It feels a bit like 'editions' for types. ^^' That would be a big rabbit hole, but maybe someone has an elegant idea that doesn't make it complicated.

I don't mean to derail this RFC, but I don't think we should be adding so many methods without a plan to prevent it getting out of hand. To move things forward more quickly: Can what this RFC proposes be done as an extension trait in a separate (non-standard) crate?

[alex]

I think, it should be technically possible to do something like (maybe this required GATs? not sure, without having actually tied to implement this :-)):

fn push<F: Fallibility<T> = Infallible<T>>(&self, v: T) -> F::Result

And then v.push::<Fallible<T>>(x)?. I guess you could also make it type-level, rather than method level.

This makes signatures a lot more complex. But it does keep you to a single method. It makes the non-default choice a bit verbose though -- somewhere like the linux kernel we want all operations to be fallible.

[y86-dev]

Having read the last few comments gave me an idea. I have formulated it on IRLO.

And then v.push::<Fallible<T>>(x)?

I do not really like that approach, it is not really ergonomic. If we were to use the type level generic, then every function taking a Vec would need to be generic as well... (and we already have that problem with the allocator)

[the8472]

That's what I proposed in this review comment