Fallible Allocation Notes

notes.md

Background

methods like push on Vec don't provide anyway for the caller to handle OOM. (I will be using push as substitute for "all allocating APIs" for simplicity here)

• Today we always abort.
• Moving to unwinding is problematic
  • unsafe code may be exception unsafe on the basis of current strategy
  • almost everyone tells me that C++'s version of this is bad
  • libunwind allocates

Want to introduce some way to handle it.

Major contenders

• Types to distinguish fallibility

  • FallibleVec<T>, replaces push(T) with push(T) -> Result<(), (T, AllocFailure)>
    • doesn't support generic use of Vec/FallibleVec
    • hard to do mixed usage of fallible and non-fallible
      • or at least, outside allocating code, fallibility loses relevance
  • Vec<T, F: Fallibility=Infallible>, makes push(T) -> F::Result<(), T>
    • requires generic associated types (stable late 2018, optimistically)
    • probably requires type defaults to be improved?
    • works with generics, but makes all of our signatures in rustdoc hellish
      • maybe needs "rustdoc lies and applies defaults" feature

• Methods to distinguish fallibility

  • Make mirrors of all methods -- try_push(T) -> Result<(), (T, AllocFailure)>
    • works fine, but people aren't happy about lots of methods
  • Only add try_reserve() -> Result<(), AllocFailure>
    • minimal impact
    • methods like extend/splice have unpredictable allocations
    • doesn't work with portability lints (see below)
    • might be nice to have anyway?
  • Add some methods, but ignore niche ones
    • Weird, going to make people mad

• Middle ground: method to temporarily change type

  • as_fallible(&'a mut self) -> FallibleVec<'a, T>
    • can do it for one method: vec.as_fallible().push(x)
    • or for a whole scope: let mut vec = vec.as_fallible()
    • doesn't enable generic use, weak for library interop
    • can be built on method style

Possible augmentation: negative portability lints

In some sense "don't use infallible allocation" is the same kind of constraint that kernel code has for "don't use floats". The latter is intended to be handled by negative portability lints, so we can do that too.

portability lints were spec'd here: https://github.com/rust-lang/rfcs/blob/master/text/1868-portability-lint.md

But the negative version (removing portability assumptions) was left as future work.

Strawman syntax -- add maybe as a cfg selector in analogy to ?Sized:

// In liballoc
impl<T> Vec<T> {
    // No need to mark push, implicitly #[cfg(std)] ?
    fn push(elem: T) { ... }

    // Say try_push doesn't infallibly allocate -- forces verification of body
    #[cfg(maybe(infallible_allocation))]
    fn try_push(elem: T) -> Result<(), AllocFailure> { ... }
}



// In your code
#![cfg(maybe(infallible_allocation))]
/* a bunch of functions/types that shouldn't use infallible allocation */

// or (equivalent)
#[cfg(maybe(infallible_alloction))]
mod allocation_sensitive_task;

// or (more granular)
#[cfg(maybe(infallible_allocation))]
fn process_task() {
    /* will get warning if any function called isn't #[cfg(maybe(infallible_allocation))] */
}

Note this analysis is local, so if you call any undecorated function from a third-party library, you'll get a warning. This is a bit annoying, but strictly correct insofar as longterm stability is concerned: they should publicly declare that they guarantee this. In this vein, adding a #[cfg(maybe)] from a public item isn't a breaking change, but removing one is.

This will also require a ton of careful stdlib decorating (don't want to promise things we shouldn't).

Interviews

I interviewed several people with industry experience in this problem, some stakeholders in Rust providing it.

Interview with Ehsan (Gecko dev; doesn't use Rust for it):

Gecko has fallible allocation in its standard collection types. Distinction can be done at the type level or method level -- there are factions that disagree on the right approach, and the issue doesn't appear to be settled?

• Personally prefers methods
• Almost all allocations in gecko are infallible; crashing is simple and maintainable (especially with multi-process!)
• Will fallibly allocate for some key things to improve reliability. Notably when website can create allocation disproportionate in size to network traffic (image size is a few bytes).
• Doesn't need to handle all fallible allocation in that region of code, or even on that buffer
  • happy to crash if the going gets tough.
  • In quick search of gecko, ¹ couldn't find any actual mixed use
    • Except a sketchy pattern ²
• Fallibility is a maintenance/safety hazard! Many untested branches.
  • In a quick search of gecko, I found a few cases that are written in a confusing way

(last two points are why methods are preferred)

// Fallibly reserve space
if (!output.SetCapacity(source.length, fallible)) { 
    return false; 
}

for (auto x : source) { 
    // Says fallible, but this is actually infallible; otherwise this is UB on OOM
    *foo.AppendElement(fallible) = x;
}

Interview with Whitequark (embedded dev; uses Rust for it):

Three lines of defense against the spectre of allocation:

• First: statically allocate; much harder to mess up.
• Second: Crash on oom! Usually hard abort (need to know how to recover anyway), but sometimes unwind (some Cortex-M devs)
• Third: actually handle oom.
  • fail at a task/request granularity
  • all allocations for task are in a pool, so that on failure we free the whole pool; avoid fragmentation
  • all allocations in this region of code are handled fallibly, no mixing strategies

Likes try_push, but wants an infectious unsafe-like lint on methods/calls to assert that some region of code never calls push and friends. If we do a typed approach, would prefer something generic for library compat.

Fallible allocation is a last resort, and devs are willing to put in work to use it properly.

Note: can we do something with local allocators here? Note: portability lints miiiight work with some tweaks? https://github.com/aturon/rfcs/blob/scenarios/text/0000-portability-lint.md

Interview with Swgillespie (CLR dev, works on the GC; doesn't use Rust for it)

Need collections for state in GC traces, e.g. stacks in graph traversal. If allocation fails, can try to shrink the stack and retry. OOMing while trying to GC is a bug.

• Uses global allocator (new with std::nothrow)
• Would use #[deny(infallible_allocations)]
• No preference on typed vs untyped.
• No need for being generic over fallibility (GCs are fairly concretely typed)
• No concern with interop with third-parties
• Lots of bugs from missing spots or failing to check results

Interview with nox (Servo dev; uses Rust for it)

Stylo needs it for Firefox 57, will be forking libstd collections until we provide these APIs.

Code like this which parses a list should be fallible: https://github.com/servo/servo/blob/de0ee6cebfcaad720cd3568b19d2992349c8825c/components/style_traits/values.rs#L251

Style sheet should just come out as "couldn't parse"/"didn't load" when this happens.

• Prefers methods to integrate into existing code where desired
• Moving to infallible likely to be incremental, as it's a big job
• Controls all the relevant libraries
• Doesn't care about generics
• Would like #[deny(infallible_allocations)], not super important though

Relevant Reading

• look into portability lints https://github.com/rust-lang/rfcs/blob/master/text/1868-portability-lint.md
• look into place API rust-lang/rfcs#1228
• look into allocator APIs https://github.com/rust-lang/rfcs/blob/master/text/1398-kinds-of-allocators.md

Footnotes

1. https://searchfox.org/mozilla-central/search?q=%5B%5En%5Dfallible%5C)&case=false&regexp=true&path== ↩

2. ↩

I, for one, (gecko dev, currently experimenting with re-implementing mozjemalloc in rust), would welcome Vec<T, F: Fallibility=Infallible>, push(T) -> F::Result<(), T>, but in a different form: Vec<T, A: Alloc=Heap>, which would continue the pattern started with RawVec. The Alloc trait would then gain the Result associated type, which, on Heap, would just be (). Or another trait derived from Alloc.