Allocation and Deallocation in different allocators

language design Unsafe Code Guidelines
1

I would introduce the problem first, then my thoughts about it.

When allocator api will get stabilized I would like to use it to store Box'ed inside static variable. Like a mini heap with capacity to hold 1 element.

The problem I have, is that I see no sound way for Box to be the size of 1 word.

I want to give allocator a place when it should try to allocate, this has size of a pointer, call it A. Allocation has a signature fn allocate(&self, layout: Layout) -> ... so I can access &self to return a pointer to that static, that allocator was constructed with. Box is storing 2 things - pointer to data and allocator. When box allocated, allocator gave it pointer A, and allocator itself has pointer A inside. So we end up with box with size of 2 words, each of them is equal (modulo synchronization).

When box will call deallocate, it will pass A to allocator. And allocator will also have access to A by &self. So it is a clear redundancy.

So we need Allocator to have size of 1 word to perform an allocation, but after that I would like to have allocator as ZST, because it will get original pointer back from Box.

Other approach might be making allocator a zst and 'magically' making it return the right pointer - by global state or something like this. But this is inefficient and complicated for no real reason.

static mut PLACE: MaybeUninit<T> = MaybeUninut::uninit();

let allocator = OneShotAlloc(PLACE.as_mut_ptr());
let my_box = Box::new_in(t, allocator);
drop(my_box);
2

The tracking issue discusses splitting Allocator into an Allocator trait with a smaller surface, and a Deallocator trait. I don't recall what the conclusions were, but I believe this is trodden ground.

1 Like
3

I don't think your allocator is sound, since calling allocate twice on it would yield the same pointer, which is obviously unsound.

It's slightly more complicated, but you instead do something like this:

let my_box = Box::write(Box::from_raw_in(addr_of_mut!(PLACE), NoopDeallocOnlyAllocator), t);

Where:

  • you skip using Box::new for allocating, since that will try to use your allocator to allocate, but it fundamentally doesn't support really allocating. Instead a *mut MaybeUninit<T> is provided to Box::from_raw_in to create a Box<MaybeUninit<T>> and then Box::write is used to initialize it with t. Note that you'll still have to guarantee that nothing else is using PLACE.
  • the allocator used (NoopDeallocOnlyAllocator) always fails to allocate/grow/shrink, while its deallocate method is a noop.
4

This is just an example. Real one would have bool inside the static and OOM if it was allocated

5

This is unsound and was discussed before

6

Perhaps ThinBox could have custom allocator support, and store the allocator on the heap, alongside the metadata.

1 Like
7

That's discussing Box<_, Global>, not Box<_, NoopDeallocOnlyAllocator>. Non-global allocators may not have the same extra restrictions applied to them to allow allocation elision, so you can do many more things soundly with them.

1 Like
8

Technically, this is undecided. However, the magic is currently only applied to alloc::Global, and the current leaning is that if similar magic is going to be available to other allocators, it will be via some magic wrapper[1], not by the unsafe impl Allocator itself.

  1. E.g. that wrapper would semantically add the possibility of bypassing your allocator and using magic compile time allocation instead, thus enabling alloc elision. ↩ī¸Ž