Tracking issue for the GlobalAlloc trait and related APIs

[SimonSapin]

PR #49669 adds a GlobalAlloc trait, separate from Alloc. This issue track the stabilization of this trait and some related APIs, to provide the ability to change the global allocator, as well as allocating memory without abusing Vec::with_capacity + mem::forget.

Defined in or reexported from the std::alloc module:

Update: below is the API proposed when this issue was first opened. The one being stabilized is at #49668 (comment).

/// #[global_allocator] can only be applied to a `static` item that implements this trait
pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut Opaque;
    unsafe fn dealloc(&self, ptr: *mut Opaque, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut Opaque { 
        // Default impl: self.alloc() and ptr::write_bytes()
    }
    unsafe fn realloc(&self, ptr: *mut Opaque, layout: Layout, new_size: usize) -> *mut Opaque {
        // Default impl: self.alloc() and ptr::copy_nonoverlapping() and self.dealloc()
    }
    
    // More methods with default impls may be added in the future
}

extern {
    pub type Opaque;
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct Layout { /* private */ }

impl Layout {
    pub fn from_size_align(size: usize: align: usize) -> Result<Self, LayoutError> {…}
    pub unsafe fn from_size_align_unchecked(size: usize: align: usize) -> Self {…}
    pub fn size(&self) -> usize {…}
    pub fn align(&self) -> usize {…}
    pub fn new<T>() -> Self {…}
    pub fn for_value<T: ?Sized>(t: &T) -> Self {…}
}

#[derive(Copy, Clone, Debug)]
pub struct LayoutError { /* private */ }

/// Forwards method calls to the `static` item registered
/// with `#[global_allocator]` if any, or the operating system’s default.
pub struct Global;

/// The operating system’s default allocator.
pub struct System;

impl GlobalAlloc for Global {…}
impl GlobalAlloc for System {…}

CC @rust-lang/libs, @glandium

Unresolved questions or otherwise blocking

• Wait for extern types Tracking issue for RFC 1861: Extern types #43467 to be stable in the language before stabilazing one in the standard library.
• Name of the Global type. GlobalAllocator?
• Name of the Void type. Lower-case void would match C (our *mut void is very close to C’s void* type), but violates the convension of camel-case for non-primitive types. But Void in camel-case is already the name of an empty enum (not an extern type like here) in a popular crate. (An extern type is desirable so that <*mut _>::offset cannot be called without first casting to another pointer type.) Maybe call it Opaque? Unknown? Renamed to Opaque.
  • Rename again to something else?
• Taking Layout by reference, or making it Copy Alloc methods should take layout by reference #48458. Copy: Implement Copy for std::alloc::Layout #50109
• GlobalAlloc::owns: Alloc: Add owns method #44302 proposes making it required for allocators to be able to tell if it “owns” a given pointer. Not to be required by this trait since glibc and Windows do not support this.
• Settle semantics of layout "fit" and other safety conditions. Without an usable_size method (for now), the layout passed to dealloc must be the same as was passed to alloc. (Same as with Alloc::usable_size’s default impl returning (layout.size(), layout.size()).)
• An oom method is part of GlobalAlloc so that implementation-specific printing to stderr does not need to be part of liballoc and instead goes through #[global_allocator], but this does not really belong in the GlobalAlloc trait. Should another mechanism like #[global_allocator] be added to have pluggable OOM handling? Replace {Alloc,GlobalAlloc}::oom with a lang item. #50144

Not proposed (yet) for stabilization

• The Alloc trait
• The rest of Layout methods
• The AllocErr type

We’re not ready to settle on a design for collections generic over the allocation type. Discussion of this use case should continue on the tracking issue for the Alloc trait: #32838.

[euclio]

I was initially confused by the name Void. I confused it with the aforementioned empty enum. Bikeshed: I wonder if it could be called Allocation or Memory?

[glandium]

Relevant discussions pre-PR:

• about Void:
  0497b5e#r28405553
• about Global:
  c32a3de#commitcomment-28405600

[glandium]

But I don’t know if any platform’s system allocator (like libc’s malloc) supports this, let alone all of them.

The OSX system allocator supports that. Jemalloc does too, optionally. Glibc malloc and Windows heap allocator don't.

[Amanieu]

Taking Layout by reference, or making it Copy #48458

The fact that realloc now takes the new size as usize rather than a Layout strongly points towards just making Layout implement Copy and treating it as a simple (length, alignment) pair.

[alexreg]

Has the Heap type been renamed to Global?

[SimonSapin]

@alexreg Yes, as described in the PR message of #49669.

[RalfJung]

Naming bikesheds:

Given that the attribute is global_allocator, should the trait be called GlobalAllocator instead? alloc vs. allocator is inconsistent.

Also, I am not very happy with Void. void is probably the most misunderstood type in C. It is often described as "empty", but it actually is a unit type (), not the empty never type !. void* is NOT just a pointer to () though, but an independent concept. I'd rather we do not step into the middle of this confusion.
From the alternatives proposed above, I prefer Unknown. Some more random suggestions: Blob, Extern, Data. I think from all of these, my personal favorite is Blob, which I have often seen used as a term for "not further specified binary data". But really, any of these is strictly better than Void IMHO.

[SimonSapin]

If GlobalAlloc is renamed to GlobalAllocator, should Alloc be Allocator? And the alloc method allocate? (And similarly other methods.)

Agreed that Void or void is probably best avoided, though I’m not sure what to pick instead.

[alexcrichton]

I would personally keep the name "alloc" for traits and methods, the global_allocator is talking about a specific instance whereas the methods/traits are actions/groups of types.

std::alloc::Global could also be something like GlobalHeap (I think suggested by @glandium?) or DefaultHeap or DefaultAlloc. I don't think we can choose the name GlobalAlloc without renaming the trait GlobalAlloc itself.

I don't think we should implement owns. The sheer fact that two tier-1 platforms don't implement it I feel like is a nail in that coffin.

[fitzgen]

The GlobalAlloc trait should require Sync as a super trait, no?

[sfackler]

Yeah, Send as well.

[Amanieu]

I don't think Send is actually necessary. A GlobalAlloc is never dropped and does not require a &mut.

My rule of thumb for Send is: "is it OK to drop this type in a different thread than the one it was created in?"

[alexcrichton]

@fitzgen @sfackler I don't think either trait is necessarily required per se though, inherently sticking it into a static will require both traits for sure. I think the main benefit may be being informative early on, but we've tended to shy away from those types of trait bounds.

[SimonSapin]

As Alex said, Sync is already required by static items which are the only ones where #[global_allocator] can be used.

[RalfJung]

@alexcrichton

sticking it into a static will require both traits for sure.

That should only require Sync, as @SimonSapin said, but not Send, right? Only &T is shared across threads.

[kornelski]

from_size_align_unchecked is not an unsafe method? Are there any invariants that Layout upholds?

Why Void and not fn alloc<T>() -> *mut T?

[SimonSapin]

from_size_align_unchecked is unsafe, that was a mistake. See https://doc.rust-lang.org/nightly/core/heap/struct.Layout.html#method.from_size_align for invariants.

alloc_one<T>() is a convenience method on top of alloc(Layout), you can’t always statically construct a type that has the desired layout.

[retep998]

Every time I see this trait name I get it confused with GlobalAlloc the Windows API function: https://msdn.microsoft.com/en-us/library/windows/desktop/aa366574

[SimonSapin]

@retep998 What do you think would be a better name for the trait?

[alexreg]

[Reposting in the right tracking issue this time...]

So, the name currently decided on by @SimonSapin for the allocated memory type seems to be Opaque. I concur that Void is a dubious name, but I don't think Opaque is great, mainly due to its complete lack of descriptiveness. I propose one of the following:

• Blob
• Mem
• MemBlob
• MemChunk
• OpaqueMem – not my favourite, but at least slightly more explicit than just Opaque
  I'd probably lean towards Mem, since it's the most pithy, but the others are okay too.

[Amanieu]

I would add Raw to the list, since allocation returns raw untyped memory.

[alexreg]

RawMem would work too, yeah. Just Raw is too vague though.

[sfackler]

The impl GlobalAlloc for Global is a bit icky, I agree. One of the alternatives we discussed at the all hands is free functions for alloc/dealloc/realloc in std::heap. They'll end up deprecated either way, but it does avoid a kind of confusing trait impl, as well as having a type that implements two traits with methods of the same names.

[Amanieu]

I'm OK with global functions, with the understanding that they will be deprecated once Alloc is stabilized.

[SimonSapin]

I’ve previously argued that if we have a set of free functions that have the exact same signature as a trait, they might as well be a trait impl. But it is a good point that functions would be easier to deprecate, so I’m fine with that as well.

[gnzlbg]

Right now we can't deprecate trait impls AFAIK: #39935

[gnzlbg]

@Amanieu

For zero-sized allocations, I would like to point to some prior art in C++'s operator new:

If this argument is zero, the function still returns a distinct non-null pointer on success (although dereferencing this pointer leads to undefined behavior).

In practice (in both Clang/libc++ and GCC/libstdc++) this is implemented as a quick check that changes the size to 1 if it is zero.

AFAICT this is not exactly how it is implemented in neither libc++ [0] nor libstdc++ [1]. When a size of zero is requested, the size is as you mention changed to one, but then, a real memory allocation for this new size is performed with the requested alignment, and a unique pointer to the address is returned.

That is, for allocations of zero size, C++ calls the system allocator, potentially performing a context switch to the kernel, etc.

I believe that the overhead in this is sufficiently low since nobody in C++-land is complaining about it.

C++ does not have zero-sized types: all types are at least 1 byte in size. For example, if you create an array of length zero of an empty type struct A{}; auto a = new A[0];, that array still has sizeof(A[0]) == 1, so the raw allocation functions will not be called with size == 0. In fact, I think triggering a call to new(size = 0) is actually really hard unless one starts writing very weird C++ code, and probably impossible if one writes modern C++.

If your language does not have a concept of zero-sized types, zero-sized allocations do not really make much sense, and I argue that the real reason nobody is complaining about these is because nobody is triggering calls to new(size = 0) in C++ yet in such a way that the answer isn't "don't write that code, it's horrible".

Many C++ developers have, however, complained about the lack of zero-sized types in the language, and ZST are already part of the C++20 standard and opt-in in some situations, but none that could trigger new(size = 0) AFAICT. Basically, empty types can opt-in to becoming zero-sized when used within other types only.

I think a better example than C++ new would be C malloc, which people do have to manually pass a size argument all the time. The C11 standard says (7.20.3 Memory management functions):

If the size of the space requested is zero, the behavior is implementation defined: either a null pointer is returned, or the behavior is as if the size were some nonzero value, except that the returned pointer shall not be used to access an object.

Which if the implementation decides to return something different than null means:

The pointer returned if the allocation succeeds is suitably aligned [...]. The lifetime of an allocated object extends from the allocation until the deallocation. The pointer returned points to the start (lowest byte address) of the allocated space. Each such allocation shall yield a pointer to an object disjoint from any other object.

So AFAICT for zero-sized allocations a compliant C11 implementation returns a pointer that cannot be dereferenced but can be freed. There are no requirements on the pointers to be unique. Since NULL can be freed without issues (its a no-op), it can return the same address for all zero-sized allocations, or some other address, or a unique address for each like C++ does.

There is a potentially interesting presentation about the topic [2] discussing it in the context of security vulnerabilities, but these probably don't apply to Rust and I haven't gone through it all yet.

[0] https://github.com/llvm-mirror/libcxx/blob/master/src/new.cpp#L71
[1] https://github.com/gcc-mirror/gcc/blob/da8dff89fa9398f04b107e388cb706517ced9505/libstdc%2B%2B-v3/libsupc%2B%2B/new_opa.cc#L95
[2] Automated vulnerability analysis of zero sized heap allocations - Julien Vanegue - Microsoft Security Engineering Center (MSEC) Penetration testing team: http://www.hackitoergosum.org/2010/HES2010-jvanegue-Zero-Allocations.pdf

[Amanieu]

I believe that the overhead in this is sufficiently low since nobody in C++-land is complaining about it.

I would like to clarify that the point I'm trying to make: The overhead of the extra zero-check in the common case (non-zero length allocation) is tiny to the point of being irrelevant. As such, we should aim to provide an API with fewer footguns, especially considering that ZSTs are much more common in Rust.

By the way, I would like to add another data point for how allocation APIs handle zero sizes. jemalloc's internal API (je_mallocx, which we use instead of je_malloc in Rust's jemalloc wrapper) has undefined behavior if a size of zero is passed [1]

[1] http://jemalloc.net/jemalloc.3.html

The mallocx() function allocates at least size bytes of memory, and returns a pointer to the base address of the allocation. Behavior is undefined if size is 0.

[SimonSapin]

The libs team discussed this thread today today and consensus was to:

• Stick with the status quo for zero-size allocations: alloc() is an unsafe fn and callers must ensure that the layout is not zero-size. We felt that making this method safe is not a significant win since the kind of code calling it needs typically needs unsafe anyway (for dereferencing the returned pointer or of deallocating), and didn’t feel confident relying on (Thin)LTO and Sufficiently Advanced optimizers to not regress performance

• Also keep raw pointers in GlobalAlloc rather than results. Rationale: Changes to GlobalAlloc #51160 (comment)

• Remove the Opaque type entirely and use pointers to u8. If we’re not waiting on extern types, an dedicated struct does not buy us much over u8. And not having a new type avoids entirely questions of its name or what traits it should implement.

• Replace impl GlobalAlloc for Global with a set of free functions

• Finally stabilize this subset (after modifications listed above) of the API:

/// #[global_allocator] can only be applied to a `static` item that implements this trait
pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut u8;
    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { 
        // Default impl: self.alloc() and ptr::write_bytes()
    }
    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
        // Default impl: self.alloc() and ptr::copy_nonoverlapping() and self.dealloc()
    }
    
    // More methods with default impls may be added in the future
}

#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub struct Layout { /* private */ }

impl Layout {
    pub fn from_size_align(size: usize: align: usize) -> Result<Self, LayoutError> {…}
    pub unsafe fn from_size_align_unchecked(size: usize: align: usize) -> Self {…}
    pub fn size(&self) -> usize {…}
    pub fn align(&self) -> usize {…}
    pub fn new<T>() -> Self {…}
    pub fn for_value<T: ?Sized>(t: &T) -> Self {…}
}

#[derive(Copy, Clone, Debug)]
pub struct LayoutError { /* private */ }

/// Forwards to the `static` item registered
/// with `#[global_allocator]` if any, or the operating system’s default.
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {…}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {…}
unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {…}
unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {…}

/// The operating system’s default allocator.
pub struct System;

impl GlobalAlloc for System {…}

Update: also:

pub fn oom(layout: Layout) -> ! {…}

[gnzlbg]

The C99 Rationale V5.10 document has rationale on why malloc supports zero-sized allocation (section 7.20):

The treatment of null pointers and zero-length allocation requests in the definition of these
functions was in part guided by a desire to support this paradigm:

OBJ * p; // pointer to a variable list of OBJs
/* initial allocation */
p = (OBJ *) calloc(0, sizeof(OBJ));
 /* ... */
/* reallocations until size settles */
while(1) {
p = (OBJ *) realloc((void *)p, c * sizeof(OBJ));
/* change value of c or break out of loop */
}

This coding style, not necessarily endorsed by the Committee, is reported to be in widespread use.

Some implementations have returned non-null values for allocation requests of zero bytes. Although this strategy has the theoretical advantage of distinguishing between “nothing” and “zero” (an unallocated pointer vs. a pointer to zero-length space), it has the more compelling theoretical disadvantage of requiring the concept of a zero-length object. Since such objects cannot be declared, the only way they could come into existence would be through such allocation requests.

The C89 Committee decided not to accept the idea of zero-length objects. The allocation functions may therefore return a null pointer for an allocation request of zero bytes

It is not 100% clear to me what this rationale means, but it appears to mean that they decided to allow malloc(0) because, since C does not have ZSTs, too many people were emulating them with malloc(0) in the wild before standardization.

---

About C++, I've asked on stackoverflow, and s Bo Persson pointed to C++'s standard 9th defect report:

Scott Meyers, in a comp.std.c++ posting: I just noticed that section 3.7.3.1 of CD2 seems to allow for the possibility that all calls to operator new(0) yield the same pointer, an implementation technique specifically prohibited by ARM 5.3.3. Was this prohibition really lifted? [...]

Proposed resolution:

[...]

Change 3.7.3.1/2, next-to-last sentence, from :

If the size of the space requested is zero, the value returned shall not be a null pointer value (4.10).

to:

Even if the size of the space requested is zero, the request can fail. If the request succeeds, the value returned shall be a non-null pointer value (4.10) p0 different from any previously returned value p1, unless that value p1 was since passed to an operator delete.

[...]

Rationale:

So it seems that in the original draft new(0) could return any non-zero pointer, including the same one for different allocations, but "ARM 5.3.3 specifically prohibited it" (no rationale given) so they changed it to the current wording. The relevant section of the C++ standard has a footnote saying that the intent of new is to be implementable by a call to malloc modulo the zero size exception.

[gnzlbg]

@SimonSapin

If the Layout used to call alloc cannot have zero-size, what did the libs team give as rationale for
allowing Layouts of zero size in the first place?

[SimonSapin]

@gnzlbg The use case of intermediate possibly-zero-size Layouts being used to build larger Layouts given earlier in this thread #49668 (comment) sounds reasonable to me. Having a separate LayoutBuilder API seems like a lot just to allow alloc() to be safe (given that callers typically need some unsafe code anyway).

[gnzlbg]

@SimonSapin

• Is alloc allowed to return a null ptr, if so, what does that mean?

Basically, the trait API looks ok, but what is missing there is the comments expressing the function requirements, semantics, and guarantees.

[SimonSapin]

Right, this still needs lots of docs to write out the API contracts. Returning null indicates an error or failure. Maybe the OS is out of memory, maybe the given Layout is not supported at all by this allocator (e.g. align overflowing u32 on macOS’s System allocator)

Calling alloc with a zero-size layout is undefined behavior, a violation of the unsafe fn contract. Meaning: impls are allowed to do anything in that case, including returning null.

[alexcrichton]

Thanks for typing this up @SimonSapin! That all looks accurate and good to me

[Amanieu]

I'm not too happy with the lack of Result and not handling zero-sized allocations, but I can accept it with the knowledge that we still have a chance to revise the API later on with the Alloc trait. However we should make it clear (as I discussed with @SimonSapin at Rustfest) that the free alloc::alloc() functions will be deprecated as soon as Alloc is stabilized, in favour of Global.alloc().

As a side note, should we add a global_ prefix to the free functions? A bare alloc might be confusing in a module full of allocation-related definitions (e.g. Alloc which differs only by casing). However this is only a weak objection, I was just wondering if the option had been discussed in the libs team meeting.

[sfackler]

I don't think a global_ prefix is all that necessary. It's a free function so it has to be talking to the global allocator, right? There aren't any other options.

[SimonSapin]

Or a global sub-module? So the full path might be std::alloc::global::alloc()

[SimonSapin]

Stabilization PR: #51241 (finally!)