Best way to initialize objects in a slab allocator?

help
1

I'm working on implementing a slab allocator, and I'm trying to figure out how to design the initialization API. In particular, slab allocators allocate slabs of already-initialized objects. In order to accomplish this, the client must provide some way of specifying how objects are to be initialized.

This is where I'm running into problems. There are three primary desiderata that are in conflict with one another:

  • The client should not need to write any unsafe code
  • The allocator should impose the fewest requirements possible on what sorts of objects can be allocated (e.g., trait requirements)
  • The initialization should be as fast as possible

I've come up with two potential solutions, but neither are ideal:

Solution 1
The client provides a function with the signature new() -> T which initializes and returns a new object of type T. When initializing a new object in a slab, the allocator calls the client's new() function, and moves the resulting T into the proper location in the slab, overwriting the previously-uninitialized memory at that location.

This approach allows the client to write a new() function which doesn't require the use of unsafe code. However, it is not performant because it might require an expensive memory copy in order to move T from new()'s stack to the slab (I don't think that the Rust compiler can optimize the copy out in the general case?) . Worse, I could be wrong about this, but I think this precludes cyclic recursive data structures since it's not safe to take a reference to the initialized object since its address will move if it's copied from new()'s stack to the slab.

Solution 2
The client provides a function with the signature init(ptr: *T), where ptr is a pointer to raw, uninitialized memory of the proper size to hold a T. When initializing an object, the allocator calls init with the address of the object's underlying memory in the slab, and init is responsible for constructing it such that ptr now points to a valid T.

This approach sidesteps the performance and recursion issues of Solution 1, but it requires the client to write unsafe code, which is not desirable.

The Question
So my question is this: Is there some way to avoid these issues and find a solution that achieves all of the desiderata outlined above? If not, does anyone have guidance on what should drive the tradeoff between the two solutions presented (or perhaps a third solution which is similarly imperfect)?

Thanks!

2

If you could require the objects to be Copy, then you could safely memcpy them around.

Instead of init(*T) you could require objects to implement Default and pass init(&mut T) to a default object instead.

Calls to (unboxed) closures are always inlined, so there's a high chance that Rust will optimize out needless memcpy's.

3

Ah, I like the Default + init(&mut T) approach.

Also, I should clarify that my issue with recursion with Solution 1 is not just recursive types, but types with cycles, where you need to know the address of the object at init time in order to construct references to it. The Default + init(&mut T) approach solves this, though.

4

It sounds like you'd do well with the upcoming Placer API.