Also, to spell out a bit of background that may not be clear, if I
understand pcwalton correctly, the problem scenario he is envisioning
is as follows. Imagine that you have a function `modify` that takes a
borrowed pointer to a cell and mutates its contents:
fn modify(x: &Cell<@T>, y: @T) {
*x.as_mut() = y;
}
Naturally, `modify)` could be used with a cell that resides
anywhere, such as the stack etc. But this cell might also
reside in managed data:
let tenured: @Cell<@T> = ...;
let nursery: @T = @...;
modify(&*tenured, nursery)
In this scenario, we are creating an edge from a tenured object to one
in the nursery, but when do we trip the write guard? We borrowed the
tenured object immutably, so there is no write guard there. The write
place would be in `modify()`, but `modify()` is not specific to
managed data, so we don't want to add any sorts of write guards there,
as they would affect all writes.
There are various options I see to rule out this scenario:
- Use MMU for write barriers.
- Add write guards to `modify()` and try to eliminate them statically
whenever possible (inter-procedural analysis).
- Forbid managed data from *owning* values with internal mutation, like `Cell`
or `RcMut`.
- Forbid `Cell` and friends from containing managed data.
- Don't use a GC scheme that requires write barriers.
Niko
On Wed, Jul 10, 2013 at 11:32:08AM -0700, Patrick Walton wrote:
> 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
> _______________________________________________
> 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
