[rust-dev] Incremental and generational GC

Patrick Walton pwalton at mozilla.com
Wed Jul 10 11:32:08 PDT 2013


Hi everyone,

(Warning: GC pointy-headedness ahead.)

I've been thinking about what will be needed to support incremental and 
generational GC in Rust. To be clear, I don't think we should block on 
it now, but we should not make it unduly difficult for us to implement 
in the future.

The hard parts of incremental and generational GC are the barriers. 
There is a different write barrier regarded for both. (I'm assuming 
incremental-update IGC, not snapshot-at-the-beginning, which is a harder 
barrier.)

First, some terminology. Consider this picture:

     +-->B
     |
     A       C

A is the "referrer". Suppose that the mutator mutates it to this:

         B

     A------>C

C is the "referent".

For IGC and GGC, we need some sort of barrier.

For incremental GC, we must maintain the tri-color invariant, which 
means that a black object must never point to a white object. There are 
two basic ways to do this: either a write barrier graying a white object 
referent or graying a black object referrer. In Rust, the latter would 
be the easiest to implement: whenever you borrow an `@mut` to `&mut` 
(which is what you need to do to mutate) we can gray the object if it's 
black. This does mean that we need to make sure that all contents of 
`@mut` are Freeze; otherwise, we won't trip the barrier.

For generational GC, we must ensure that objects in the nursery pointed 
to by the tenured generation are either added to a remembered set or 
tenured. This is harder in Rust because we have to know both the 
generation of the referrer and the referent simultaneously. I believe 
that conservatively tenuring all objects that are mutated would be 
overconservative and defeat much of the purpose of GGC.

The only thing that I can think of that would work is to use the MMU and 
do the generational GC barriers on a per-page basis. I believe that this 
is what Boehm does in its GGC mode. This to me seems the most risky part 
of this; I'm not sure what the performance implications of this are.

Doing this will keep `Gc` and `GcMut` implicitly copyable without custom 
copy constructors, which is nice. It is true that we will not be able to 
perform the change that was agreed on to change `GcMut<T>` to 
`Gc<Cell<T>>`, since `Cell<T>` is not `Freeze`.

Thoughts?

Patrick


More information about the Rust-dev mailing list