Tracking issue for allocation APIs

@ruuda

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.

@pnkfelix

cc @pnkfelix

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.

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<(), ()> { /* ... */ }
}

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

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

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

@SimonSapin

@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 :-)

@kamalmarhubi

@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.)

@pnkfelix

@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...

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

@glandium

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:

Re-implementation of all allocating functions I encounter. Is this list actually exhaustive, or only for collections?
Looking for actionable work I can perform to accelerate stabilization of set_oom_handler. What would be most helpful?
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?

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.

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.

@nathanaeljones

@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.

And of course, before stabilizing:

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

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.

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?

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.

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

I don’t have an opinion on the rename.

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.

@aturon

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

I'd like to be involved.

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 Prepare global allocators for stabilization rfcs#1974, comfortable merging and implementing.
The std::heap API is poposed in Prepare global allocators for stabilization 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 Allocator traits and std::heap #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!

[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

@rolandsteiner

@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.

@ssokolow

@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 (?).

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.

Navigation Menu

Tracking issue for allocation APIs #27700

Current status

Original report

Opt-in to Panic

Out-out of panic

10 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Tracking issue for allocation APIs #27700

Description

Current status

Original report

Activity

alexcrichton commented on Aug 13, 2015

SimonSapin commented on Jan 5, 2016

SimonSapin commented on Jan 5, 2016

kamalmarhubi commented on Mar 17, 2016

SimonSapin commented on Mar 17, 2016

kamalmarhubi commented on Mar 18, 2016

pnkfelix commented on Mar 18, 2016

kamalmarhubi commented on Mar 18, 2016

glaebhoerl commented on Mar 19, 2016

lilith commented on Aug 29, 2016

lilith commented on Sep 2, 2016

lilith commented on Sep 2, 2016

Opt-in to Panic

Out-out of panic

arielb1 commented on Sep 4, 2016

10 remaining items

SimonSapin commented on Mar 29, 2017

Gankra commented on Mar 29, 2017

SimonSapin commented on Mar 30, 2017

Gankra commented on Mar 30, 2017

SimonSapin commented on Mar 30, 2017

aturon commented on Apr 25, 2017

yorickpeterse commented on Apr 25, 2017

Gankra commented on Apr 27, 2017

alexcrichton commented on May 19, 2017

rolandsteiner commented on Jun 19, 2017

ssokolow commented on Jun 19, 2017

rolandsteiner commented on Jun 20, 2017

alexcrichton commented on Jun 20, 2017

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions