[rust-dev] Incremental and generational GC

Felix Klock pnkfelix at mozilla.com
Thu Jul 11 16:00:47 PDT 2013

Niko (cc'ing Patrick and rust-dev; resending from correct account)-

> > * 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.

What if (1.) the borrowed-object is in the nursery at the time of the borrow, and (2.) then is tenured during a minor gc that occurs during the dynamic extent of the borrow, and (3.) there are more writes to the newly tenured object during the dynamic extent of the borrow?

Or in (rough) code:

let cell : &Cell<T> = ...;    // cell is young and in the nursery
let ref : &T = cell.as_mut(); // cell is still in the nursery
<minor gc> // cell is tenured into the older generation, and has no refs into nursery
...        // (i.e. its referents in nursery are also tenured here), so cell is not
...        // added to remembered-set nor borrowed-set.
*ref = new_infant(); // now cell is in tenured space and has a ref to infant in nursery;
...                  // but there is no meta-data telling GC to scan cell at next GC...
<minor gc>           // Nothing keeping baby alive.
compute(*ref);       // Boom!


----- Original Message -----
From: "Niko Matsakis" <niko at alum.mit.edu>
To: "Patrick Walton" <pwalton at mozilla.com>
Cc: rust-dev at mozilla.org
Sent: Thursday, July 11, 2013 9:12:45 PM
Subject: Re: [rust-dev] Incremental and generational GC

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

> * 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.


> 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.


Rust-dev mailing list
Rust-dev at mozilla.org

More information about the Rust-dev mailing list