`root!` macro

[CeleritasCelery]

This uses the same principle as the root_struct! macro. So if this is sound I expect that will be as well.

https://github.com/CeleritasCelery/rune/blob/7136b74386a4586537ffa59c3be4849cb76354fe/src/arena/mod.rs#L78-L83

We create a new StackRoot using an unsafe method. We then set the stack root, which will push the object on the RootSet. This will be popped when root drops. If the this stack like behavior of the drop glue does not happen, this will lead to UB.

Why this is sound

The new method on Root is unsafe to call, and requires that root is dropped in stack order (i.e. does not move).

impl<'rt> Drop for StackRoot<'rt> {
    fn drop(&mut self) {
        self.root_set.roots.borrow_mut().pop();
    }
}

Similar constraint as pin_mut macro. We make sure of this by never exposing the binding of root. We also require that set is called before the object is used, which is part of the macro code. Set has the follow definition ensuring that the object is borrowed for the lifetime of root.

    pub(crate) fn set<'root>(&'root mut self, obj: Object<'_>) -> Object<'root> {
        ...
    }

[Alan-Chen99]

Hmm, whats enforcing this stack order here? afaik pin_mut! does not enforce objects being drooped by the order they are created

[CeleritasCelery]

Rust has a guaranteed drop order. So long as you don't move a T (which root! prevents by never exposing T) and don't call drop early or never via mem::forget (which are prevented for the same reason), then you can rely on things getting dropped in a stack like order.

You are correct that pin_mut! doesn't make any guarantees about drop order, but root! does.

[Alan-Chen99]

I see, ig there is a degree this is sound. The user might still mess up by writing a function that consumes a root by move, though.

Have you considered using a closure for this, which specifically makes a (presumably inline) stack frame and thus is more strictly sound? It also doesn't require keeping a reference to rootset

[CeleritasCelery]

A user can’t consume or move a root because they don’t have access to it.

https://github.com/CeleritasCelery/rune/blob/6b54612727459d8752562b1244e5bf6a6fa73ab6/src/core/gc/root.rs#L178-L181

They only get access to a &mut Rt<T>, which means they can’t move the root. I believe this makes the API completely sound (but would be very interested in someone able to prove it wrong).

[Alan-Chen99]

Ah, I see. Cool idea! You have convinced me that root! is sound.

I think this can be made even lighter:

struct __StackRootLight<'rt> {
    root_set: &'rt RootSet,
}
impl Drop for __StackRootLight<'_> {
    fn drop(&mut self) {
        self.root_set.roots.borrow_mut().pop();
    }
}
struct RtLight<'a, T> {
    obj: T,
    // safe to make it shorter lived
    marker: PhantomData<&'a ()>,
}
fn record_on_rootset<'a, 'rt, T>(
    obj: T,
    sr: &'a __StackRootLight,
    root_set: &'rt RootSet,
) -> RtLight<'a, T> {
    todo!()
}
fn testfn<'rt>(root_set: &'rt RootSet) {
    let __stackroot1 = __StackRootLight { root_set };
    let mut rt1 = record_on_rootset(1, &__stackroot1, root_set);
    {
        let __stackroot2 = __StackRootLight { root_set };
        let mut rt2 = record_on_rootset(1, &__stackroot2, root_set);
        mem::swap(&mut rt1, &mut rt2);
    }
    // drop(rt1); // error[E0597]: `__stackroot2` does not live long enough
}

Not entirely sure if this new version is sound yet.

With this you can only root single pointers into gc heap; to root vectors one would have a separate macro

[CeleritasCelery]

This exposes the StackRoot which means that you could call drop or mem::forget on it.

fn testfn<'rt>(root_set: &'rt RootSet) {
    let __stackroot1 = __StackRootLight { root_set };
    let mut rt1 = record_on_rootset(1, &__stackroot1, root_set);
    drop(__stackroot1); // dropped here
    garbage_collect(); // memory is reclaimed
    println!("{rt1}"); // attempt to access invalid memory
    {
        let __stackroot2 = __StackRootLight { root_set };
        let mut rt2 = record_on_rootset(1, &__stackroot2, root_set);
        mem::swap(&mut rt1, &mut rt2);
    }
    // drop(rt1); // error[E0597]: `__stackroot2` does not live long enough
}

I don't think you can implement rooting without a macro.

[Alan-Chen99]

Of course this would still be a macro; it will expand to something like

let __stackroot1 = __StackRootLight { root_set };
let rt1 = record_on_rootset(1, &__stackroot1, root_set);

and we would expose rt1.

Presumably, this would allow the compiler to optimize out __stackroot1 entirely. The actual rooted object will only need to live in rootset.

It wouldn't be useful for a copying GC though, which I assume is the goal here?

Also, whats the reason behind using dyn Trace instead of a RawObj for rootset?

[CeleritasCelery]

Ah that makes more sense.

Yes the goal is to enable a copying GC. But as you observe, making room for a copying GC adds an extra level of indirection.

Also, whats the reason behind using dyn Trace instead of a RawObj for rootset?

Because not everything in the rootset is an object. There are things like handlers and the env that are can be added to the rootset directly. But you are correct that most things in the rootset are objects.

[Alan-Chen99]

Is handlers for catching lisp exceptions?

Anyways, this is unsound for a copying gc:

#[repr(transparent)]
pub(crate) struct Rt<T: ?Sized> {
    _aliasable: PhantomPinned,
    inner: T,
}

PhantomPinned does not make a type aliasable. This should probably be UnsafeCell<T> and keep references. I don't think it needs to be pinned, since modifying a root seems fine under the current model of the "other stack" (but the caller that is providing a rt might not except it to change to a different object though, maybe make another type for an immutable root)

[CeleritasCelery]

Is handlers for catching lisp exceptions?

yes, it determines where to jump for a condition-case statement.

PhantomPinned does not make a type aliasable.

It actually does. It marks the type !Unpin which prevents noalias annotations. It feels kinda hacky, but it is the official way and is used in tokio. You are correct though that in this context it has nothing to do with pinning.

the caller that is providing a rt might not except it to change to a different object though, maybe make another type for an immutable root

Rt follows normal mutability conventions, so an &Rt is immutable and &mut Rt is mutable.

[Alan-Chen99]

It actually does. It marks the type !Unpin which prevents noalias annotations

Interesting, I was not aware of this. I would still say interior mutability is the "right" way here, its more explicit and I suppose standard.

[Alan-Chen99]

yes, it determines where to jump for a condition-case statement.

I see. What motivates this instead of putting the error in the Result?

[CeleritasCelery]

I would still say interior mutability is the "right" way here, its more explicit and I suppose standard.

They are orthogonal issues. You need aliasing for tracing. You need interior mutability for moving objects. Adding interior mutability will not remove the need for PhantomPinned.

What motivates this instead of putting the error in the Result?

They errors are in a Result, but condition-case can have multiple handlers depending the error type, so we need to setup all of those.

[Alan-Chen99]

They errors are in a Result, but condition-case can have multiple handlers depending the error type, so we need to setup all of those.

Ah I see, that makes more sense.

They are orthogonal issues. You need aliasing for tracing. You need interior mutability for moving objects. Adding interior mutability will not remove the need for PhantomPinned.

Not sure what you mean; interior mutability is the default way to allow aliasing pointers. The API would work like this:

struct __stackroot(UnsafeCell<T::withlifetime<'static>>, &RootSet) // for drop order, never exposed
struct Rt<'a>(&'a UnsafeCell<T::withlifetime<'static>>) // Exposed to user by value, not copy nor clone
// 'a borrows from __stackroot to ensure it always points to something really rooted
// we keep a dyn &UnsafeCell<T> in rootset, which can alias with the & held in Rt

// sound since 
// 1) we also borrow from Context => no gc possible
// 2) Rt is unique for each UnsafeCell => no borrow_mut twice
borrow_mut(&'a mut Rt<'_, T>, &'a Context) -> &'a mut T::withlifetime<'a>; 
// sound since no gc + no &mut Rt
borrow(&'a Rt<'_, T>, &'a Context) -> &'a T::withlifetime<'a>;

(my understanding is this is the same API currently other than the user having a Rt type by value, do correct me if I'm wrong)

Note: this is a "not quite Lcell": If T is a Vec<Object>, it needs to restrict the lifetime of the Vec as well as the Object

[Alan-Chen99]

btw bind_as is unsound, it lets you get a 'static

[CeleritasCelery]

interior mutability is the default way to allow aliasing pointers.

it allows aliasing only in certain circumstances. The docs say:

Note that only the immutability guarantee for shared references is affected by UnsafeCell. The uniqueness guarantee for mutable references is unaffected. There is no legal way to obtain aliasing &mut, not even with UnsafeCell.

With UnsafeCell you can have a &mut T alias with a &UnsafeCell<T>, but not the other way around. You can't have &mut UnsafeCell<T> alias with &T, which is what we need to trace objects. The only way to get that is with !Unpin.

(my understanding is this is the same API currently other than the user having a Rt type by value, do correct me if I'm wrong)

That seems to be the case. What advantage do you see in that API over the current one?

btw bind_as is unsound, it lets you get a 'static

Again you are correct. You are good at finding these unsoundness holes.

[Alan-Chen99]

With UnsafeCell you can have a &mut T alias with a &UnsafeCell, but not the other way around. You can't have &mut UnsafeCell alias with &T, which is what we need to trace objects. The only way to get that is with !Unpin.

Nowhere will we need to have &mut UnsafeCell (It would be unsound to do so). When we do have &mut T, we make sure that it must also borrow from Context, so by the time we gc there could not be a &mut T left anymore. The UnsafeCell approach have nothing to do with !Unpin.

That seems to be the case. What advantage do you see in that API over the current one?

The API doesn't have any advantage (I tried to make it the same); but it seems to me that the !Unpin is just an arbitrary hack to not brake existing code when enabling noalias. What it does is not seriously documented (especially since we constructs !Unpin via a transmute). UnsafeCell is the more standard here.

[CeleritasCelery]

When we do have &mut T, we make sure that it must also borrow from Context, so by the time we gc there could not be a &mut T left anymore. The UnsafeCell approach have nothing to do with !Unpin.

I think I understand better. This is very similar to the solution I originally created to work around the aliasing problem. In fact we don't even need the the UnsafeCell to make this work. Having the extra level of indirection is enough.

I ended up moving away from this approach for a few reasons:

1. an extra level of indirection for data structures. When passing something like Env into a function you would have something like this &mut Rt<'_, Env>. and since Rt contains a reference instead of the value, you go through two pointers instead of one to get to Env. For objects it's the same level of indirection as the current approach, since you can pass Rt by value.
2. You have to explicitly borrow using borrow_mut. This is mostly just a quality of life thing, but it is nice to simplify the code. I called my function as_mut instead of borrow_mut, but it served the same purpose (bind the mutable borrow to Context). You don't even need borrow because you can just implement Deref.

but it seems to me that the !Unpin is just an arbitrary hack to not brake existing code when enabling noalias. What it does is not seriously documented (especially since we constructs !Unpin via a transmute).

That is how I originally felt, as mentioned in the blog post. But I have to come to feel that if it is good enough for Tokio (the biggest and most popular Async runtime in Rust) then it is good enough for me. It certainly feels hacky, but they haven't provided a less hacky way. Ideally they would create something like AliasableCell or #[aliasable] attribute. It's not like we are using something in a way that no one has thought of before, this is the intended workaround to this issue.

[Alan-Chen99]

Ah, I think I understand the problem better now. Rust DO have an aliasable pointer: its called raw pointers (surprise!)

it seems to me that &mut to an !unpin is just a *mut, but we can expose &mut to safe rust (We cant expose *mut to safe rust, mostly because it doesnt have a lifetime);

So it suffices to use a newtype. I think the following is a safe API: (and solve the indirection problem)

struct __stackroot(T::wlt<'static>, &RootSet) // for drop order, never exposed

// exposed by value
struct Rt<'a>(*const T::wlt<'static>, PhantomData<&'a ()>) // Copy
// the user get this on a root!.
struct RtMut<'a>(*mut T::wlt<'static>, PhantomData<&'a ()>) // NOT Copy, but see reborrow below

fn as_ref(&'a mut RtMut<'_, T>) -> Rt<'a, T>
fn borrow_mut(&'a mut RtMut<'_, T>, &'a Context) -> &'a mut T::wlt<'a>
fn borrow(Rt<'_, T>, &'a Context) -> &'a T::wlt<'a>

fn project(Rt<'a, T>, for<'c> FnOnce(&'c T::wlt<'c>) -> &'c W::wlt<'c>) -> Rt<'a, W>

// we can push an object<'c> borrowed from &'c Context into a rooted vector
fn project_mut(&'a mut RtMut<'_, T>, &'c Context, FnOnce(&'c mut T::wlt<'c>) -> &'c mut W::wlt<'c>) -> RtMut<'a, W>

// caller must make sure the closure does not gc
unsafe fn project_mut_unchecked(&'a mut RtMut<'_, T>, for<'c> FnOnce(&'c mut T::wlt<'c>) -> &'c mut W::wlt<'c>) -> RtMut<'a, W>

// we can pass the result of this to function arguments instead of &mut RtMut to reduce an indirection:
// fn_that_gc(root_vec.reborrow())
// project_mut_unchecked is easy to use: we are pretty sure |x| x does not gc
fn reborrow(self: &'a mut RtMut<'_, T>) -> RtMut<'a, T> { unsafe { self.project_mut_unchecked(|x| x) } }

With this I think a lot of root.rs can be moved out of core and be safe instead. Is there any functionality that I missed here with this approach?

It seems that !Unpin gets a special treatment from miri, which is not great since we really have no way to know if this is sound:

impl<T> Rt<Vec<T>> {
    fn as_mut_ref(&mut self) -> &mut Vec<Rt<T>> {
        unsafe { &mut *(self as *mut Self).cast::<Vec<Rt<T>>>() }
    }
}

You can't deref anymore, but I think this is for the good as deref means sketchy operations like this vector cast. Instead you rootedvec.project(cx, |v| v[0]), clean enough i think.

Note: In this model Trace must take a &mut self and produce a list of &mut rawobj This might not be good, so it might be worth while to wrap the "leaves" of roots with a Cell, then make Trace take &self

[Alan-Chen99]

Actually that might not work due to stacked borrows, will need to think more. One thing that will definitely work is to use !Unpin on leaves. This is still arguably better than current (since it doesn't require transmute). Not sure whether !Unpin will "infect" miri in terms of its ability to track down UB in wrapped types.

[Alan-Chen99]

Hmm apprently miri approves this code:

let stackvec = UnsafeCell::new(Box::new(Box::new(Cell::new(1))));

// pointer held in Rt
let rootvec = stackvec.get();
// pointer held in StackRoot
let gcptr = stackvec.get() as *const Box<Box<Cell<i32>>>;

let rootvec_bind = unsafe { &mut *rootvec };
**rootvec_bind = Box::new(Cell::new(2));
dbg!(&rootvec_bind);
// projected Rt
let el_ptr = &mut **rootvec_bind as *mut Box<Cell<i32>>;

let gcref = unsafe { &*gcptr };
gcref.set(3);
dbg!(gcref);

let el_bind = unsafe { &mut *el_ptr };
el_bind.set(4);
dbg!(el_bind);

let gcref = unsafe { &*gcptr };
gcref.set(5);
dbg!(gcref);

Not sure if this is actually sound or its a miri bug

[CeleritasCelery]

It seems that !Unpin gets a special treatment from miri, which is not great since we really have no way to know if this is sound:

There seems to be some misconception about the role of !Unpin. It is handled correctly by miri because it is the officially supported way to have aliasing &mut. Miri is not "hiding" unsoundness when using !Unpin. It has specially handling just like it does for UnsafeCell or other language constructs, because those are part of the language semantics.

So it suffices to use a newtype. I think the following is a safe API: (and solve the indirection problem)

How does it solve the indirection problem? If you need to pass a rooted data structure like Env to a function you would still need double references (&mut RtMut<'_, Env>).

fn asref(&'a mut RtMut<', T>) -> Rt<'a, T>

Why is doe this take a mutable ref?

fn reborrow(self: &'a mut RtMut<'_, T>) -> RtMut<'a, T> { unsafe { self.project_mut_unchecked(|x| x) } }

We are taking the lifetime 'a of the borrow of RtMut and making it the lifetime of inner object of the return value (RtMut<'a, T>). This would be unsound if mem::swap was used to swap two RtMut's.

With this I think a lot of root.rs can be moved out of core and be safe instead.

I don't fully understand. The new API would need to be unsafe under the hood, just the like the current API. But the current approach also provides a safe API.

You can't deref anymore, but I think this is for the good as deref means sketchy operations like this vector cast.

I don't follow. Deref is very useful. Why do you think getting rid of it is good? What do you see that is sketchy about that cast statement?

Note: In this model Trace must take a &mut self and produce a list of &mut rawobj This might not be good, so it might be worth while to wrap the "leaves" of roots with a Cell, then make Trace take &self

That is how things work now no? anything that needs to be mutated during tracing is wrapped in a cell.

Not sure if this is actually sound or its a miri bug

Looks fine to me. You are using "base" pointers and just casting those to references when needed. None of the references overlap.