Tracking issue for allocation APIs

[alexcrichton]

Current status

Final incarnation of std::heap is being proposed in rust-lang/rfcs#1974, hopefully for stabilization thereafter.

Open questions for stabilization are:

• Is it required to deallocate with the exact size that you allocate with? With the usable_size business we may wish to allow, for example, that you if you allocate with (size, align) you must deallocate with a size somewhere in the range of size...usable_size(size, align). It appears that jemalloc is totally ok with this (doesn't require you to deallocate with a precise size you allocate with) and this would also allow Vec to naturally take advantage of the excess capacity jemalloc gives it when it does an allocation. (although actually doing this is also somewhat orthogonal to this decision, we're just empowering Vec). So far @Gankro has most of the thoughts on this.

• Is it required to deallocate with the exact align that you allocate with? Concerns have been raised that allocatores like jemalloc don't require this, and it's difficult to envision an allocator that does require this. (more discussion). @ruuda and @rkruppe look like they've got the most thoughts so far on this.

Original report

This is a tracking issue for the unstable APIs related to allocation. Today this encompasses:

• alloc
• heap_api
• oom

This largely involves just dealing with the stabilization of liballoc itself, but it needs to address issues such as:

• Are we willing to stabilize the exact interface of the allocation API as-is today?
• Do we want to stabilize custom allocators?
• Do we want to stabilize a standalone allocation library, liballoc?
• Should oom be a generally available piece of functionality, and should it be pluggable?

This will likely take a good deal of work to stabilize, and this may be done piecemeal, but this issue should serve as a location for tracking at least these unstable features.

[alexcrichton]

cc @pnkfelix

[SimonSapin]

It’s already possible to indirectly use allocate and deallocate in stable Rust:

fn allocate<T>(count: usize) -> *mut T {
    let mut v = Vec::with_capacity(count);
    let ptr = v.as_mut_ptr();
    std::mem::forget(v);
    ptr
}

fn deallocate<T>(ptr: *mut T, count: usize) {
    std::mem::drop(Vec::from_raw_parts(ptr, 0, count));
}

Any future GC support (mentioned in the #[unstable(feature="heap_api")) message) will need to deal with this.

While this hack has the merit of existing (and enabling many libraries to making themselves available on stable Rust),

• It’s ugly
• It’s hard to discover if you haven’t seen it before
• It’s sometimes awkward to use. For example, Tendril wants to do something like Rc<str> where a reference count is in a header next to (before) that bytes that make up a string. The header needs to be memory-aligned, but the amount of bytes is arbitrary. Tendril ends up calculating the next multiple of size_of::<Header> in order to find out what capacity of Vec<Header> to allocate for a given number of bytes.

While I’m not attached to the details of the current alloc::heap API, I think it’s important for Stable Rust to have a more straightforward way to allocate/deallocate memory.

[SimonSapin]

Random idea for a (more rustic?) RAII-based API for alloc::heap:

/// Allocated but not-necessarily-initialized memory.
struct Buffer {
    ptr: Unique<u8>,
    size: usize,
    align: usize,
}

impl Drop for Buffer {
    /* deallocate */
}

impl Buffer {
    fn new(size: usize, align: usize) -> Result<Self, ()> {
        /* allocate, but avoid undefined behavior by asserting or something
           (maybe skip calling allocate() on `size == 0`?) */
    }

    // Maybe skip those and keep the unsafe functions API?
    fn into_ptr(self) -> *mut u8 { /* forget self */ }
    unsafe fn from_raw_parts(ptr: *mut u8, size: usize, align: usize) -> Self { /* */ }

    fn as_ptr(&self) -> *const u8 { self.ptr }
    fn as_mut_ptr(&mut self) -> *mut u8 { self.ptr }
    fn size(&self) -> usize { self.size }  // Call this len?
    fn align(&self) -> usize { self.align }

    // The caller is responsible for not reading uninitialized memory
    unsafe fn as_slice(&self) -> &[u8] { /* ... */ }  
    unsafe fn as_mut_slice(&mut self) -> &mut [u8] { /* ... */ }

    fn reallocate(&mut self, new_size: usize) -> Result<(), ()> { /* ... */ }
    fn reallocate_in_place(&mut self, new_size: usize) -> Result<(), ()> { /* ... */ }
}

[kamalmarhubi]

It’s already possible to indirectly use allocate and deallocate in stable Rust:

this doesn't get you access to the align parameter though

[SimonSapin]

Not directly, but you can influence alignment by carefully picking T in Vec::<T>::with_capacity.

[kamalmarhubi]

@SimonSapin ooh nice! I'd have to read up on alignment rules to figure out if there's a type that would let me align to a page boundary or not, but nice trick :-)

[pnkfelix]

@kamalmarhubi This stackoverflow answer is probably the most relevant thing that is actually implemented today: http://stackoverflow.com/questions/32428153/how-can-i-align-a-struct-to-a-specifed-byte-boundary

(Longer term we'll presumably put in something better. The Allocator trait I'm proposing has Layout objects to describe blocks of memory that allow one to specify alignment constraints.)

[kamalmarhubi]

@pnkfelix thanks for the link. Sounds like I'm out of luck for page boundary alignment though! I am also unclear if the allocator would hate me for SPLICE_F_GIFT pages to the kernel. I should probably set up my own anonymous mapping for this anyway...

[glaebhoerl]

It took me several seconds to realize that "aligning to a page boundary" actually wasn't a tongue-in-cheek joke about text rendering...

[lilith]

I noticed that set_oom_handler mentions this issue and provides not a scrutinized interface as the reason for instability.

Echoing @glandium, my focus is:

what can rust code do to gracefully handle memory allocation failure?

Per #33082 (comment), I understand the answer is:

Currently, in stable Rust, nothing. All collections and pointers in the standard library end up calling that oom routine if a memory allocation fails. We plan on stabilizing the ability to handle this eventually, but that's pretty far off.

I'm focused on server use cases - particularly those where large allocations are both common and recoverable. I think a strong case for OOM recoverability has been made in several ways.

I would, ideally, like to see

• APIs which trigger allocations flagged in some fashion (and ideally documented). Has this been considered?
• The stabilization of set_oom_handler or another method for making OOM recoverable.

Looking at actionable options, I appear to be presented with:

1. Re-implementation of all allocating functions I encounter. Is this list actually exhaustive, or only for collections?
2. Looking for actionable work I can perform to accelerate stabilization of set_oom_handler. What would be most helpful?
3. Using nightly Rust for production server software. Is this something other people are doing?

And last, is this the right place to discuss, or should this be a separate issue?

[lilith]

I've seen a lot of push-back about whether Rust should offer graceful handling of malloc failure. A few points that recur:

• If any malloc fails, there's no hope of recovery anyway. - This is false, as delayed or smaller mallocs are likely to succeed. Malloc failure can be temporary, and is typically (in most allocators) specific to the size of the block requested. Anything involving a work queue can deal gracefully with this by reducing the number of concurrent workers or skipping the task. Simply retrying a few hundred milliseconds later may resolve the problem. On some operating systems, fragmentation causes large malloc failure at below 50% utilization. Imperfect implementations of virtual memory (and allocators!) make the fundamental reasoning behind this myth quite useless. TLDR; Common predictions of future behavior of malloc are unlikely to correspond with reality.
• Overcommit is enabled by default on most linux distros, so malloc failure is delayed till memory access anyway - This myth stems from a misunderstanding of overcommit 0. An overcommit heuristic is enabled. Failure may be delayed, but is only likely to occur when the heuristic fails. The default behavior reduces swap usage. It does that by failing mallocs, but using a less detailed method of accounting. TLDR; "overcommit enabled"="overcommit fractionally more likely"
• C developers don't bother handling malloc; Rust developers shouldn't be expected to, either. - Despite the ease of comprehensively testing software for graceful malloc failure handling (swap out malloc fn ptr, iterate failure on nth and later calls, or fuzz failures), this remains a prevalent perception. I've performed this kind of testing against many C libraries with great results; malloc failure is nearly always handled gracefully. This may be uncommon in applications, but correct malloc handling is quite common in the embedded, library, systems, and server space, which appears to be where Rust is targeted. Graceful malloc failure handling has also been witnessed in many mobile apps. It would appear that a lot of C/C++/Java/C#/Swift/etc developers are putting effort into this, and many are succeeding. TLDR; Relative justifications of laziness unfounded after actual inspection.

And a few recurring points about panic-on-OOM specifically:

• Unwinding may allocate, causing undefined behavior if OOM panics - Double panic aborts, so this concern is unfounded.
• Crate authors assume OOM never panics, but always aborts - This is already an invalid assumption - OOM can panic [Update: but only in the case of capactiy overflows?], although most often it aborts. Of the discussions I've read, most involve at least one person being very surprised by a (primarily) abort behavior, having assumed a recoverable behavior as is present in many other languages. Perhaps a poll could measure which behavior (panic vs. abort) is less surprising?
• Recoverable OOM could fragment the ecosystem - I don't have specifics about how this might occur, but I would imagine a scenario where catch_panic is used without expectation that an OOM panic is possible. This concern has legs, but would support a strategy to make panic the default - process abort is always going to work, but increasing the scenarios in which OOM panics might trigger unexpected code paths. So #![feature(abort_on_oom)] couldn't cause unexpected behavior (only absence of behavior), while #![feature(panic_on_oom)] could cause unexpected behavior in an improperly used catch_panic. Rust seems to favor more conservative/forwards-compatible approaches, so abort_on_oom as opt-in would seem to be consistent with that philosophy.

I have not yet found any sound arguments as to why OOM should not panic by default (vs. current behavior - panic sometimes, but usually abort).

Perhaps I should write a rust app that demonstrates how malloc failure isn't what people expect, and link to it here.

[lilith]

I am concerned that as catch_panic was stabilized a few weeks ago, crates may start using it with false assumptions about panic vs. abort on OOM (currently either can occur, which is actually a good thing - they cannot correctly assume OOM exclusively aborts, although the docs aren't clear about this).

As code paths dependent upon this may start appearing, the likelihood of breakage decreases the earlier OOM behavior is changed (or clearly documented to be changing, or documented as changeable).

To present a couple strawmen that, through simplicity, might be faster to stabilize:

Opt-in to Panic

#![feature(panic_on_oom)] - a subset of #![feature(oom)]

• Causes OOM to attempt a panic instead of abort, and defines the panic value for catch_panic users.
• Double panics still abort.
• Will be overridden by #![feature(oom)]
• Has no corresponding API methods.
• As a stable feature, will be referenced in catch_panic and other relevant documentation, to encourage crate authors to support the behavior, for those (potentially theoretical?) crates who depend on certain behavior from catch_panic.

Out-out of panic

#![feature(abort_on_oom)] - a subset of #![feature(oom)]

• Causes an abort in all OOM scenarios
• Otherwise same as above.

Would either of these be easier to fast-track for stabilization (compared to stabilizing alloc or oom)?

EDIT: Is there concern that libstd may not be robust in the face of panic-on-OOM due to unsafe bits with un-exercised OOM failure states? If so, perhaps this could be opened as an issue for me to work on? With custom allocators this can be pretty straightforward to test.

[arielb1]

@nathanaeljones

OOM always aborts. It's only capacity overflows that panic, which Vec is required to handle correctly. Other collections may not be as careful.

For example, BTreeMap does not guard its allocations with a capacity overflow, and is a fairly complicated bit of code.

[Amanieu]

@nathanaeljones

As the person who implemented set_oom_handler, I'd like to provided a bit of background about why this function was added. Previously, running out of memory would result in a call to instrinsics::abort, which is an undefined instruction and causes the process to crash with an "Illegal instruction" message.

Since this behavior was confusing many people, I added this function, which is used by libstd to set an OOM handler that prints "Out of memory" to standard error before calling libc::abort, which crashes the process with an "Abort" message.

This functionality couldn't have been put into liballoc directly since that crate is used in bare metal systems and kernels which don't have a standard error to print to and don't have an abort function to call. So the default behavior is to call intrinsics::abort while allowing it to be overridden by a more user-friendly OOM handler.

TLDR: set_oom_handler was never meant to be used by applications, it is just a way for libstd to print a nicer error message on OOM.

[Amanieu]

@nathanaeljones

Regarding your proposal of panicking on OOM, the biggest issue I can see is that unsafe code may leave inconsistent state if a panic occurs where it does not expect one. This inconsistent state could result in memory unsafety and could even be used by exploits that can trigger OOM conditions.

[lilith]

@Amanieu The first step to either improving robust OOM-panic handling in libstd or creating replacement APIs is to identify which APIs perform allocations. Is there an automated way to do this? I would love to see such APIs flagged in documentation, although a simple list would suffice. Is there already a compiler plugin for this?

For APIs whose state is contained in a single region of memory, my default testing approach would be to employ a custom allocator to exhaustively force *alloc failures, while requiring that post-panic state involves a bit-for-bit match with the original. I would hope those writing unsafe code in libstd put allocations as early as possible.

Also, thank you for explaining the motivation behind set_oom_handler

[tiffany352]

I'd like for the OOM API to be stabilized in some form. I currently have a sandboxed process which performs calculations on bignums, and OOMs frequently result. Because there is no stabilized API for reporting and handling OOM failures, I have to assume that all aborts are OOMs, which is not always the case. I don't need to be able to recover from an OOM failure - I just need to signal to the parent process that it was an OOM and not some other crash.

[YorickPeterse]

Perhaps this is not the right place to ask, but what's the progress on the alloc library, and alloc::heap in particular? I'm currently working on a programming language and the only hard reason this requires nightly is the use of alloc::heap as I have to allocate memory with a specific alignment.

[aturon]

Nominating for libs team discussion.

[YorickPeterse]

In my previous comment I mentioned I was using alloc::heap but I didn't show any code. If it's of any use, the code can be found here: https://github.com/YorickPeterse/inko/blob/4e81de458af096dff47f29ce9aff47900becb14d/vm/src/immix/block.rs#L118

[SimonSapin]

It’s already possible to indirectly use allocate and deallocate in stable Rust

There’s even a crate for it: https://crates.io/crates/memalloc

[SimonSapin]

Proposal:

Edit: removed drive-by changes per discussion below.

• Make allocate reallocate and reallocate_inplace return Result to indicate errors in a more idiomatic way. Details of the error type(s) to be determined
• Return Err(_) rather than invoke undefined behavior for zero size or non-power-of-two alignment
• Make allocate not unsafe
• Reexport alloc::heap as std::heap
• Stabilize std::heap and its content
• Leave the alloc crate unstable, tracked in #27783
• Leave the oom module unstable, file a new tracking issue for it.
  • Details of a settable OOM handler (including whether it should be settable at all) can be left to a future RFC.
  • In the meantime, std::process::abort is an appropriate OOM handler. (Is it? The current default OOM handler is core::intrinsics::abort. How are they different? Do the differences matter?)

@aturon how does this sound?

[SimonSapin]

And of course, before stabilizing:

• Document for each unsafe function exactly what invariants callers need to maintain.

[Gankro]

If we insist on building more ergonomic APIs, I think we should expose the current ones as-is, suffixed with _raw or something. Just so there's absolutely zero blocker on getting them out, and everyone knows they're using the kinda janky "look it works" one.

[SimonSapin]

I proposed small changes in passing because that seemed an easy improvement, but I’m not particularly attached to them. And I don’t think they’re worth doubling the API surface. @Gankro What’s the value of the _raw functions if the other ones are only slightly different?

[Gankro]

There is little to know value; I've just seen this API get punted from stabilization time and time again over hemming and hawing over potential improvements, when everyone just needs some way to allocate with a given size and alignment. So basically I'm desperate to do anything it takes to get this landed. I had already been planning to suggest this rename precisely to get them "out of the way" of premium name real-estate.

I personally don't think our lowest level allocation functions should provide any help or do anything on top of the system allocator. This is a critical code path. We should definitely provide higher level abstractions that do the sorts of things you suggest, but the API as it exists should be preserved and pushed out ASAP.

[SimonSapin]

Sounds fair enough. I’ve edited my "proposal" message above to skip the changes.

I don’t have an opinion on the rename.

[aturon]

Discussed briefly in the libs meeting today; I proposed that we need to get all of the allocator stakeholders together to discuss our plan (in light of @sfackler's RFC, etc).

The goal would be to lay out a definite plan of action for incremental stabilization of pieces of the allocator system, trying to get something stable ASAP.

If you'd like to take part in this discussion, please leave a comment and I'll be in touch.

[YorickPeterse]

@aturon I'm happy to share any feedback/thoughts/grumpy remarks/etc.

[Gankro]

I'd like to be involved.

[alexcrichton]

Ok! We've now had a chance to get many of the stakeholders together and chat about the current state of affairs. Action items coming out of this moot:

• Everyone's on board with rust-lang/rfcs#1974, comfortable merging and implementing.
• The std::heap API is poposed in rust-lang/rfcs#1974 and can likely be stabilized far ahead of the "swap the global allocator" logic proposed in the RFC.
• At that point we'll probably close this issue, as the relevant high-impact pieces will be stable.
• Custom local allocators are covered by #32838, in addition to custom allocators in collections, I'll leave a comment over there.

So with that in mind hopefully we can aim to start closing out this issue soon!

[rolandsteiner]

[I hope this is the right place to ask]

Playing around with aligned allocation using alloc::heap::allocate, I noticed that usable_size() does not steadily increase by a factor of 2 with increasing requests, but instead jumps in reported (effectively allocated?) storage after 2K directly to 16K.
That is, when requesting an allocation just larger than 2K, usable_size() will report 16K, even if 4K or 8K would have sufficed. Is this known or expected?

Playground: https://is.gd/HGhRYR

[ssokolow]

@rolandsteiner Have you tried requesting the system allocator to see if that behaviour changes?

...because I know jemalloc rounds allocations up as part of its approach for combatting memory fragmentation in long-running programs.

EDIT: Yep. I just tried adding alloc_system to your example and now the allocations match the requests. https://is.gd/ce43nS

You'll have to ask the jemalloc devs what rationale they used to decide against having a 4K or 8K arena.

[rolandsteiner]

@ssokolow Thanks for the follow-up! I was mainly puzzled because this behavior is only triggered by the requested alignment, not size (i.e., a 4K or 8K request on a 2K alignment returns a 4K/8K block just fine).

This means, one cannot naively request a single 4K page. But perhaps the playground server runs on a different architecture that uses 16K pages (?).

[alexcrichton]

Upon review of the allocator-related tracking issues we actually have quite a lot now! I'm going to close this in favor of #32838 as the stabilization of the std::heap module is now quite likely to use those traits.

I'll be copying over some of the points at the top of this tracking issue to that issue as well.