Ban zero-sized allocations

[TimDiekmann]

From rust-lang/rust#32838 (comment):

For me, an important constraint is that if we ban zero-sized allocations, the Alloc methods should be able to assume that the Layout passed to them is not zero-sized.

There are multiple ways to achieve this. One would be to add another Safety clause to all Alloc methods stating that if the Layout is zero-sized the behavior is undefined.

Alternatively, we could ban zero-sized Layouts, then Alloc doesn't need to say anything about zero-sized allocations since these cannot safely happen, but doing that would have some downsides.

For example, , some types like HashMap build up the Layout from multiple Layouts, and while the final Layout might not be zero-sized, the intermediate ones might be (e.g. in HashSet). So these types would need to use "something else" (e.g. a LayoutBuilder type) to build up their final Layouts, and pay for a "non-zero-sized" check (or use an _unchecked) method when converting to Layout.

Making Layout only accept non-zero size is not possible anymore as it's stable. But banning zero-size allocation would simplify the safety clause on Alloc.

This would also unlock to move helper methods to an extension trait.

This change could easily be reverted in the future if actual use cases appear. Currently I don't see any, because we cannot rely on an implementation to allow zero-sized allocations, thus we have to check size_of::<T>() == 0 in any way.

[gnzlbg]

If we do this, it might make sense to change the types that Alloc takes from Layout to something else, e.g., NonZeroLayout or similar, and provide checked and unchecked conversions from/to Layout for that type.

That would basically turn Layout into the "LayoutBuilder" that I was talking about in the original post.

[TimDiekmann]

cc rust-lang/rust#63291

[Lokathor]

I don't understand why zero sized allocations are banned if the output is a result anyway.

Can't an allocator that disallows zero sized allocation just return an err if given a zero sized layout?

[petertodd]

How about adding a SizedLayout, and changing the API to have alloc() and alloc_sized()? The former can then have a default implementation that returns a ptr set to the alignment if size == 0.

While most allocators have no reason to deal with ZST's, a minority will want to intercept such allocations. Equally, for most code it's must easier if the allocator API can handle ZST's and treat them like any other type. So I think a default implementation that works for 99% of use-cases will save everyone some work.

[petertodd]

(feel free to bikeshed the name; SizedLayout isn't quite the right term here)

[Amanieu]

My personal preference is to always require allocators to support zero-sized allocations, which keeps things simple. Some allocators such as bumpalo don't need any special work to support this, while others can simply cast the alignment to a pointer and return that if the size is zero.

[TimDiekmann]

Shall we introduce a NonZeroLayout and use this in the alloc trait(s)?

Currently, zeroed allocation is pretty error prone and even experienced users may miss this: rust-lang/rust#63291 (comment). On the other hand, we would restrict implementations which are fine to get zeroed layout like a bump allocator.

	ban zero-sized allocation	close
@Amanieu		👎
@Ericson2314
@glandium
@gnzlbg
@Lokathor		👎
@scottjmaddox		😕
@TimDiekmann		👎
@Wodann

Please vote with

• 👍 ban zero-sized allocation
• 👎 close

[Wodann]

Disclaimer: I am just spitballing to get some feedback.

In general, Rust's philosophy is to provide safe, zero-cost abstractions; while also allowing unsafe behavior at the cost of some additional effort from the programmer. According to that philosophy, the basic behavior of an allocator should detect and prevent mistakes that are easily overlooked by the programmer.

Zero-sized allocations seem like an instance of the aforementioned, so it might be a good idea to create a special syntax for it.

[TimDiekmann]

I think this would be a good new issue if this proposal gets rejected. For methods like alloc_one and alloc_array it's possible at compile time to determine the size of the layout as long as the type is Sized. One way to get the best of both worlds, it may be possible to provide a small trait, which accepts a NonZeroLayout instead, so an allocator, which accepts a zeroed layout could implement both traits. This wouldn't necessarily to be implemented in liballoc.

Another way to solve this dilemma is to pass NonZeroLayout to AllocRef and lift the conditions on another trait.

I didn't test those approaches so far, these are only random thoughts, so take it with a grain of salt.

[scottjmaddox]

It's nonsensical to allocate a zero sized type. The AllocRef trait should not allow something nonsensical. It should be the lowest level cross-platform API to any allocator, including those that don't account for zero sized allocations.

It might make sense to add an extension trait with some sort of logic for handling zero sized allocations, but what should it do? Return a unique pointer for each allocation? Return a unique pointer for each distinct zero-sized layout? It's application specific.

[Amanieu]

Allocating a zero sized type is perfectly well defined. Each distinct memory address can contain an infinite number of ZSTs, so the allocator can just return any arbitrary address if the allocation size is zero. The only constraint is that ZSTs may have an alignment requirement (e.g. zero-length array), which is why the simplest way to handle them is to cast the alignment part of the Layout to a pointer and return that. This is a two-line change which is absolutely trivial to add.

[scottjmaddox]

That assumes you have nothing at those memory locations that you care about, which is a bad assumption on embedded devices. And, in my opinion, part of the goal of this working group should be to support allocation on embedded devices.

[Amanieu]

No, it literally doesn't matter what is at those memory locations because that memory is never accessed. Dereferencing a ZST doesn't actually access any memory.

[Amanieu]

Also keep in mind that it's perfectly fine for multiple ZSTs to share the same memory address.

[scottjmaddox]

I guess I just don't understand the semantics of ZSTs in Rust. What's the best place for me to read up on them?

[Amanieu]

https://doc.rust-lang.org/nomicon/vec-zsts.html seems to have a pretty good coverage of the topic. There's also https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts as a more general introduction to ZSTs.

[Lokathor]

There is not now, nor has there ever been, a reason to make zero-sized allocations UB. GlobalAlloc::alloc is simply a very poorly designed method, that we should not emulate the design of going forward.

[scottjmaddox]

Okay, thank you for the links. After reading them, I agree that the standard alloc method should accept and appropriately handle zero sized types, since there's a simple, sound approach to handling such a request.

That being said, I don't think we should require implementors to handle that case. So I propose providing a default impl for alloc that calls into a new "abstract" method alloc_nonzero_unchecked (modulo the name), which assumes a non-zero size. This would provide the same optimal performance, while exposing a clear and ZST-aware API.

[Lokathor]

If we did a split like that would the main alloc method then be marked safe? I don't want complexity for no reason, but if it lets us give the "normal" allocation path a safe route that'd be worth it.

Otherwise, I can't imagine it's any sort of performance penalty. If the size requested is zero you cast the alignment to a pointer and off you go. I don't think it's worth complicating the API for a single if statement. This isn't like slice indexing, you're not doing it multiple times per loop on the hot path.

[TimDiekmann]

@scottjmaddox Do I understand correctly you want to introduce at least two methods: alloc_nonzero and alloc_nonzero_unchecked? I'd omit the unchecked variant and make alloc_nonzero accept NonZeroLayout instead. Then it's up to the user to construct the NonZeroLayout.

@Lokathor The alloc(_zeroed) methods are only unsafe because it's undefined behavior, if a zeroed layout is passed to the methods. If we either explicitly allow to pass zeroed layouts or have a methods only accepting non-zeroed layouts, the unsafe can be removed (like I did in alloc-wg). In either case the realloc and dealloc methods remain unsafe, as the pointer must point to a location allocated by this allocator.

I think we should close this proposal and make a new one for the splitting things. With that proposal we may explicitly allow to pass zero to alloc and introduce another alloc_nonzero methods.
One thing I don't like about alloc_nonzero is that we should introduce something like alloc_zeroed_nonzero, so if someone would come up with a better name... 😕

[Lokathor]

alloc_nonempty
alloc_zeroed_nonempty

[petertodd]

Note how a default alloc impl for potentially zero sizes allocations needs a corresponding default impl in dealloc that does nothing.

…

On February 1, 2020 6:27:44 PM EST, Lokathor ***@***.***> wrote: an allocator should have sentinel values for ZST inputs, and _usually_ those sentinel values should be the alignment requested. Of course if you potentially allocate out of the first 16 bytes or whatever you'd have to pick some other sentinels. -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #16 (comment)

[TimDiekmann]

Note how a default alloc impl for potentially zero sizes allocations needs a corresponding default impl in dealloc that does nothing.

The trait is unsafe anyway so an implementor have to follow the safety guidelines on the traits in either case.

[TimDiekmann]

an allocator should have sentinel values for ZST inputs, and usually those sentinel values should be the alignment requested.

I think a sentinal value may be used as const value, as different allocators may have different sentinals. This sentinal value have to be checked in dealloc, if alloc isn't implemented. IMO this is fine.

[scottjmaddox]

Hmm... So supporting zero sized allocation requires an extra branch condition in alloc and an arbitrary number of extra branches (or maybe a jump table?) in dealloc to check for sentinel values... Sounds kind-of expensive. Maybe supporting zero-sized allocation isn't such a great idea...

[petertodd]

You don't need a sentinel. Just mark dealloc unsafe and do nothing if the size is zero. If the outer alloc is marked inline that'll be optimized out in most cases.

…

On February 1, 2020 6:39:35 PM EST, Scott J Maddox ***@***.***> wrote: Hmm... So supporting zero sized allocation requires an extra branch condition in `alloc` and an arbitrary number of extra branches (or maybe a jump table?) in `dealloc` to check for sentinel values... Sounds kind-of expensive. Maybe supporting zero-sized allocation isn't such a great idea... -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #16 (comment)

[petertodd]

(and actually, or course it's unsafe already)

…

On February 1, 2020 6:39:35 PM EST, Scott J Maddox ***@***.***> wrote: Hmm... So supporting zero sized allocation requires an extra branch condition in `alloc` and an arbitrary number of extra branches (or maybe a jump table?) in `dealloc` to check for sentinel values... Sounds kind-of expensive. Maybe supporting zero-sized allocation isn't such a great idea... -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #16 (comment)

[scottjmaddox]

Oh, right, I forgot the dealloc takes a Layout, too. Okay, so just an extra branch in alloc and in dealloc. Still not free, but as long as there's a way to bypass the branches, it should be fine.

[Wodann]

How would a default implementation behave, if the layout has a zeroed size?

The former. As dangling is generic over type T it becomes (source from bumpalo):

    #[inline(always)]
    unsafe fn alloc_zero_sized_type(&self, align: usize) -> NonNull<u8> {
        // We want to use NonNull::dangling here, but that function uses mem::align_of::<T>
        // internally. For our use-case we cannot call dangling::<T>, since we are not generic
        // over T; we only have access to the Layout of T. Instead we re-implement the
        // functionality here.
        //
        // See https://github.com/rust-lang/rust/blob/9966af3/src/libcore/ptr/non_null.rs#L70
        // for the reference implementation.
        let ptr = align as *mut u8;
        NonNull::new_unchecked(ptr)
    }

Note how a default alloc impl for potentially zero sizes allocations needs a corresponding default impl in dealloc that does nothing.

I forgot about dealloc needing to handle this case too (and by extension realloc probably too)

At this point you basically have a set of safe Sized trait functions and a set of non-Sized trait functions.

[Lokathor]

How often could you possibly be allocating that you need to worry about a single if.

Surely the rest of the allocator isn't branchless anyway.

[Wodann]

The way I see it alloc_zero_sized_type and alloc_sized are orthogonal in behaviour. They are completely separate cases of allocation that have no overlap. The choice to provide a shared alloc function is merely to provide a "usability" wrapper that allows people to specify a single entry-point for all of their allocation needs - that comes at the expense of performance.

As such I'd argue for something along the lines of:

trait AllocRef {
    fn alloc_sized(self, layout: NonZeroLayout) -> NonNull<u8>;

    /// Has default implementation
    #[inline(always)]
    unsafe fn alloc_zero_sized_type(self, align: usize) -> NonNull<u8> {
        // We want to use NonNull::dangling here, but that function uses mem::align_of::<T>
        // internally. For our use-case we cannot call dangling::<T>, since we are not generic
        // over T; we only have access to the Layout of T. Instead we re-implement the
        // functionality here.
        //
        // See https://github.com/rust-lang/rust/blob/9966af3/src/libcore/ptr/non_null.rs#L70
        // for the reference implementation.
        let ptr = align as *mut u8;
        NonNull::new_unchecked(ptr)
    }

    unsafe fn alloc(self, layout: Layout) -> NonNull<u8> {
        if layout.size() == 0 {
            self.alloc_zero_sized_type(layout.align())
        } else {
            self.alloc_sized(NonZeroLayout::from_layout_unchecked(layout))
        }
    }

Devs can choose the performant route; implementing and calling alloc_sized andalloc_zero_sized_type directly, or using alloc if they don't care about bare metal performance.

[Wodann]

Surely the rest of the allocator isn't branchless anyway.

Optimization in a hot code path (such as an allocator) means everything. Branching is a big part of that. E.g. https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html

[scottjmaddox]

How often could you possibly be allocating that you need to worry about a single if.

Surely the rest of the allocator isn't branchless anyway.

Bump allocators only need a few (very fast) integer ops and a branch to check if there's enough memory available. An extra branch would be significant.

[TimDiekmann]

@Wodann I think your approach is matured enough to be summed up as a proposal. Do you want to make one and file a new issue? While I don't like to have too many functions in AllocRef, those absolutely makes sense to me.

[JelteF]

Surely the rest of the allocator isn't branchless anyway.

Optimization in a hot code path (such as an allocator) means everything. Branching is a big part of that. E.g. https://fitzgeraldnick.com/2019/11/01/always-bump-downwards.html

Not denying this, but I would assume this branch is optimized away by the compiler most of the time, since often constant sizes are allocated. So constant folding should remove the check, assuming the check is inlined.

Especially in @Wodann case. If you put #[inline] on that alloc method, then performance should be the same most of the time.

[Ixrec]

Bump allocators only need a few (very fast) integer ops and a branch to check if there's enough memory available. An extra branch would be significant.

Would a bump allocator need to explicitly check for zero to support zero-sized allocations? IIUC its alloc() would be little more than ptr += size; and if (ptr >= (start + capacity)) { ... } which seems like it'd do the right thing even if size is 0.

(I couldn't personally come up with an allocator usage where the performance of a single branch in alloc() matters and supporting ZSTs would add an additional branch, only one or the other, which is why I buy the arguments others in this thread have been making for requiring ZST support to keep the Alloc API simple)

[Wodann]

Would a bump allocator need to explicitly check for zero to support zero-sized allocations?

The returned pointer needs to have the proper alignment, which could require the ptr value to be offset. As that is the case, you still need to perform the branch statement.

edit: My response didn't make it clear that "branch statement" refers to the bounds check. Indeed for the bump allocator a if layout.size() == 0 would not be necessary, because the normal logic applies for zero-sized types too.

[..] I would assume this branch is optimized away by the compiler most of the time, since often constant sizes are allocated.

For any compile-time constants, that's true but not for runtime-specified layouts. Whether that is a common, I can't tell.

Do you want to make one and file a new issue

Yes, I can do that. What would be favorable, us adding the additional functions guaranteeing a zero-cost API for both compile-time constants and runtime variables? Or making the API simpler?

[Lokathor]

But checking for alignment and needing to offset by some amount from the current bump location is done regardless of the allocation size, so i don't think that counts.

EDIT: also most Zero-sized types are alignment 1.

[JelteF]

For any compile-time constants, that's true but not for runtime-specified layouts. Whether that is a common, I can't tell.

I can see it happening mostly for datastructures that want to grow their buffer. I'm not sure but in those cases the compiler might still be able to assert that it's non-zero in most cases.

Do you want to make one and file a new issue

Yes, I can do that. What would be favorable, us adding the additional functions guaranteeing a zero-cost API for both compile-time constants and runtime variables? Or making the API simpler?

I think @TimDiekmann meant your 3 method approach, where only alloc_sized doesn't have a default implementation. My suggestions/questions for those methods:

1. Add #[inline(always)] to alloc
2. What's the reason you marked alloc and alloc_zero_sized_type as unsafe? Only because alloc_zero_sized_type doesn't work when passing 0? If so you can use NonZeroUsize

[Lokathor]

I like the NonZeroUsize approach because a person can use NonZeroUsize::new_unchecked if they want to on their end, and then that keeps that particular bit of unsafety outside of the allocators.

[Wodann]

I can see it happening mostly for

for?

1. Add #[inline(always)] to alloc

Sounds reasonable.

2. What's the reason you marked alloc and alloc_zero_sized_type as unsafe? Only because alloc_zero_sized_type doesn't work when passing 0? If so you can use NonZeroUsize

That's a good point. I can make alloc_zero_sized_type safe by making the type NonZeroUsize. Thanks!

alloc can still be unsafe, since align could be zero. There's no easy way to fix that, unless we make Layout::align a NonZeroUsize

[Lokathor]

more than just non-zero, it has to be power-of-two.

[Wodann]

I checked the docs. The is_power_of_two guarantee that Layout provides is enough to warrant making alloc safe too.

[Wodann]

I was preparing my proposal, but found an issue with Layout. Currently, safe ways of initializing a Layout forbid the usage of zero. If we are saying that it is safe to allocate a zero-sized type by including a default implementation in alloc, I feel that we should also make it safe to initialize a Layout with zero.

Do we want to make this a change to Layout::from_size_align or introduce a new function?

Edit: striking through my comment, as my question was based on a wrong conclusion.

[petertodd]

What do you mean "forbid the usage of zero"? `size` is allowed to be zero; only `align` must be nonzero (and a power of two).

…

On February 3, 2020 8:23:42 AM EST, Wodann ***@***.***> wrote: I was preparing my proposal, but found an issue with `Layout`. Currently, safe ways of [initializing](https://doc.rust-lang.org/nightly/std/alloc/struct.Layout.html#method.from_size_align) a `Layout` forbid the usage of zero. If we are saying that it is safe to allocate a zero-sized type by including a default implementation in `alloc`, I feel that we should also make it safe to initialize a `Layout` with zero. Do we want to make this required change to `Layout::from_size_align`? -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #16 (comment)

[Wodann]

You are so right. Sorry about that..

[petertodd]

No worries. I had to read it twice myself to be sure. :)

…

On February 3, 2020 8:42:35 AM EST, Wodann ***@***.***> wrote: You are so right. Sorry about that.. -- You are receiving this because you commented. Reply to this email directly or view it on GitHub: #16 (comment)

[TimDiekmann]

I close this in favor of #38