[rust-dev] Incremental and generational GC

Niko Matsakis niko at alum.mit.edu
Thu Jul 11 12:12:45 PDT 2013


Some comments inline (mostly for my own clarification).

> * Whenever we borrow an `@mut` to `&mut`, add it to a "borrowed set"
> for the duration of the borrow.

Presuming we adopt `Cell` in place of `@mut`, then this changes to
"when borrowing a Cell as mutable, check if the cell is located within
managed memory and add the cell to the borrowed set".

It is interesting to note that if we adopt `Cell`, then the borrowed
and remembered sets need not be sets of managed boxes but rather can
be sets of cells. The distinction is only that you don't have to scan
the full object. It may be better to ignore this fact.

> * Objects in the borrowed set are grayed before each incremental GC slice.

The thesis that Graydon forwarded uses a different approach. If we
adopted their approach, I think we would (1) immediately promote all
pages reachable from stack and (2) promote any managed boxes as soon
as they are borrowed (whether mutably or immutably). Promoting here
means pinning the containing pages and then scanning their contents:
any nursery objects found within would be copied into tenured pages
and rewritten. This involves a read barrier, which seems undesirable.

If we limit ourselves to write barriers, as you suggested, then what
you wrote sounds about right. Presumably we still begin by pinning all
pages reachable from the stack. We then do some work and eventually
resume execution. When a cell in a block object is mutably borrowed,
we pin its pages and mark it grey. Whenever we wish to resume
scanning, we must re-scan the stack because the user may have borrowed
white objects onto the stack and they must now be pinned.

OK, that's a bit hand-wavy, but I think I can see how it could work.

> * Objects in the borrowed set are scanned during each minor
> collection, even if they're tenured.

I wouldn't add a non-tenured object to the borrowed set. What's the
point.

> * When removing an object from the borrowed set (because the borrowed
> is done), add it to a remembered set. Objects in the remembered set
> are scanned during minor collections.

You only need to add to the remembered set if the new value contains
objects in the nursery. This amounts to eagerly scanning the cell
rather than waiting until the minor collection.  I'm not sure if it's
worth it, but if you don't do it, there is no reason to distinguish
the borrowed and remembered sets.

> * There are no other write barriers.

Right.

> I believe (although I haven't thought about it too hard) that this
> suffices to make generational and incremental GC work in Rust's
> mostly-copying setting.

Agreed.


Niko


More information about the Rust-dev mailing list