You might be interested to learn about the MMTk [1, 2] project which aspires to be a language agnostic library for garbage collection. It was used by the LXR authors [3] to develop a GC that beat production OpenJDK 11 collectors in throughput and latency. I believe they have work on a bunch of bindings to other VMs underway as well such as V8 (JavaScript), MRI (Ruby), Julia, GHC (Haskell), and PyPy (Python)!
I don't understand how the rooting works here. Usually GC languages make the distinction between a "pointer" which is a reference into the heap, and a "root" which is something known to the GC that keeps a pointer live. I don't see that distinction here. I think this is what the author is saying:
1. You can allocate from an arena; you get an object.
2. Allocated objects may be freed when a GC is triggered, unless they are added as a root. It is your responsibility to add your object as a root.
3. Roots are in a LIFO stack and cannot be moved.
Ok, but we never actually see the root type. For example:
let rooted: Vec<Object<'root>> = ...; // we have a vec of root objects
let object: Object<'arena> = arena.add("new"); // object is bound to arena
rooted.push(object); // object is now bound to rooted
arena.garbage_collect(); // Object is marked as live and not freed
How is anything rooted here? The lifetime changed from 'arena to 'root but I don't see a root being created.
Some other misc questions:
What if instead of storing them as a map, we store them as a stack instead? When something is rooted, it is pushed on the stack. When it drops, it is popped from the stack.
But later we see roots not obeying a LIFO order, under "Preventing escapes" where roots are dynamically created and destroyed in an arbitrary order.
The function takes a &mut Arena, and at the end it returns an Object with the same lifetime
But earlier it says "we have to make sure the object can’t move." I'm confused what is being returned here: an object reference, or a root.
> How is anything rooted here? The lifetime changed from 'arena to 'root but I don't see a root being created.
In this example, the Vec has been rooted previously. So pushing an object into the Vec will make it "transitively" rooted (accessible from the root). You would root a struct with the root_struct![1] macro, which works very similar to the root! macro shown in the post.
However you made you realize one error; The rooted `Vec` in the example you pointed is a by value type, but in the implementation you can only get references to rooted structs, so that example needs to be updated.
> But later we see roots not obeying a LIFO order, under "Preventing escapes" where roots are dynamically created and destroyed in an arbitrary order.
Objects are just a copyable wrapper around a pointer, so they are not the part that has the LIFO semantics. inside the root! macro[2] there is a `StackRoot` type that is the actual "root". The object just borrows from that so that is has a 'root lifetime and is valid post gc. The actual root struct is not exposed outside of the macro.
I hope this makes the distinction between "roots" and "objects" clearer. Objects are just pointers to heap data. When we root an object we store the data it points to on the root stack and create a new `StackRoot`. Then we say this object is rooted. But the struct that "does the rooting" is inside the macro and not exposed. Rooting a struct works similarly.
The existence of the StackRoot type is definitely a missing piece of the puzzle, thank you. So we have Object and StackRoot. But then what is a "root object?"
let rooted: Vec<Object<'root>> = ...; // we have a vec of root objects
I would expect this vector to just contain Objects?
I think conceptually you have two different Object types: a "dangling" Object that is subject to collection, and a "rooted" Object which is referenced by a root stored in the RootSet. Part of my confusion is that there's no vocabulary to distinguish these. In this code:
root!(value, gc)
Visually it appears to "do something" to value but in fact there's two different variables, with two different types, both named 'value'. It would be clearer at least to me to reify that by giving them different types instead of calling both Object.
In a moving GC this distinction becomes unavoidable: dangling objects are raw pointers, while rooted objects refer to the root location itself and require double indirection to access.
Anyways it's just a suggestion, take it or leave it. It's very cool how Rust's lifetimes let you enforce that no collections happen while an Object dangles.
One last thought: because you're already on the hook for passing in the GC when dereferencing an Object, you could exploit this by making Object references just a 32 bit offset, relative to the GC's heap. This would let you save some memory.
I had hard time trying to explain the concept without getting deep in the implementation. You have given me some ideas of how I can explain things clearer. Mentioning StackRoot seems like a critical part.
> So we have Object and StackRoot. But then what is a "root object?"
If you think of Object's as pointer to heap data, then "root object" is just a pointer to heap data where that data also has a entry in the root set pointing to it (the data is rooted). You are right that the object does not change types, only rebinds the lifetime. Initially I actually had them as two separate types; `RootObject` and `Object`. But this ended up making things harder because now I had to create two version of many functions, one for "dangling objects" and another for "rooted objects". And I was converting between the two types all the time. Or I could use generic code, but generic programming is more painful then concrete functions. I ended up unifying them since they had nearly identical properties, and they are only distinguished by lifetimes (bound to the GC or to a StackRoot). But better and more consistent nomenclature would make things more understandable.
> In a moving GC this distinction becomes unavoidable: dangling objects are raw pointers, while rooted objects refer to the root location itself and require double indirection to access.
Is that always true? My understanding is that generally moving GC's will put a forwarding pointer at the old address and update all references during collection. I want to make this GC moving at some point and didn't think the rooting system would be a limitation.
> because you're already on the hook for passing in the GC when dereferencing an Object, you could exploit this by making Object references just a 32 bit offset
You don't need a reference to the GC to dereference an object. An object is always safe to deference. But you do need to pass the GC to get a field of something in the GC heap (i.e. something that the object is pointing to, like a vector or a Cons cell). This is because GC heap allocated types use interior mutability and something could change under your nose and take an object that was previously reachable from a root and make it no longer reachable (Similar to my Preventing Escapes section). Therefore we require that taking the field of GC heap allocated type takes a reference to GC, and therefore makes it "dangling" by default.
This was an advantage of the 2-type rooting systems I mentioned earlier. If we had a "dangling object" type we didn't need to take reference to the GC to access a field because we know that it's lifetime was borrowed from the GC already (i.e. It was already dangling).
But I had not thought about using a 32-bit handle. I will look into that once I actually start using the Allocator API.
Thanks for the reply, what you wrote makes sense to me. I want to expand on the copying GC ideas:
> I want to make this GC moving at some point and didn't think the rooting system would be a limitation.
Currently the rune RootSet is "a list of pointers to be treated as roots" and so long as the pointer is in the list, the GC will not collect it, and you are free to pass around copies of that pointer. But if the heap object were to be moved, the GC could only update the pointers in the RootSet, not those on the native C (err, Rust) stack. So you would get dangling pointers, which is bad.
One solution for this is double indirection:
1. StackRoot changes from "a pointer which should be rooted" to "a location in memory containing a pointer which should be rooted, and this location is known and updated by the GC."
2. You stop passing around copies of pointers, you pass around pointers to a StackRoot which itself contains a pointer. We do this because the GC may change the pointer stored in a StackRoot at any collection point. Hence double indirection: we have a pointer to a location which is known by the GC, which in turn contains a pointer to our data.
This approach is mind-bending and took me a while to grok.
One thing I'm trying to understand is: Is this a garbage collector for Rust; or is this a garbage collector implemented in Rust for another environment.
It's confusing because the author refers to their Emacs VM; but then refers to Rc in Rust.
It’s currently the latter, but the author believes that this approach could be cleaned up and generalised to also be the former. I believe it would then be a general purpose GC library in Rust that could be used for Rust code or any environment written in Rust.
The latter, implemented in Rust (in my understanding).
They bring up Rc<T> because using reference counting as their implementation is in theory a possibility, which they then quickly (and rightfully, imho) dismiss.
Although you probably could use it for something else, Boa[1] is a good demonstration of this (it uses the GC crate, but the same principle probably applies).
I talk little bit about that in my introductory post[1]. Basically my interest in Emacs, Rust, and interpreters came to together and I decided to see what I could do. I was also inspired by the remacs project[2] and I think Rust has a lot to offer as dynamic language backend. I don't know where this will go, but I am going to continue to work on it.
This is cute but modern concurrent garbage collectors like the ones used in VMs and languages such as Go are way more complicated. In fact, the GC can be the most difficult aspect of an entire environment including the compiler.
[1]: https://www.mmtk.io/
[2]: https://github.com/mmtk/
[3]: https://users.cecs.anu.edu.au/~steveb/pubs/papers/lxr-pldi-2...