Hmm, on IRC strcat pointed out another option. Imagine that we pushed
all mutability into `Cell`. Then when `Cell` borrows as mut, it could
have some code like this:
if contains_managed::<T>() {
// contains_managed is an intrinsic test of the type T
write_barrier();
}
We would have to design the write barrier code to be able to cheaply
check whether a given pointer is managed or not, but that's not a big
deal (this requirement is already present).
I didn't list this option because I considered it to be the same as
guarding all writes, but of course it is not. It imposes additional
overhead on all users of Cell, but *only* on users of Cell, and only
when the values in the cell contain managed pointers.
Technically, this design does not require pushing mutability into
`Cell`, but if we do that we gain the advantage that Cell is the only
one who has to worry about tripping 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
