The goal of a GC is to automatically manage memory. When something isn't being used anymore, it should be freed. But that implies it should never free anything that is still in use, because that could lead to a use-after-free. You don't typically think about this when using a language with garbage collection, because it has managed references which the compiler and GC know about and so it all just works and you as the user don't have to worry that something will be freed from under your nose.
But it's different when you're the one implementing the language and its runtime. Remember how Crafting Interpreters does it, with pushing temporary values onto the runtime stack so that the GC can find them there. Which is very error-prone.
That's where what I'm trying to do comes in. There are already a few Rust GC implementations that are memory safe, in that there's no possible way to introduce a use-after-free without unsafe code, because the garbage collector is made aware of every reference for as long as you're actually using it in Rust code.
I'm going to ignore the existence of other safe Rust GCs, because this wall of text is already quite long, but I've definitely looked at them and they're all limited in some way that I'm not happy with. It's about tradeoffs (and I will explain the downside of my approach in a bit).
The approach I'm using is actually just stolen from V8. They use the concept of "handles", which is a double indirection for each object (*mut *mut Object). These handles are allocated from handle scopes. Each handle is a pointer to a slot in some block of memory, which holds a pointer to the actual object. The collector can trace through the live handles by iterating over all the slots in that block of memory. This means that a handle, as long as its alive, is always safe to dereference.
The problem with it in V8 is that it's... C++. C++ does not have the concept of lifetimes baked into the language like Rust. But conceptually, a handle's lifetime is tied to the handle scope it was allocated from, so as long as we can re-implement all this in Rust and have a Handle<'a, T> type where 'a is the invariant (must be exactly equal to) lifetime of its scope, then we can actually ensure the references aren't used incorrectly at compile-time, making it completely memory safe to use this API to implement a language runtime.
The downsides of this approach are:
- It's really easy to forget to allocate a new scope, and end up allocating way too many handles, such as in a loop or when recursing.
- There is a small fixed cost for allocating a new scope. It's not a heap allocation, as scopes are allocated on the stack, but it's still a cost you have to pay for once per basically every function and loop.
- Each reference held on the Rust stack is a double indirection instead of a single indirection. Because of how page tables work, this is not that big of a deal, but it does still add up over time, and generally slows everything down. I have yet to measure this properly, but seeing as V8 uses this approach and their performance is fine (even
--jitless), it should be ok.
Now as for the reasons why I'm using this approach:
- You can run the collector at any point in your mutator code safely. This means you can sequence your code however you see fit. (In
kyren/gc-arena, you have to yield to the collector completely, in order to clear all references from the Rust stack, which requires managing "fuel" so you know when to yield and/or restructuring everything to be aFuture. That can be cool, but it's really really inefficient compared to straight-line synchronous code.piccolo, which usesgc-arena, is typically 10-20x slower than PUC Rio Lua 5.4) Localdoes not have aDropimplementation. Which means neither doesValue, and both can be passed around like they're just integers!- It is precise, because the GC is always aware of every single reference to a managed object, which has implications for what kind of algorithm you can implement. The precise ones are always much faster than the conservative ones, and require far less bookkeeping. As far as I know, it's actually not possible to implement a conservative collector safely in Rust because of how Rust references work, but I don't understand it well enough to explain why.
I've got something that looks alright, but still struggling with ways to make dereferencing GC'd references stored in fields safe. The idea is that a member reference should not be tied by any particular lifetime, so a struct with member references doesn't need a lifetime parameter. It should only be possible to dereference those member references given a handle (Local) to the parent object:
struct Child { value: i32 }
struct Parent { child: Member<Child> }
let child: Local<Child> = scope.alloc(Child { value: 100 });
let parent: Local<Parent> = scope.alloc(Parent { child: Member::from(child) });
drop(child); // imagine that this means `child` is no longer reachable from the stack
// (even though in reality it is still reachable because of how the scoping mechanism works)
scope.collect_all(); // run a full collection - this did not collect `child`,
// because it is still reachable through `parent`.
// but now I need a way to access `parent.child.value` in a way that guarantees that
// it goes through a `Local<Parent>`.
// One possible approach is to do something similar to `RefCell's` `Ref::map`:
// `parent` is always safe to dereference, because it's behind a live `Local`.
// So we take advantage of that property and have it return a reference to the
// `Member<Child>`. The closure ensures that the lifetime of the `&'a Member<Child>` and lifetime of `&'a Parent` are the same for some lifetime `'a` (the lifetime `'a` is invariant).
let child: Local<Child> = Local::map(scope, parent, |parent| &parent.child);
// we can now dereference `child` safelyThe code using map is kind of awful, but in theory it can be hidden behind a getter method on parent itself, or some kind of macro. Another issue is that child is now placed into a fresh local. It would be nice if it was possible to instead retrieve a kind of "raw" reference to the member which does not go through the extra indirection.
This actually still leaves one huge problem though, which is that constructing a Member from a Local is currently unsafe. You can't guarantee that the Member which you're storing inside of an object is actually still live, because you can trivially stash it away in a place where the GC won't find it without using any unsafe code, because Member is 'static. And then you have a dangling reference which you can use to wreak havoc by placing it inside of a live object. I haven't come up with a good API to allocate an object and initialize its member reference fields from locals at the same time.
In order to make constructing a Member safe, I have to find a way to guarantee that the Local it is constructed from lasts beyond the point where the Member is placed into some other object and the object is itself put onto the managed heap and behind a Local.
// OK, because `Local<Child>` is still alive when `Local<Parent>` is created from it
let scope = &mut Scope::new(ctx);
let child: Local<Child> = scope.alloc(Child { value: 100 });
let parent: Local<Parent> = scope.alloc(Parent { child: Member::from(child) });
// NOT OK, because `Local<Child>` is gone by the time we place it in `parent`
let child: Member<Child> = {
let scope = &mut Scope::new(ctx);
Member::from(scope.alloc(Child { value: 100 }))
// `scope` dropped here, and with it the `Child` as well
};
let scope = &mut Scope::new(ctx);
let other = scope.alloc(SomethingElse); // this may trigger a collection
let parent: Local<Parent> = scope.alloc(Parent { child });I need something that supports the above, but prevents what's happening below... Which is tricky
I thought about using some kind of proc macro that generates a constructor for you, or some kind of declarative macro that performs both the allocation and initialization for you so that you don't call Member::from yourself