To improve memory allocation and de-allocation performance in my application I wrote a very customized and simplistic replacement for std::boxed::Box. It comes with some limitations:
For any given T, all Box<T> are allocated from the same fixed-size buffer, allowing at most 128 items of a type to be allocated at the same time.
No unsized types are supported.
The allocator allows to allocate only 16 distinct types.
No types with non-'static lifetime can currently be allocated.
Limitations 1 and 2 are inherent to the allocator's design: I simply use a u128 to track free slots in the statically-sized storage array. Limitations 3 and 4 are unpleasant implementation details which I'd like to get rid off but I don't know how.
Miri detects UB in your playground example (pick Tools > Miri), so seems like it's not.
error: Undefined Behavior: trying to retag from <3916> for SharedReadOnly permission at alloc1860[0x0], but that tag does not exist in the borrow stack for this location
--> /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:376:18
|
376 | unsafe { &*self.as_ptr() }
| ^^^^^^^^^^^^^^^
| |
| trying to retag from <3916> for SharedReadOnly permission at alloc1860[0x0], but that tag does not exist in the borrow stack for this location
| this error occurs as part of retag at alloc1860[0x0..0x4]
|
= help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
= help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <3916> was created by a SharedReadWrite retag at offsets [0x0..0x4]
--> src/main.rs:163:5
|
163 | element.as_mut_ptr()
| ^^^^^^^^^^^^^^^^^^^^
help: <3916> was later invalidated at offsets [0x0..0x210] by a Unique retag
--> src/main.rs:113:19
|
113 | .position(|e| e.downcast_mut::<Allocator<T>>().is_some());
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
= note: BACKTRACE (of the first span):
= note: inside `std::ptr::NonNull::<Foo>::as_ref::<'_>` at /playground/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:376:18: 376:33
note: inside `<boxed_poorly::Box<Foo> as std::ops::Deref>::deref`
--> src/main.rs:201:13
|
201 | unsafe { self.0.pointer.as_ref() }
| ^^^^^^^^^^^^^^^^^^^^^^^
note: inside `main`
--> src/main.rs:254:13
|
254 | assert_eq!(foo1.a, 1);
| ^^^^^^
Well, I guess I am creating aliasing mutable references, and those are illegal even though I should not be using them at the same time. Unfortunately it will be hard to get rid of those in the current design, even using UnsafeCell and such. Not sure if it's even possible. Therefore I would be open to any suggestions...
You basically just need to avoid ever creating an &mut to anything "above" the actual array elements that belongs to the same memory region. When you create an &mut Allocator<T> that grants exclusive permission to the all of the memory directly covered by the struct[1] which clobbers the permissions for all of the existing boxes.
You can fix it relatively easily by wrapping the Allocator fields in an UnsafeCell and modifying the rest of your code so you only ever have a shared reference or a raw pointer to the whole allocation.
That passes miri, but if you uncomment the call to boxed_poorly::create_mut_ref() and re-run miri on it, it will fail. The function just creates an &mut AllocatorInner<Foo> which is the type inside the UnsafeCell. That hopefully helps to demonstrate what the problem was in your original code.
i.e. it wouldn't affect the permissions on a memory region you held a pointer to since that isn't directly part of the struct âŠī¸
This looks very promising, thanks! Your Allocator::get could return Option<*mut MaybeUninit<T>> directly, then two casts can be omitted (your .cast() and my as *mut _).
Though I do have one more question. AllocatorArray::retrieve still needs &mut self and I use a Mutex to access the whole thing. Doesn't this mean that once any data has been allocated and given to the user as a boxed_poorly::Box (which bypasses the mutex), allocating any more data leads to mutable aliasing again? Even though Miri doesn't seem to catch it right now.
No references or pointers to AllocatorArray's memory persist past when the MutexGuard is dropped. AllocatorArray contains pointers to Allocators it doesn't contain them directly. If you weren't using indirection in the ArrayVec you would need to get creative to avoid issues. As things are though as long as you never hand out the same array element while a Box exists I think you shouldn't run afoul of the stacked borrows rules
Well from my understanding, owning a Box<T> should be semantically equivalent to owning a T directly with regards to the borrow checker. Even though there's some indirection, ownership is still the same. Consider the case where I hypothetically drop the AllocatorArray but have already given out references to allocated memory. Those would become dangling. While I think my AllocatorArray should live until the program ends because it's a static item - so it's probably a non-issue -, it would be more correct to leak the boxed allocators. Does this make any sense?
When we say that a type "owns" a value, we generally mean that it's responsible for dropping that value when it is destroyed. Owning a value is sort of the opposite of borrowing it, but the borrow checker doesn't particularly care about owned values. The stacked borrows rules care even less, as they are entirely concerned with how raw pointers and safe references interact with one another.
Alright, that makes sense because there's no borrowing going on. But then I would argue that the ownership is messed up instead, because as I outlined, if the AllocatorArray type was used on the stack for example, there could be problems with the drop order leading to dangling references. However I accept your answer with the updated playground because I am sure I can fix this issue by myself, and although I'd still be interested in further improvements, I am most concerned with the soundness.