Better allocation signatures?

[Alan-Chen99]

It's unfortunate that allocation must go through refcell.

Perhaps we can do better by using some sort of ghosttoken?

fn alloc<'b, 'a>(cx: &'a mut Context, token: &'b Token) -> Object<'b>
fn garbage_collect<'b, 'a>(cx: &'a mut Context, token: &'b mut Token) {}

This way we don't need to rebind! as the objects will borrow from the token instead.
a root will take a &Object and produce something not borrowed from token.
when we garbage_collect, we take a &mut token ensuring we rooted any pointers to the gc heap.

Hmm ig this doesn't actually work. didn't really thought this through

[CeleritasCelery]

Thanks for looking into this. I would love to find ways to remove refcell or improve the code. I don't see a way to get rid of the rebind! macro due to this fundamental limitation. Currently, Context is acting both as a data structure and a token.

[Alan-Chen99]

Hmm, Perhaps one can use HRTBs to get rid of rebind? we tag ContextWrapper with a 'b which changes on gc. we only allow objects to be accessed given a ContextWrapper of the same tag.

struct TokenInit<'b> {
    marker: PhantomData<fn(&'b ()) -> &'b ()>,
}
struct BrandedObject<'b, T> {
    x: T,
    marker: PhantomData<fn(&'b ()) -> &'b ()>,
}
struct ContextWrapper<'ob, 'rt, 'b> {
    cx: &'ob mut Context<'rt>,
    marker: PhantomData<fn(&'b ()) -> &'b ()>,
}

fn alloc<'b, T>(cx: &ContextWrapper<'_, '_, 'b>) -> BrandedObject<'b, T> {
    todo!()
}
fn borrow_mut<'a, 'b, T>(
    obj: &'a mut BrandedObject<'b, T>,
    cx: &'a ContextWrapper<'_, '_, 'b>,
) -> RefMut<'a, T> {
    todo!()
}

fn garbage_collect<'ob, 'rt, 'b, 'c>(
    cx: ContextWrapper<'ob, 'rt, 'b>,
    init: TokenInit<'c>,
) -> ContextWrapper<'ob, 'rt, 'c> {
    todo!()
}
fn with_token<T, F: for<'b> FnOnce(TokenInit<'b>) -> T>(f: F) -> T {
    f(TokenInit {
        marker: PhantomData,
    })
}

fn function_that_gcs<'ob, 'rt, 'b, 'c>(
    obj: BrandedObject<'b, i32>,
    init: TokenInit<'c>,
    cx: ContextWrapper<'ob, 'rt, 'b>,
) -> (BrandedObject<'c, i32>, ContextWrapper<'ob, 'rt, 'c>) {
    todo!()
}

trait Branded<'b> {
    type Type;
}

fn loop_with_token<'rt, 'ob_outer, 'b_outer, 'c_outer, B, F>(
    cx: ContextWrapper<'ob_outer, 'rt, 'b_outer>,
    init_token: TokenInit<'b_outer>,
    init: <B as Branded<'b_outer>>::Type,
    f: F,
) -> (
    ContextWrapper<'ob_outer, 'rt, 'c_outer>,
    <B as Branded<'c_outer>>::Type,
)
where
    B: for<'b> Branded<'b>,
    F: for<'b, 'c, 'ob> Fn(
        TokenInit<'c>,
        ContextWrapper<'ob, 'rt, 'b>,
        <B as Branded<'b>>::Type,
    ) -> (ContextWrapper<'ob, 'rt, 'c>, <B as Branded<'c>>::Type),
{
    todo!()
}

This has the bonus that we can pass non-rooted objects as arguments. Rather verbose though.
Possible to rewrite to reduce pointer indirections.

Edit: must use invariant marker

[CeleritasCelery]

You will have to help me break this down. I have a few questions.

When you say reduce pointer indirection, where are you talking about specifically? Objects themselves are tagged pointers that don't have any indirection. Rooted objects do have a level of indirection, but that is because it allows us to implement a moving collector. We can (and I plan to) change the Root and Rt type to hold a cell, and then during collection we could update the pointer to a new area. This wouldn't be possible without a level of indirection.

As far as HRTB's are concerned. I am try to see where those would be helpful. One of the key features of the current approach is that we can statically prove that all roots are accounted for. This is because all objects have their lifetimes tied to Context and we take &mut Context when we call garbage_collect. This ensure that no objects can live through a garbage collection. The only way they can is if they are rooted, in which case their lifetime is no longer tied to Context. The garbage_collect method in your sample code does not seem to have that property.

But you do present a really interesting alternative to rebind! with your function_that_gcs example. We could return a Context or ContextWrapper and rebind that without a macro. That would effectively change this:

let x = rebind!(function_that_gcs(cx), cx)

into this:

let (cx, x) = function_that_gcs(cx)

I honestly had not thought of that approach before. I wonder if there are corner cases that would make it harder to work with. Using your approach would both get rid a macro and some gnarly unsafe code.

[Alan-Chen99]

Note: above markers fixed to be invariant

HRTB is used to enforce safety.
The idea is that a normal function would look like this:

fn function_that_gcs<'ob, 'rt, 'b, 'c>(
    obj: &BrandedObject<'b, i32>,
    init: TokenInit<'c>,
    cx: ContextWrapper<'ob, 'rt, 'b>,
) -> (BrandedObject<'c, i32>, ContextWrapper<'ob, 'rt, 'c>) {
    todo!()
}
fn function_that_gcs2<'ob, 'rt, 'b, 'c>(
    obj: BrandedObject<'b, i32>,
    init: TokenInit<'c>,
    cx: ContextWrapper<'ob, 'rt, 'b>,
) -> (BrandedObject<'c, i32>, ContextWrapper<'ob, 'rt, 'c>) {
    with_token(|init2| {
        let mut obj = obj;
        borrow_mut(&mut obj, &cx); //Ok
        let (mut obj2, cx) = function_that_gcs(&obj, init2, cx);
        borrow_mut(&mut obj2, &cx); //Ok

        // borrow_mut(&mut obj, &cx); //error[E0521]: borrowed data escapes outside of closure
        function_that_gcs(&obj2, init, cx)
    })
}

so you would need a &context to actually access the fields of obj.
From the signature of borrow_mut, the &context must have the same "brand" ('b lifetime), or else it won't compile. The commented line generates an error: (Unfortunately not the best error message ever)

388 |     obj: BrandedObject<'b, i32>,
    |     --- `obj` declared here, outside of the closure body
...
392 |     with_token(|init2| {
    |                 ----- `init2` is a reference that is only valid in the closure body
...
398 |         borrow_mut(&mut obj, &cx); //error[E0521]: borrowed data escapes outside of closure
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^ `init2` escapes the closure body here
    |
    = note: requirement occurs because of the type `ContextWrapper<'_, '_, '_>`, which makes the generic argument `'_` invariant
    = note: the struct `ContextWrapper<'ob, 'rt, 'b>` is invariant over the parameter `'rt`
    = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

The way this works is that we force the new cx to be tied to the TokenInit which we only allow to generate through a HRTB (with_token). This forces our code to be generic over the lifetime of init2, which forces each generic to be unique. There might be a way to force it without HRTB, will need to think more on that.

By pointer indirection, I meant allocation performance, i.e. one hopefully don't need to walk 3 pointers to get the Block. Sorry this wasn't clear

[CeleritasCelery]

Thanks.

I was able to test your example, and it works like you said.

I still don't understand what this approach is trying to accomplish. Is the sole purpose to reduce pointer indirection to the Block or am I confusing two things? You mention safety, but the current scheme is also a safe interface.

[Alan-Chen99]

Sorry if this wasn't clear, with that I wasn't trying to accomplish anything particular; rather was an experiment to try to not have rebind.
It ends up having the advantage of

1. function arguments no longer need to be rooted
2. It is safe to have two contexts at once (can be accomplished in simpler ways though)
3. It feels less unsafe than rebind, which is based on an unsafe trait (I think rebind can be done in a safer way on its own though, i.e. transmuting only lifetime)

I don't think the advantages outweigh having to make a closure for every call, but it might be useful if we find a way to achieve the same without closures.

[Alan-Chen99]

also, maybe unrelated question: why cant Context own RootSet?

[CeleritasCelery]

Ah, that makes more sense.

why cant Context own RootSet?

Because stack roots need a reference to the RootSet.

rune/src/core/gc/root.rs

Lines 113 to 116 in db0ac8a

	pub(crate) struct __StackRoot<'rt, T> {
	data: &'rt mut Rt<T>,
	root_set: &'rt RootSet,
	}

If the RootSet was owned by Context then the lifetime 'rt would need to be tied to the reference of Context (&'rt Context). However the whole point of rooting is to have a lifetime not tied to Context So that an object can survive garbage collection. If we wanted to use unsafe, we could change __StackRoot to take a raw pointer instead of reference, then we could get away with Context owning the RootSet. But I prefer to avoid unsafe when I can.

It feels less unsafe than rebind, which is based on an unsafe trait (I think rebind can be done in a safer way on its own though, i.e. transmuting only lifetime)

Unfortunately transmute does not work here because we don't want to change the lifetime itself, we want to disassociate two lifetimes so that the mutable borrow is can be dropped.

Your original strategy of passing the Context reference in the return type would already get rid of unsafe code. We would have to see what other trade-off come with that.

function arguments no longer need to be rooted

That would be big if we could find some way to accomplish that. However I wouldn't want to sacrifice a lot of code readability or idomaticness to do so.

[Alan-Chen99]

If the RootSet was owned by Context then the lifetime 'rt would need to be tied to the reference of Context (&'rt Context). However the whole point of rooting is to have a lifetime not tied to Context So that an object can survive garbage collection. If we wanted to use unsafe, we could change __StackRoot to take a raw pointer instead of reference, then we could get away with Context owning the RootSet. But I prefer to avoid unsafe when I can.

I see, I think this is sensible now.

Unfortunately transmute does not work here because we don't want to change the lifetime itself, we want to disassociate two lifetimes so that the mutable borrow is can be dropped.

Its possible to transmute through 'static like so:

pub(crate) unsafe trait Rebindable<'b> {
    // SAFETY:
    // Type must not contain any field of type &'b mut T
    type Type;
}
unsafe impl<'b, T: Rebindable<'b>> Rebindable<'b> for Gc<T> {
    type Type = Gc<<T as Rebindable<'b>>::Type>;
}

pub(crate) unsafe fn unbind_for_rebind<'b, T>(
    val: <T as Rebindable<'b>>::Type,
) -> <T as Rebindable<'static>>::Type
where
    T: for<'c> Rebindable<'c>,
{
    mem::transmute(val)
}

pub(crate) unsafe fn rebind_by_ref<'c, T, R>(
    _cx: &'c T,
    val: <R as Rebindable<'static>>::Type,
) -> <R as Rebindable<'c>>::Type
where
    R: for<'b> Rebindable<'b>,
{
    mem::transmute(val)
}

#[macro_export]
macro_rules! rebind_new {
    ($type:ty, $cx:ident, $value:expr) => {{
        let value = $value;
        unsafe {
            let value_as_static = $crate::core::gc::unbind_for_rebind::<$type>(value);
            $crate::core::gc::rebind_by_ref::<_, $type>($cx, value_as_static)
        }
    }};
}
// example:
// let obj = rebind_new!(Gc<RebindObj>, cx, self.implicit_progn(iter, cx)?);

I believe one can make this even safer by making a closure in the macro which makes unbind_for_rebind only transmute the lifetime that comes from the input &mut Context to 'static instead of any arbitrary 'b.

Your original strategy of passing the Context reference in the return type would already get rid of unsafe code. We would have to see what other trade-off come with that.

Unfortunately I don't think this accomplishes anything on its own. If we return something that contains &mut Context, we cannot also return any objects that borrows from it. The HRTB only works due to using types instead of borrowing to enforce safety.

That would be big if we could find some way to accomplish that. However I wouldn't want to sacrifice a lot of code readability or idomaticness to do so.

Agree.

[Alan-Chen99]

I think I have a way to (cleanly) allow non-rooted objects as arguments now.

We can try to pass around contexts that contains objects:

struct ContextWrapper<'ob, 'rt, T> {
    // or maybe just an owned Context?
    cx: &'ob mut Context<'rt>,
    // Non-rooted obj that can be thought of as immutably borrowed from cx
    obj: T,
}

we provide these apis:

// deref
fn(&ContextWrapper<T>) -> &T;
// derefmut
fn(&mut ContextWrapper<T>) -> &mut T;

fn borrow_ctx(&ContextWrapper) -> &Context;
// Need a (safe) trait for T<'a> and R<'a> to be a thing
fn(ContextWrapper<T>, for<'a> FnOnce(&'a Context, T<'a>) -> R<'a>) -> ContextWrapper<R>;
// return local root as non-root
fn(ContextWrapper<_>, Rt<R>) -> ContextWrapper<R>;

and functions will look like

fn function_that_may_gc(ContextWrapper<T>) -> ContextWrapper<R>

GC by converting ContextWrapper into &mut Context by throwing away obj.
With this I think we will also no longer need to rebind!.

Not sure how well Rust can optimize ContextWrapper; there might be a case for a separate zero-sized token for permission

[Alan-Chen99]

Actually, that was unsound since it cannot prevent the user from storing an &Context inside the T of ContextWrapper.

Using Token doesn't have this problem. We have instead

//unique for each context
struct State<T> {
    obj: T,
}
// 'a is mandatory to prevent user from moving an object out of the closure
fn(State<T>, for<'a> FnOnce(Token<'a>, T<'a>) -> R<'a>) -> State<R>;
// you can get a bool or int out or just do mutations
fn(&State<T>, for<'a> FnOnce(Token<'a>, &T<'a>) -> R) -> R;
fn(&mut State<T>, for<'a> FnOnce(Token<'a>, &mut T<'a>) -> R) -> R;
// Get out a single Object which can then be rooted
fn(&b State<T>, for<'a> FnOnce(Token<'a>, &mut T<'a>) -> Object<'a>) -> Object<'b>;
// Token is Copy
fn alloc(Token<'a>, &mut Context) -> Object<'a>;
fn from_root(Token<'a>, &mut Rt<T>) -> T<'a>;
// clear out state
fn garbage_collect(State<_>, &mut Context) -> State<()>
fn function_that_may_gc(State<T>, &mut Context) -> State<R>

The user is free to keep a Token in T if they want, it wont accomplish anything and wont be unsound

[CeleritasCelery]

Its possible to transmute through 'static like so:

You can transmute through a static, but it still doesn't dissociate the lifetimes. Take this sample code

use std::mem;

#[derive(Debug)]
struct Gc<'a>(&'a usize);
struct Context(usize);

pub(crate) unsafe fn unbind_for_rebind<'b>(val: Gc<'b>) -> Gc<'static> {
    mem::transmute(val)
}

pub(crate) unsafe fn rebind_by_ref<'c>(_cx: &'c Context, val: Gc<'static>) -> Gc<'c> {
    mem::transmute(val)
}

fn test_fn(cx: &mut Context) -> Gc<'_> {
    Gc(&cx.0)
}

fn main() {
    let cx = &mut Context(7);
    let obj = test_fn(cx);
    let value_as_static = unsafe { unbind_for_rebind(obj) };
    let value = unsafe { rebind_by_ref(cx, value_as_static) };
    test_fn(cx);
    println!("{:?}", value);
}

You get this error:

error[E0502]: cannot borrow `*cx` as mutable because it is also borrowed as immutable
  --> src/main.rs:24:5
   |
23 |     let value = unsafe { rebind_by_ref(cx, value_as_static) };
   |                                        -- immutable borrow occurs here
24 |     test_fn(cx);
   |     ^^^^^^^^^^^ mutable borrow occurs here
25 |     println!("{:?}", value);
   |                      ----- immutable borrow later used here

I am still trying to grok the token solution you presented. I will have to look at it more. You seem to understand the type system better and how it can be used.

[Alan-Chen99]

You get this error:

error[E0502]: cannot borrow `*cx` as mutable because it is also borrowed as immutable
  --> src/main.rs:24:5
   |
23 |     let value = unsafe { rebind_by_ref(cx, value_as_static) };
   |                                        -- immutable borrow occurs here
24 |     test_fn(cx);
   |     ^^^^^^^^^^^ mutable borrow occurs here
25 |     println!("{:?}", value);
   |                      ----- immutable borrow later used here

This is as intended, right? We rebind! to get a non-rooted value, which is not supposed to live past a gc.

I am still trying to grok the token solution you presented. I will have to look at it more. You seem to understand the type system better and how it can be used.

I have actually only been learning more about the type system quite recently! It helps a lot to look at some self-referential crates; There seem to be a lot of them, with varying degrees of soundness...

The key idea is really here:

fn garbage_collect(State<_>, &mut Context) -> State<()>
fn function_that_may_gc(State<T>, &mut Context) -> State<R>

Since we don't expose any State constructor, anything we keep in a State could not have been gc'ed, thus any non-rooted objects in State must still be valid.
So this is simply solved, right? Not quite. We still need to provide a way for users to

1. modify whats in State
2. put a newly allocated Object into State

One way to do this is to rebind Object into State using a macro. This is fine, but it requires writing some unsafe code for any type T for State.
So I thought we can do better with a Token<'a>. Now we know exactly what is created in this closure: everything with 'a. So everything with 'a is safe to put into State. This lets the user use arbitrary T as State without unsafe.
Note that I don't think we can use &'a Context as Token here. This is because this let the user keep &'a Context as part of state, and then give us back an aliasing &mut Context.

[CeleritasCelery]

This is as intended, right? We rebind! to get a non-rooted value, which is not supposed to live past a gc.

rebinding and rooting are actually separate concerns. Rebind is only to work around this issue with the type system. Essentially we need to rebind whenever a function that takes a &mut Context returns an object, and then later we need to use Context immutably then use the object again. This only shows up occasionally, and if the Rust type system had been design differently (if you could downgrade a mutable reference), it would not be required at all.

Since we don't expose any State constructor, anything we keep in a State could not have been gc'ed, thus any non-rooted objects in State must still be valid.

So it sounds to me like State is essentially a collection of roots? Rather then passing in 5 rooted arguments you would put them all in State data structure and pass that?

So is this similar to cell-gc or gc-arena where they use a closure to create "heap mutation sessions" where no gc can occur and therefore it is safe to operate on variables? The closure keeps variables from escaping, which sounds like what you are trying to do with closures as well. That is my understanding of the Token approach.

[Alan-Chen99]

But this can't be right? what prevents an object returned by rebind! from being garbage collected?
The following currently segfaults:

let cons = list!["foo", 1, false, "end"; cx];
let cons = rebind!(cons, cx);
cx.garbage_collect(true);
dbg!(cons);

[Alan-Chen99]

My understanding is that rebind is supposed to change a mutable borrow to an immutable one, which prevents a gc but allows allocation

[CeleritasCelery]

The following currently segfaults:

oh snap you’re right! That’s not good. I think the issue is rebind_raw_ptr is not associating the lifetimes correctly.

[CeleritasCelery]

Okay I fixed the unsoundess bug you found. thank you!

The example you provided now correctly fails to compile.

what prevents an object returned by rebind! from being garbage collected?

because it is (now) tied to the immutable borrow of Context. It can't survive garbage collection without being rooted. Essentially we set it back to a "normal" object that you would get from something like cx.add("foo"). Otherwise it is in this much less useful state because the mutable borrow of Context must live as long as our object.

Like the lifetime misconception guide says "The re-borrowed shared ref has all the cons of a mut ref and all the cons of a shared ref and has the pros of neither." We use rebind! to get out of that undesirable state where we can't use Context.

[Alan-Chen99]

Nice! the transmute I gave above does the same thing, but you can also make them work with, say, vectors.

So is this similar to cell-gc or gc-arena where they use a closure to create "heap mutation sessions" where no gc can occur and therefore it is safe to operate on variables? The closure keeps variables from escaping, which sounds like what you are trying to do with closures as well. That is my understanding of the Token approach.

The Token approach is I think only similar in terms of the safety bound.

So it sounds to me like State is essentially a collection of roots? Rather then passing in 5 rooted arguments you would put them all in State data structure and pass that?

State is the opposite of root. In a garbage_collect, State is cleared:

fn garbage_collect(State<_>, &mut Context) -> State<()>

Due to this, you can stick anything in State: A RefCell of a closure that borrows from a refcell of a closure. whatever. State<T> just compiles to T, so its 0 overhead. So its a 0 overhead way of passing arguments (impossible rn) and giving return for functions that can gc.

The Token is there to prevent you from copying something out of state, do gc, and put that back into state.

[CeleritasCelery]

the transmute I gave above does the same thing, but you can also make them work with, say, vectors.

Can you make this sample code compile using transmutes? This will work with the raw conversion method. But I couldn't make it work with transmute.

State is the opposite of root. In a garbage_collect, State is cleared:
The Token is there to prevent you from copying something out of state, do gc, and put that back into state.

Hmm, interesting. So if I wanted to pass multiple arguments to a function I would create State<(arg1, arg2, arg3)>? Does that mean we would need to create functions to convert between all different possible types of State? I would have Also why wouldn't taking something out of State just bind it to Context? Similar to how taking something out of an Rt does. That seems like it could remove the need for the Token.

[Alan-Chen99]

Can you make #26 (comment) sample code compile using transmutes? This will work with the raw conversion method. But I couldn't make it work with transmute.

This isn't supposed to compile, right? If it does, you would garbage collect obj (its not rooted) and then print the dangling pointer.

Hmm, interesting. So if I wanted to pass multiple arguments to a function I would create State<(arg1, arg2, arg3)>? Does that mean we would need to create functions to convert between all different possible types of State? I would have Also why wouldn't taking something out of State just bind it to Context? Similar to how taking something out of an Rt does. That seems like it could remove the need for the Token.

When I wrote that API I imagined functions to look like this:

fn func_that_gc(state, cx) -> State<obj>
{
    let state: State<(obj, obj)> = function_that_gc_1(state, cx);
    let state: State<Vec<obj>> = function_that_gc_2(state.map(|(x, y), token| (x.car(), cons!(x.cdr(), y), rooted.bind(token))), cx);
    let state: State<obj> = state.map(|v, token| vector_to_list_nogc(v, token, cx));
    state
}

Where cons! wraps a alloc_cons(cx, token).

Note that you can still pass roots as arguments ofc.
To root I think we can have map_split(state, FnOnce ... -> <A, B>) -> (State, B) which lets you "split out a part" to root.

I think you are right that "rebinding" is more suitable here:

// obj1 and obj2 borrow from cx or empty_state (bad, this must use macros) or another global token that also inhibits gc
let (empty_state, (obj1, obj2)) = function_that_gc_1(state, cx).split_state(cx)
function_that_gc_2(to_state(empty_state, x.car(), cons!(x.cdr(), y), rooted.bind(cx)), cx)

Kind of a seperate idea is I think ideally we use &mut Context instead of &Context for allocations and use something else to track permissions, since we don't need a refcell indirection. not sure if this really makes a difference.

[CeleritasCelery]

This isn't supposed to compile, right? If it does, you would garbage collect obj (its not rooted) and then print the dangling pointer.

Touche. Turns out you were right on both accounts. That code shouldn't compile and transmute does work for rebind!. I swear I tested that, but clearly didn't do it correctly.

When I wrote that API I imagined functions to look like this:

Hmm that is really interesting. It has the advantage that you can pass arguments without rooting them and you don't need to rebind the return value. I wonder if rust would optimize a struct of a tuple for the argument as well as it optimizes individual arguments. Seems like the tradeoff is increased verbosity though.

Kind of a seperate idea is I think ideally we use &mut Context instead of &Context for allocations and use something else to track permissions, since we don't need a refcell indirection. not sure if this really makes a difference.

Are you thinking of if it makes a difference for performance? Allocation will probably be on the hot path so I think it would. But another way we could solve this is use UnsafeCell and have "mutation functions". Mutating the block can only happen within those functions, and we never expose references outside of the functions. I don't think it could ever be made sound as a public API, but it could work for Context.

[Alan-Chen99]

UnsafeCell and &mut should make a difference in theory. In practice it doesn't (for now), due to things like rust-lang/rust#71354. It will probably make a difference in future versions of rust/llvm

[Alan-Chen99]

Seems like the tradeoff is increased verbosity though

Yea, the verbosity is no good. If we do adopt this we need a good abstraction over this using macros. I will need to think more on that.