Pinned Box #228
Pinned Box #228
Conversation
|
I don't have time to dig in yet, but here are some initial thoughts:
|
👍
Yes, that's how it's currently implemented. (Besides, the sentinel node is also currently lazily allocated and initialized.)
Exciting stuff!
Yeah, I don't think the ordering requirement is going to be a problem. The current impl uses a doubly linked list, so you could just iterate forwards or backwards regardless in what order you push the drop entries. However, the way some APIs are currently implemented might pose an issue here: Both Also, I am not exactly sure about the design you have in mind but I can also imagine one could maintain multiple drop lists for each sub-arena/checkpoint,
I've added some basic tests that test the API surface of the pinned Box. But we should probably add some tests around the internals (drop list) too.
It's more of an implementation detail (See below).
That won't work with SB because it's still doing "pointer arithmetic" (playground). IIUC, pointers can only be derived by actually "reborrowing" from a pointer, Although, I admit I'm not an expert in the SB/Tree-Borrows pointer aliasing models, so I might be totally wrong about this 😅. |
| _marker: PhantomData<&'a mut T>, | ||
| } | ||
|
|
||
| impl<'a, T> Box<'a, T> { |
There was a problem hiding this comment.
T must satisfy T: 'a (or be able to outlive 'a) so that drop within the bump would not be called on invalid value.
| impl<'a, T> Box<'a, T> { | |
| impl<'a, T> Box<'a, T> | |
| where | |
| T: 'a | |
| { |
There was a problem hiding this comment.
Actually 'a is just an lifetime to an immutable reference of Bump, which can be subtyped into smaller lifetimes via covariance, so this is not good enough. Appropriate fix for would be to add a covariant lifetime argument 'b to Bump itself to restrict it and then restrict T: 'b.
There was a problem hiding this comment.
The marker PhantomData<&'a mut T> inside Box<'a, T> should produce the implied bound T: 'a, so your suggested change should be a noop.
Actually 'a is just an lifetime to an immutable reference of Bump, which can be subtyped into smaller lifetimes via covariance, so this is not good enough.
I don't see how this is unsound. Even if you'd have &'short Bump, T must outlive 'short (and 'long: 'short). The returned ref to T will be borrowed for the shorter lifetime and can't live longer than that.
It would be great if you could provide an example where this unsoundness is demonstrated :)
There was a problem hiding this comment.
You drop T: 'short object within the Bump: 'long's drop. Just as i've said it in the first comment.
There was a problem hiding this comment.
Ah I see the issue now. Yeh, it's actually very easy to trigger a UAF with something like
#[test]
fn pinned_failure() {
struct Foo<'a>(&'a String);
impl<'a> Drop for Foo<'a> {
fn drop(&mut self) {
println!("{}", self.0);
}
}
let bump = Bump::new();
let s = "hello".to_string();
let p = Box::new_in(Foo(&s), &bump);
mem::forget(p);
drop(s);
drop(bump);
}There was a problem hiding this comment.
I've added a T: 'static bound (for now) which should hopefully make this more sound. It is obviously more restrictive now but it doesn't require more "invasive" api changes to Bump. Haven't really thought much about this, but I'll have a more deeper look into this in the upcoming days. Also thank you @zetanumbers for noticing this :)
| /// Constructs a new `Pin<Box<T>>`. If `T` does not implement `Unpin`, then | ||
| /// `x` will be pinned in memory and unable to be moved. | ||
| #[inline(always)] | ||
| pub fn pin_in(x: T, a: &'a Bump) -> Pin<Box<'a, T>> { | ||
| Box(a.alloc(x)).into() | ||
| } | ||
|
|
There was a problem hiding this comment.
Instead of being removed entirely, it would also be sound to restrict it to 'static, i.e. add a separate impl block for Box<'static, T> with
impl<T: ?Sized> Box<'static, T> {
/// Constructs a new `Pin<Box<'static, T>>`. If `T` does not implement `Unpin`, then
/// `x` will be pinned in memory and unable to be moved. This requires borrowing
/// the `Bump` for `'static` to ensure that it can never be reset or dropped.
#[inline(always)]
pub fn pin_in(x: T, a: &'static Bump) -> Pin<Box<'static, T>> {
Box(a.alloc(x)).into()
}
}| impl<'a, T: ?Sized> From<Box<'a, T>> for Pin<Box<'a, T>> { | ||
| /// Converts a `Box<T>` into a `Pin<Box<T>>`. | ||
| /// | ||
| /// This conversion does not allocate on the heap and happens in place. | ||
| fn from(boxed: Box<'a, T>) -> Self { | ||
| // It's not possible to move or replace the insides of a `Pin<Box<T>>` | ||
| // when `T: !Unpin`, so it's safe to pin it directly without any | ||
| // additional requirements. | ||
| unsafe { Pin::new_unchecked(boxed) } | ||
| } | ||
| } | ||
|
|
There was a problem hiding this comment.
Likewise, this impl could just be restricted to 'static.
impl<T: ?Sized> From<Box<'static, T>> for Pin<Box<'static, T>> {
/// Converts a `Box<'static, T>` into a `Pin<Box<'static, T>>`.
///
/// This conversion does not allocate and happens in place. This requires borrowing
/// the `Bump` for `'static` to ensure that it can never be reset or dropped.
fn from(boxed: Box<'static, T>) -> Self {
// It's not possible to move or replace the insides of a `Pin<Box<T>>`
// when `T: !Unpin`, and because the lifetime the `Bump` is borrowed
// for is `'static`, the memory can never be re-used, so it's safe to pin
// it directly without any additional requirements.
unsafe { Pin::new_unchecked(boxed) }
}
}
Fixes #226.
Fixes #186.
This adds a new "pinned" Box type (
pin::Box<T>), that guarantees runningT's drop impl whenever the box is leaked and theBumpallocator is reset or dropped.The impl utilizes a "intrusive circular doubly linked list" that links every "pinned" allocation that needs a cleanup. Each list entry detaches when the Box itself is dropped.
That way, when the
Bumpallocator is cleared, we can run theDropimpls by traversing the list.The pinned Box is still one pointer-sized big. We can calculate the each allocation's header pointer by doing some pointer arithmetic. Note that this only passes miri with tree-borrows enabled (not compatible with stacked borrows and reports UB) due to the kind of container-of style pointer arithmetic being used.
As I mentioned above this has the implication that drop impls have to run when the bump allocator is cleared which goes against bumpaloo's current situation that resets are "extremely fast" and don't run any Drop impls.
So this change is a breaking change and needs discussion first. Whether or not we want to actually support this. One simple alternative would be to simply remove the support for pinned Boxes.
TODO