That's a good point, I hadn't considered the possibility that something could become tenured during the borrow.
Niko On Thu, Jul 11, 2013 at 04:00:47PM -0700, Felix Klock wrote: > 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! > > Cheers, > -Felix > > > > > ----- Original Message ----- > From: "Niko Matsakis" <[email protected]> > To: "Patrick Walton" <[email protected]> > Cc: [email protected] > 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 > 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 > _______________________________________________ > Rust-dev mailing list > [email protected] > https://mail.mozilla.org/listinfo/rust-dev _______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
