Garbage collected handles are lifetime-contravariant

18 points by aapoalas

rpjohnst

Contravariance has nothing to do with GC or self-reference. The mirror images of covariance and contravariance come from the mirror between producers and consumers - producing a value of type &'a T simultaneously produces a value with all shorter lifetimes, and vice versa a consumer of a value of type &'a T automatically accepts a value of any longer lifetime. But both forms of variance are really sort of a distraction here.

The problem with the initial example here is not that you should be allowed to assign a Handle<'local, T> into a place of type Handle<'external, T>. If 'local is, as you describe, a "lifetime during which it is guaranteed that garbage collection does not happen," then contravariance would allow you to store it in e.g. a static UNRELATED: Mutex<Handle<'static, T>>, essentially claiming that GC will never happen again.

The actual problem is on the other end: 'external is too long. The entire point of the GC heap is that references written into it will survive GCs, so it doesn't make any sense to use the type Handle<'external, T> for those references! The most natural type for an in-heap reference like this wouldn't have a lifetime in the first place, because its target is owned by the heap- just like Rc<T>.

The problem with just using owning references is that the GC needs to invalidate borrows derived from any of them, all at once, and then restore access to them again afterwards. From this perspective, it should be clear why neither 'local nor 'external makes any sense for in-heap references- we're trying to eat our cake (invalidate the borrows) and have it too (give back access to the pointers).

Fundamentally what we need is some way to connect all the borrows formed before a GC, so they can all be invalidated, but also keep them distinct from the in-heap references, so those can survive. The only reason in-heap lifetimes get involved at this point (as in the generative/branded lifetimes approach) is really more of a clever hack than anything to do with what lifetimes were designed to model- those lifetimes do not signify how long the in-heap references are valid, but they do control the lifetimes of out-of-heap borrows, and are effectively reset after each GC.

aapoalas

Contravariance has nothing to do with GC or self-reference.

Of course it doesn't have anything fundamentally to do with GC or self-referential data-structures, but that doesn't mean it cannot be a useful tool in modeling them.

contravariance would allow you to store it in e.g. a static UNRELATED: Mutex<Handle<'static, T>>, essentially claiming that GC will never happen again.

Yup, there are branding and API design issues to be solved as well, but this is present with most handle representations and has nothing to do with contravariance: using pointer handles you can verify the address points into the arena, but once you let go of pointers and instead eg. use 16-bit offsets like V8 does, you're out in the wilderness. You have to either brand everything related to the same arena, or have to simply trust that no one does anything weird.

When you're given a Handle out of that Mutex, how do you trust that they had a valid Handle to give in the first place? Branding can help make sure you're at least talking about the same arena, but the validity of the Handle is simply something you have to take for granted. In this sense, one interpretation that I've been using for contravariant Handles is that they are not a guarantee of validity but a promise to uphold it, and thus unsafe to create. Creating the Handle<'static, T> to put into the Mutex required you to give a promise that you will indeed keep it valid for 'static or it is dropped.

it doesn't make any sense to use the type Handle<'external, T> for those references! The most natural type for an in-heap reference like this wouldn't have a lifetime in the first place, because its target is owned by the heap

This is the usual decision indeed; just use raw pointers or whatever. But! Doing that doesn't change the fact that fundamentally these are still handles, and handles are non-owning references. Especially when you start interacting with the stack and giving out handles from the heap, then the difference between an in-heap handle and an on-stack handle seems superficial at best: you have some RawHandle<T> on the heap which is very possibly byte-wise identical to a Handle<'_, T>, and when giving it to the stack you copy its data, change the type, and somehow attach it to some lifetime. When writing an on-stack handle into the heap, you copy out the data, change the type, and cast out the lifetime which is very much equivalent to turning '_ into 'static.

What was then the point of the separate on-heap type? Did it make things safer? No, it doesn't seem so. Did it make things simpler? Probably not.

And for the types on the heap, the hope here is that contravariant references might provide for some modicum of useful guarantees for the person writing the heap / GC code. That would definitely be better than just RawHandle<T>.

just using owning references

I don't understand: there are no owning references here.

anything to do with what lifetimes were designed to model

Yup, this isn't something lifetimes were designed for but mathematics often ends describing useful things even when (or especially when) outside of the original intended derivation. So too, I believe, with covariant and contravariant references. eg. If we take the most literalist approach to GC handles using contravariant references, they could be read as "this points to some value with a lifetime 'a that is or was valid for some shorter lifetime 'b but we don't know that shorter lifetime"; we might as well decide that the 'b is empty ie. that the Value was effectively never valid. With this, any read-like usage of the handle is unsafe so let's mark it unsafe! This is going to look be terrible but it does show a true thing: handles (that cannot be checked for validity by their value alone) are fundamentally unsafe and using them is an act of trust in both whoever gave you that handle, and anyone who held it before that. Safety becomes a global property again.

Once you see all the unsafe, that's when you start thinking about ways to do validation so that you can either reduce the blast radius, or eliminate the unsafety.

In other words, I think contravariant references might be a useful tool for modeling about unsafe systems based on trust, and for writing code for these systems.
- rpjohnst
  
  When you're given a Handle out of that Mutex, how do you trust that they had a valid Handle to give in the first place? Branding can help make sure you're at least talking about the same arena, but the validity of the Handle is simply something you have to take for granted.
  
  No, it is not. It is totally possible to design an actually-sound handle API that does not have this problem.
  
  And for the types on the heap, the hope here is that contravariant references might provide for some modicum of useful guarantees for the person writing the heap / GC code.
  
  This is exactly what I am disputing. Contravariance does not provide any useful guarantees for either the person implementing the GC or the person using it, because it doesn't correspond to any actual rules about how the heap works. You would be better off just using lifetime-less handles, because then there would be no risk of accidentally allowing unsoundness via the implied bounds on the T of Handle<'a, T>.
  
  Yup, this isn't something lifetimes were designed for but mathematics often ends describing useful things even when (or especially when) outside of the original intended derivation.
  
  No, the way people use lifetimes to (correctly and soundly) model GC references is by going out of their way to disable a bunch of their behaviors. That's essentially the opposite of "mathematics ends up describing useful things outside of the original intent." Rather, lifetimes simply happen to be Rust's only form of non-monomorphized type parameter, which is what people typically use in other languages for this sort of thing.
  - aapoalas
    
    No, it is not. It is totally possible to design an actually-sound handle API that does not have this problem.
    
    Can you really design a sound API that uses unrooted handles? First we have to solve the "mixing arenas" problem, so that requires branding. But once we have that, I don't see a way to make the branded unrooted handles safe in the Rust of today, at least not if you're passing them as normal parameters. If you only have a Context parameter that acts as an API to read parameters to write the function result value then I can kind of see how it might work... but it seems like at least you'd need to always create a new on-stack Context that gets passed to the next function over by reference and contains references to the parameters on the stack. You could then get then invalidate all references to the Context when a GC safepoint is reached, but you also then need to track if a GC safepoint has been reached to make it impossible to re-read arguments after GC has happened. If you don't do that, then it's possible to read the handles after GC at which point they're stale. And if you don't want them to go stale, then you need to trace the Context stack, at which point these are no longer unrooted handles.
    
    Contravariance does not provide any useful guarantees for either the person implementing the GC or the person using it
    
    I think you're in large parts right but also a little wrong here. Contravariance has absolutely terrible sharp edges (especially while Rust cannot reason about lifetime parameters that should end within the function call), but there are some guarantees it can give. First, if we give our heap a lower contravariant lifetime 'external rather than using 'static, it means that the heap will not accept any Handle that has been made 'static. Similarly, if our APIs take their unrooted handles using a lifetime that is either that same 'external or (preferably) a local 'gc that is automatically bound to a normal covariant Gc marker parameter's existence (and that is then used through a &mut Gc at GC safepoints, invalidating the 'gc lifetime), then you cannot call APIs with a 'static Handle or return one from your own call either. The only thing you can then do with a 'static Handle is to create it in your function and drop it within your function, but you cannot access any data with it nor can you "pawn" it off to someone else and pretend like it's a valid Handle. (This has actually made it clear to me that indeed I must not use 'static as the lifetime of the heap but must have an 'external lifetime.) Unsafe Rust can of course transmute the lifetime to something else, but that goes for any lifetime, contravariant or not.
    
    EDIT: I found a loophole here: as long as we can name the 'external or 'gc lifetime, we can make a local copy of a "bound" Handle and expand it to Handle<'external> or Handle<'gc> and return it from our function even after GC safepoints have happened. This is a problem.
    
    EDIT 2: Oh actually even worse: you don't even need to name a lifetime, just let bad_handle = good_handle; is enough to get an "lifetime-untracked" unrooted handle :/ No Clone or Copy for me I guess...?
    
    While we still don't have the feature of binding a parameter's lifetime to another, it is apparently something that Polonius might introduce. And until we have it, proc macros or dylints might be able to plug the gap.
    
    You would be better off just using lifetime-less handles, because then there would be no risk of accidentally allowing unsoundness via the implied bounds on the T of Handle<'a, T>.
    
    There is always the risk of accidentally allowing unsoundness whenever you're writing unsafe Rust.
    
    No, the way people use lifetimes to (correctly and soundly) model GC references is by going out of their way to disable a bunch of their behaviors.
    
    I tried to look and couldn't at least immediately find a library that implements unrooted handles with any lifetimes. One library did indeed provide unrooted handles but simply panicked on misuse.
    
    rpjohnst
    
    Can you really design a sound API that uses unrooted handles?
    
    Yes- for example the gc-arena post by kyren (that I linked in my first reply) describes an approach that uses a Gc<'gc, T> type, which is branded but implements Copy and Deref, for both in-heap and out-of-heap references. The brand not only ensures that heaps are not mixed, but also that no unrooted references are held across a safepoint. The key is the Arena<R>::mutate method with this (slightly simplified) signature:
    
    pub fn mutate<T, F>(&self, f: F) -> T where F: for<'gc> FnOnce(&'gc R<'gc>) -> T
    
    Safepoints happen between calls to mutate, and never during. Each call gives you access to the root set of the heap R<'gc> with a fresh, distinct, invariant brand 'gc. You can allocate, read, write, and pass around Gc<'gc, T>s freely, because the brand ensures they cannot escape the current call to mutate except by being stored somewhere reachable from R<'gc>.
    
    there are some guarantees it can give
    
    These only incidentally have anything to do with contravariance, via thinking of invariance as simultaneous covariance+contravariance. If you only have one or the other then things quickly fall apart in the ways you are seeing.