Idea: Allocator trait should exclude Copy trait, require Drop trait, and get mutably borrowed on allocations

[Zero-Tang]

Neither does current Allocator trait exclude Copy trait nor does it require Drop trait.

Scenario 1: No implementation of Copy

Only one allocation is allowed in this scenario. The following example won't compile.

let a=AltAlloc::default();
// Compiler will allow this allocation.
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
// Compiler will reject this allocation.
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);

Scenario 2: No implementation of Drop, but Copy is implemented

This can cause some issues, though the following example will compile.

let a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);

Waste of Resource if AltAlloc is implemented by slicing huge internal array

Assume AltAlloc is an array of u8:

#[derive(Copy,Clone)] struct AltAlloc
{
    internal:[u8;0x10000],    // Each allocator has 64K bytes.
    // Internal members that records allocations.
    /**/
}

This AltAlloc might not need a real Drop trait implementation. But the Copy trait will make this allocator to be created more than once. In above example, there are two allocators actually created. In other words, 128K was allocated, rather than 64K.

// Allocated 64K.
let a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
// Allocated another 64K.
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);

Use After Free if AltAlloc is implemented by slicing referenced internal array

Assume AltAlloc includes a pointer to u8:

#[derive(Copy,Clone)] struct AltAlloc
{
    internal:*mut u8,    // Pointer received from `VirtualAlloc`, `mmap`, etc.
    // Records of allocations are included inside `internal`.
}

In this case, using Copy trait is fine because it only copies a pointer. It won't cause repetitive huge memory allocations. However, this AltAlloc requires something like Drop trait. Since Copy trait is implemented, Drop trait can't be implemented. Assume a destroy method is implemented:

impl AltAlloc
{
	pub unsafe fn destroy(self)
	{
		/* Internal implementation that calls munmap, VirtualFree, etc. */
	}
}

Then it would cause Use-After-Free while dropping:

let a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);
a.destroy();
// Dropping ab1 and ab2 requires using data in `a.internal`.
// This causes `Use-After-Free` fault.

The only workaround is via scoping:

let a=AltAlloc::default();
{
    let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
    let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);
    // ab1 and ab2 are dropped right before this scope ends.
}
a.destroy();

If Drop trait is implemented, then destroy method won't be required.

let a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);
// Ideally, Rust will drop things in the order of: ab2, ab1, a.

However, Copy trait can't co-exist with Drop trait. That's because it would cause doubled-free if AltAlloc contains only a pointer.

Idea: Allocators should get borrowed

If allocators are borrowed, then Copy trait won't be needed. I think Allocator trait should exclude Copy trait.

pub fn new_in(x: T, alloc: &mut A) -> Self

let mut a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,&mut a);
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,&mut a);
// Rust will drop things in the order of: ab2, ab1, a.
// This works fine even if `AltAlloc` is implemented via slicing an internal huge array on stack.

Same principle can be applied on String, Vec, etc.

[steffahn]

Scenario 1

you don’t write much about this scenario; it works, all good

Scenario 2

This can cause some issues

let’s address the issues you think you see:

Assume AltAlloc is an array of u8:

#[derive(Copy,Clone)] struct AltAlloc
{
    internal:[u8;0x10000],    // Each allocator has 64K bytes.
    // Internal members that records allocations.
    /**/
}

this is not a valid allocator at all, at least in the sense of implementing the Allocator trait, and it’s clearly documented so:

Allocator is designed to be implemented on ZSTs, references, or smart pointers because having an allocator like MyAlloc([u8; N]) cannot be moved, without updating the pointers to the allocated memory.

it’s not a valid allocator regardless of whether or not it implements Copy. The Copy implementation is unrealistic anyways, one shouldn’t derive or implement Copy on such large types. Even if you do have a concrete example of allocator that works fine if it isn’t Copy but is problematic with the Copy, that’s not a valid argument for denying Copy on all allocators altogether.

If it’s unsound for some allocators to be Copy, but okay for others, then allocator implementors just simply mustn’t implement nor derive Copy in the former cases. Allocator is an unsafe trait, and the safety contract explicitly refers to copying and cloning already.

However using data on the stack for allocation is an intended (and supported) use case, see more below.

---

Assume AltAlloc includes a pointer to u8:

#[derive(Copy,Clone)] struct AltAlloc
{
    internal:*mut u8,    // Pointer received from `VirtualAlloc`, `mmap`, etc.
    // Records of allocations are included inside `internal`.
}

This case is indeed problematic. As mentioned above, this particular allocator must thus not implement Copy if it wants to support proper clean-up a la Drop

Requiring some sort of scoping for such usage, as in e.g.

let a=AltAlloc::default();
{
    let ab1:Box<u32,AltAlloc>=Box::new_in(1234,a);
    let ab2:Box<u32,AltAlloc>=Box::new_in(4321,a);
    // ab1 and ab2 are dropped right before this scope ends.
}
a.destroy();

is indeed the correct idea to combine lightweight sharing with destructors, and indeed you almost get ther:

If allocators are borrowed, then Copy trait won't be needed. I think Allocator trait should exclude Copy trait.

pub fn new_in(x: T, alloc: &mut A) -> Self

let mut a=AltAlloc::default();
let ab1:Box<u32,AltAlloc>=Box::new_in(1234,&mut a);
let ab2:Box<u32,AltAlloc>=Box::new_in(4321,&mut a);
// Rust will drop things in the order of: ab2, ab1, a.
// This works fine even if `AltAlloc` is implemented via slicing an internal huge array on stack.

The only issue is the mutability. If you really write &mut a, you can’t actually use ab1 and ab2 at the same time in Rust. This is exactly why the actual existing design instead uses shared references everywhere! Note that shared references can still support mutability; the allocator implementor must just decide how to actually do that, whether this interior mutability would be limited to single-threaded use (and enforced via A: !Sync) or if locking or atomics can solve thread safety, or if that choice is somehow configurable. So without the mut on the references, here we are:

pub fn new_in(x: T, alloc: &A) -> Self

let mut a = AltAlloc::default();
let ab1: Box<u32,AltAlloc>=Box::new_in(1234,&a);
let ab2: Box<u32,AltAlloc>=Box::new_in(4321,&a);
// Rust will drop things in the order of: ab2, ab1, a.
// This works fine even if `AltAlloc` is implemented via slicing an internal huge array on stack.

That would work! How does it compare to the actual API? Here’s the secret: The current API is merely a generalization of the above!

This is all because of this blanket impl:

impl<A> Allocator for &A
where
    A: Allocator + ?Sized,
{ … }

which makes it so that “when A is an allocator, so is &A”.

So the above code isn’t changed much, as the below will work today:

pub fn new_in(x: T, alloc: A) -> Self

let mut a = AltAlloc::default();
let ab1: Box<u32,&AltAlloc>=Box::new_in(1234,&a);
let ab2: Box<u32,&AltAlloc>=Box::new_in(4321,&a);
// Rust will drop things in the order of: ab2, ab1, a.
// This works fine even if `AltAlloc` is implemented via slicing an internal huge array on stack.

Now, the Box::new_in call no longer works with A = AltAlloc but A = &AltAlloc. Types like Box can work either with a sort of “owned” allocator directly, or a shared one (shared via the &_ type), and only in the latter case do you need to endure the downsides of this approach of usage, because there are downsides to using references as allocators:

• using a reference means the collection now has a lifetime parameter; if you work with Box<u32, &AltAlloc>, that’s really only a shorthand, the actual type is always Box<u32, &'lt AltAlloc> involving some lifetime argument 'lt.

  That’s another mistake in your presentation; with a pub fn new_in(x: T, alloc: &A) -> Self constructor, the type Box<T, A> would need to be changed to something like Box<'lt, T, A> – and new_in then takes a &'lt A of that same lifetime – to denote the lifetime somewhere.

  The default Box<T> using Global allocator can avoid this downside entirely; there’s no lifetime in Box<T, Global>

• using a reference means there’s always a reference value involved. The type &mut AltAlloc or &AltAlloc is as large as a pointer; as would be &mut Global or &Global, even though user of the global allocator do not need any actual memory address to help them. The current design can have Box<T, Global> use a zero-sized type Global as a marker, without any runtime overhead at all, so the whole of Box<T> (aka Box<T, Global>) itself can still be a simple, single one-word pointer under the hood. [Ignoring T: !Sized cases.]

[the8472]

Assume AltAlloc is an array of u8:

#[derive(Copy,Clone)] struct AltAlloc
{
    internal:[u8;0x10000],    // Each allocator has 64K bytes.
    // Internal members that records allocations.
    /**/
}

You might be interested in the storage API proposal #93 and related discussions, though not much progress has been made afaict.