containers should provide some way to not panic on failed allocations

I was working on a Rust image library, which has code like:

  vec![0xff; self.num_channels * self.width as usize * self.height as usize]

This code should really be checking for overflow on the multiplications. But doing so only eliminates one class of problems with this code: it's still reasonable for a maliciously crafted image to have large self.width and self.height values whose product doesn't overflow usize and yet the amount of memory can't be allocated. (I discovered this through an image test suite that has images with...large widths and heights that ought to return errors, but panic'd in Rust.)

Looking through the documentation, I didn't see any way of avoiding this panic-on-allocation failure, either at vector creation, or when trying to append elements to a vector.

I think this is pending the custom allocator work.

Yes, in general, the standard library assumes that you can't really handle OOM. Using libcore and custom allocators, you could implement whatever behavior you'd like, but you'd still need to re-implement this kind of thing on top of it.

The standard library is going to operate this way for the forseeable future, as it would require changing the signatures of stable things (like vec!) in a backwards-incompatible way. So I'm going to give this one a close.

@steveklabnik

So I should have been clearer about this: I don't think that all operations would need to return bool or Option or whatever. Firefox's data structures (which I'm most familiar with for something like this) typically have an "infallible" (i.e. panic on allocation failure) and "fallible" (return error value on allocation failure) variant of all the appropriate operations. Simply adding fallible operators, while increasing the API surface quite a bit, should also mean that this work could be done in a backwards-compatible way, as the current (infallible) API wouldn't have to change. So you'd have vec! and vec_fallible!, for instance, Vec::with_capacity and Vec::with_capacity_fallible, and so forth.

To my mind, it'd be better for the standard library to have this sort of thing, rather than folks having to write their own crate for VecFallible<T> or whatever and needing to propagate that through dependencies.

Does that seem reasonable, @steveklabnik ? I'm afraid I'm ignorant of the custom allocator bits cited herein, so I can't really tell if that's a way to modify the allocation behavior of Vec<T> or something else.

Independent of the custom allocators, i.e. Vec<T, A> where A: Allocate, I guess Vec would still have to expose fallible versions of these operations in order to avoid A's default out-of-memory behavior. This is possible to implement right now (RawVec manually calls oom, for example), but probably needs an RFC.

Yeah this is a tricky problem. I'd really not like to bloat up the collections APIs with _fallible variants if we can avoid it. However custom allocators will do nothing for this, as apasel notes.

To be exhaustive, we'd need to provide fallible versions of:

Vec:

push
insert
extend
resize
append
split_off
into_boxed_slice
reserve
reserve_exact
with_capacity
shrink_to_fit ???
clone
vec!

Maps:

insert
entry
extend
with_capacity
reserve
shrink_to_fit ???
clone

Unless you believe that only a subset is "truly" necessary?

Waking up, and this is getting more in cache. Part of this problem is the fuzzy nature of OOM on modern platforms (at least, Linux). It's my understanding that you can happily allocate some eggregious amount of memory from a bad image, only to get smacked down by the OOM killer when you really start trying to use the memory, and there's no way for us to deal with that.

Is there any problem with just having an incredibly reasonable policy like "no images bigger than 100MB"?

I assume this wouldn't be backwards-compatible, but it'd be nice to avoid the proliferation of methods with something like:

#![feature(default_type_parameter_fallback)]

pub trait AllocResult<T = (), E = ()> {
    fn ok(value: T) -> Self;
    fn err(err: E) -> Self;
}

impl<T, E> AllocResult<T, E> for T {
    fn ok(value: T) -> T { value }
    fn err(_err: E) -> T { oom(); }
}

impl<T, E> AllocResult<T, E> for Result<T, E> {
    fn ok(value: T) -> Self { Ok(value) }
    fn err(err: E) -> Self { Err(err) }
}

impl<T> Vec<T> {
    pub fn with_capacity<T, R: AllocResult<Self> = Self>(cap: usize) -> R {
        let ptr = alloc::heap::allocate(...);
        if ptr.is_null() { R::err(()) } else { R::ok(Vec { ... }) }
    }

    pub fn push<R: AllocResult = ()>(&mut self, item: T) -> R {
        if self.needs_reallocate() {
            let ptr = alloc::heap::reallocate(...);
            if ptr.is_null() { return R::err(()); }
            ...
        }
        ...
        R::ok(())
    }
}

#[test]
fn test() {
    let vec: Vec<i32> = Vec::with_capacity(5); // aborts on OOM

    let mut vec: Vec<i32> = match Vec::with_capacity(5) { // returns `Err` on OOM
        Ok(vec) => vec,
        Err(_) => panic!("OOM"),
    };

    vec.push(1); // aborts on OOM

    match vec.push(1) { // returns `Err` on OOM
        Ok(_) => {}
        Err(_) => panic!("OOM"),
    }
}

But this is clearly less discoverable and comprehensible for users.

Waking up, and this is getting more in cache. Part of this problem is the fuzzy nature of OOM on modern platforms (at least, Linux). It's my understanding that you can happily allocate some eggregious amount of memory from a bad image, only to get smacked down by the OOM killer when you really start trying to use the memory, and there's no way for us to deal with that.

That's a reasonable point, but on Windows the memory allocator really can fail, and Rust should be able to deal with that relatively gracefully. I don't know about OS X; I'm guessing it's more like Windows than Linux in this regard?

Is there any problem with just having an incredibly reasonable policy like "no images bigger than 100MB"?

A 100MB image is just 5k x 5k x 32bpp (raw pixel data), which is pretty big (roughly 3x 4k monitors), but doesn't sound like anything too out of the ordinary.

I'm having trouble finding details TBH. It would appear that FreeBSD supports overcommit, and by extension OSX/iOS seem to as well, at least to a limited extent. It certainly seems that they will do implicit deduplication and then copy-on-write transparently. Since the COW can presumably fail to find any physical memory (otherwise why bother? cache?), that opens up code to the same implicit failure state. iOS at least will send your application a warning that the OOM killer is eyeing it, giving it a chance to make amends (but this may be futile if other memory-starved applications are eating all the memory you're giving up).

Good old SIGDANGER

IIRC there was some discussion about allowing custom allocators someday. In combination with specialization, could an allocator + impl<T> Vec<T, NonPanicAlloc> {} be used to create an entirely new set of functions (returning Result) while blanking out the original functions?

cc me

@gankro you mean something like #29802 (comment) ?

Yeah I don't want to do that. I want to add an associated error type to the allocator trait, make it ! in the infallibility wrapper, and then "unwrap" Result<T, !> in the infallible methods.

Oh ok, well that one just won't ever be implemented, so it's even less possible to implement today?

Huh? Lets not confused not wanting to do something with the impossibility of doing something. This is the main benefit of the associated error type, so it's good to consider together.

Sorry do you mean having (on Vec<T, Alloc>):

fn push(&mut self) -> Result<(), Alloc::Err> {
  if cap == len { self.alloc.reserve(1)? }
  ...
}

or

fn push(&mut self) {
  if cap == len { self.alloc.reserve(1).unwrap() }
  ...
}

fn try_push(&mut self) -> Result<(), Alloc::Err> {
  if cap == len { self.alloc.reserve(1)? }
  ...
}

Ah, sorry if I was unclear before. Here's a more worked out example:

//!
//! in alloc or collections, based on how that shakes out
//!

struct PanicOom<T>(T);

impl<A: Alloc> Alloc for PanicOom<A> {
   type Error = !;

   // much repetition of
   fn something(&mut self) {
     self.something().or_else(|_| self.oom())
   }
}

// In the future, define and use a:
// trait InfalibleAlloc=Alloc<Error=!>;

//!
//! in collections
//!

impl<T, A: Alloc> Vec<T, A> {
  fn try_push(&mut self) -> Result<(), A::Err> {
    if cap == len { self.alloc.reserve(1)? }
    ...
  }
}

// in the future, use `InfalibleAlloc` for more readable bound
impl<T, A: Alloc<Error=!>> Vec<T, A> {
  fn push(&mut self) {
    self.try_push().void_unwrap()
  }
}

//!
//! In std
//!

// stop gap until we have aliases with params with default args
type HashMap<K, V> = HashMap<K, V, PanicOom<GlobalAlloc>>;

The idea being one either uses only vec.push() or vec.try_push(). If they mainly use vec.try_push(), they can add some manual expect, explaining why some critical allocation cannot fail. If they mainly uses push, it would be silly to out-of-the-blue handle an allocation failure when the code at large is not robust against it.

@Ericson2314

This is an interesting idea, but it seems like a lot of work for a lint that none of the users I've interviewed actually seem interested in.

@Ericson2314 do you intend to use this API? What for? (feel free to contact me on irc/email/twitter if you prefer)

If we're talking about a lint for unhandled allocation failures (non-fallible allocations), I and many others are very interested. Codec libraries (and most other libs) are usually required to gracefully handle any alloc failures.

…

On Aug 3, 2017 12:28 PM, "Alexis Beingessner" ***@***.***> wrote: This is an interesting idea, but it seems like a lot of work for a lint that none of the users I've interviewed actually seem interested in. @Ericson2314 <https://github.com/ericson2314> do you intend to use this API? What for? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#29802 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAGln17P3erDaE5NL_lOyO6Wg_Eqha-nks5sUhFWgaJpZM4GhKY0> .

Sorry to be clear: there is a strong desire for such a lint, but this is a lot of work for a weak version of it.

I could have sworn I linked this thread here, but I don't see it, so here's where I discuss various options and what different users were asking for: https://internals.rust-lang.org/t/notes-interviews-on-fallible-collection-allocations/5619/8

In it I describe hooking into the availability lint system that is intended to solve similar problems like "don't use floats". This would be more robust in that it would also verify you don't call methods which e.g. create their own Vec and infallibly allocate.

@aturon

Well, I'm glad you find it interesting :). This is something I've murmored about for a while, but I guess I made the mistake of never actually writing it down.

Truth by told, my day job is Haskell so I personally will not have the time to be a serious consumer of the allocation APIs any time soon. I hope to fine time to use it in my tiny toy OS, but that's it for now.

My general principle is while I'm sure serious industrial users can get away without any sort of lint, it's a nice thing to have that helps everyone not shoot themselves in the foot and, more importantly, help (no-std, for now) library authors not shoot each other in the foot, so the ecosystem can better trust itself.

@aturon mentions the portability lint, but I think that's a rather heavyweight solution for dealing with a pure-Rust interface (as opposed to however allocation is implemented). In particular, no one has proposed a modular way just yet for using it with user-defined CFG tokens. Now, cargo features would be the natural solution, and I suppose we could add a "oom-ignore" default feature for alloc/collections, ~~but I rather put the feature cfg just once on OomPanic than every single faux-infalliable method. That seems more maintainable.~~ Ah oops. We'd need per-method CFGs either way, but it would be easy to forget one without this, whereas the cfg on OomPanic will force us to not forget to also cfg the method (in conjunction with the portability lint).

[edited a bunch, a hard habit to kick.]

@gankro Ah your latest comment appeared as I was writing this. Nor had I read the thread. Glad to here we all do want a lint. In light of that I think my point about making the lint easier to maintain is perhaps the best.

Relatedly, for refactoring existing Rust code, e.g. Servo, I'd want

A transition feature so that the faux-infalliable methods are defined for all allocators with unwrap instead of void_unwrap.
A tool to convert all .foo() to .try_foo().unwrap(), which would then making auditing far easier--grep for unwrap or try.*unwrap.
Run that and disable the feature.

And again in terms of expediency, while the portability lint is not yet implemented, everything I mention an be done today. A road map could be

Immediately add associated type, PanicOom, and convert all collections to use infallible allocators. No clever thinking about algorithms is needed.
Collection-by-collection, see if algorithms can be tweaked to support the fallible case---easier for flat ones like Vec, a good deal harder for tree-based ones (if we don't consume the collection lest it gets in an inconsistent state).
Whenever the portability lint using features is ready to go, the cargo features can be in place to support them.

To be clear, we identified that the lint was nice to have but in no way a blocker for our users. As such we planned to punt on it and solve it more robustly with actual lints. In the mean time we could provide the methods, and users could build wrapper types to hide infallibility if they chose want.

On the topic of different collections, only BTreeMap would run into issues with a naive translation. It shouldn't be too difficult to pre-allocate the nodes before starting the mutations.

@gankro I think expecting users to write their own wrapper types is futile because the biggest benefit is trust between libraries, but I can't see any wrapper types outside of the libcollections becoming as standard.

I also forgot to mention how error-type polymorphism allows one to convert code bases function by function.

Is there anything you dislike about mine, besides it being a lot of work in your eyes?

RFC: rust-lang/rfcs#2116

Since the RFC was merged, and I believe future work in this area will require extensive discussion (either on internals or in RFC(s)) I'm closing this issue.

Navigation Menu

Repository navigation

containers should provide some way to not panic on failed allocations #29802

30 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

containers should provide some way to not panic on failed allocations #29802

Description

Activity

apasel422 commented on Nov 12, 2015

steveklabnik commented on Nov 12, 2015

froydnj commented on Nov 13, 2015

apasel422 commented on Nov 13, 2015

Gankra commented on Nov 13, 2015

Gankra commented on Nov 13, 2015

apasel422 commented on Nov 13, 2015

froydnj commented on Nov 13, 2015

Gankra commented on Nov 14, 2015

sfackler commented on Nov 14, 2015

oli-obk commented on Nov 16, 2015

jdm commented on Nov 16, 2015

30 remaining items

Ericson2314 commented on Aug 3, 2017

Gankra commented on Aug 3, 2017

Ericson2314 commented on Aug 3, 2017

Gankra commented on Aug 3, 2017

Ericson2314 commented on Aug 3, 2017

Gankra commented on Aug 3, 2017

lilith commented on Aug 3, 2017

Gankra commented on Aug 3, 2017

Ericson2314 commented on Aug 3, 2017

Ericson2314 commented on Aug 3, 2017

Gankra commented on Aug 3, 2017

Ericson2314 commented on Aug 3, 2017

Gankra commented on Aug 18, 2017

Mark-Simulacrum commented on May 28, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions