6 ms·

Has there been any work on how to leverage Rust's strengths for a GC language implementation? For example, Rust assumes unique ownership for mutable values; how

Has there been any work on how to leverage Rust's strengths for a GC language implementation? For example, Rust assumes unique ownership for mutable values; how do you express that the value is also reachable by the GC?

saagarjha 6y ago
I’m not sure I follow. Are you suggesting the addition of multiple mutable ownership of values to Rust, managed by a garbage collector?
- ridiculous_fish 6y ago
  No, I am talking about writing Rust code that refers to objects on a GC-managed heap. For example, assume v8-ish semantics: let mut cell = allocate(0.0); let counter : &mut f64 = cell.as_mut_ref(); *counter += 1; stuff(); *counter -= 1; Here `stuff()` may trigger further allocations which result in moving `cell`, leaving `counter` dangling.
  - saagarjha 6y ago
    Ah. I am not a Rust expert but I think the language might actually support this sort of construct (though it might be inefficient to implement), as IIRC if you want something to stay at a fixed place in memory you need to “pin” it there.
  - pirocks 6y ago
    Surely they way most gcs achieve this is by asking you to tell the gc when you aquire a reference to an object, and tell it again when you no longer need it. You could do that with a custom implementation of drop in rust.
Falell 6y ago
This isn't really directly related to your question, but I recall hearing that in Servo and Firefox, the usage of Rust is limited as it gets close to the DOM specifically because of interactions with the JS engine and its separate garbage collector, which Rust does not understand. Without any more specific knowledge, I bet the way a generational garbage collector moves data around really messes with Rust's view of the world...
monadic2 6y ago
If by GC you’re referring to its reference counting, either by Rc or Arc, there is no GC reachability beyond the reference counting. The responsibility for counting the contained object and dropping (cleanup before dealloc) is up to the type, either Rc or Arc (a stands for atomic, not automatic, as both are “automatic” in the sense that you never need to manually increment or decrement a reference). the owned, mutable object would contain the type information necessary to generate the right Rc calls ay the right time, but a distinct type is necessary to encapsulate the behavior. There are also escape hatches, between unsafe leaking and the RefCell type, to provide “interior mutability”, i.e. mutable aliasing via an without the memory safety issues which come with this. Note I have only had to use the unsafe bits when passing memory up to a c stack. I don’t believe there is a tracing GC implementation in the standard library, although I’ve heard plenty of discussion and you can find some simple implementations on crates.io. However, I would assume there would need to be some language changes to properly account for assumptions on how the Drop (free) functionality fires, not to mention significant backend work for tracing to work.
- ridiculous_fish 6y ago
  Let's put it this way: if you have a &mut to a heap allocated object (Box, whatever), you pretend it's unique, BUT its contents are also reachable by the global allocator, say, malloc. So it's not really a unique reference. If you allocate something new, Rust pretends it is independent, assuming that malloc won't muck with the other objects it knows about. What if we relax that assumption? Allocations may perturb other allocations - that's how moving GC heaps work! Can that be modeled usefully in Rust?
  - pitaj 6y ago
    I think Rust's model with smart pointers and deref could work really well with a colored pointer, short-pause GC like ZGC. Rust has the capability to do things like execute load barriers on access, so it could still work when objects have been moved around.
  - amaranth 6y ago
    The allocator API hands out `*mut u8` so... not really. If you changed the allocator API and everything that uses it and makes assumptions about how it works then sure, you could make it hand out a pointer to a pointer so you could come in later and update the inner pointer after you've done a GC pass. You couldn't do something like handing out a normal `Box` and keeping track of where it lives so you can patch it later though. Rust doesn't have move or copy constructors so as it gets passed around it'll just be `memcpy`'d and you'll lose track of it.
Rusky 6y ago
That's an interesting question, and there has been some work in that area. Getting shared mutability as a user of GC is basically the same as getting shared mutability in any other scenario in Rust. You use `UnsafeCell<T>` or a safe wrapper around it, like `Mutex` or `Cell`. You can get a feel for this even in idiomatic Rust using `Rc` instead of a tracing GC. When you start looking at other methods of GC things get trickier. Even with `UnsafeCell<T>` the GC can't, in general, know whether something is borrowed (mutably or immutably) by the mutator, so the problem to be solved is finding ways to enforce that there are no references into the heap at all, when collection needs to happen. But when you think about it, this is actually not so different from the usual problem of GC safepoints. The problem is the same- enforce that there are no un-rooted pointers into the heap, when collection needs to happen. And it turns out there are some tricks you can do with lifetimes to get borrowck to enforce safepoints for you, and it could even be made pretty ergonomic in the future. Some early discussion of the problem space: * http://blog.pnkfx.org/blog/categories/gc/ http://blog.pnkfx.org/blog/categories/gc/ * https://manishearth.github.io/blog/2015/09/01/designing-a-gc-in-rust/ https://manishearth.github.io/blog/2015/09/01/designing-a-gc... * https://manishearth.github.io/blog/2016/08/18/gc-support-in-rust-api-design/ https://manishearth.github.io/blog/2016/08/18/gc-support-in-... A design from Servo, and a paper to go with it: https://github.com/asajeffrey/josephine https://github.com/asajeffrey/josephine A series of blogposts describing a more recent attempt: https://boats.gitlab.io/blog/post/shifgrethor-i/ https://boats.gitlab.io/blog/post/shifgrethor-i/ The most recent attempt I know of: https://github.com/kyren/gc-arena/ https://github.com/kyren/gc-arena/ I think gc-arena is fairly similar to josephine- both treat the GC heap itself as a container-like object, requiring `&` or `&mut` access to dereference a GC pointer. Gc-arena also suggests that we could use generator yield points as GC safepoints- they have exactly the required lifetime properties. So you might (to borrow Python syntax) `yield from fn_that_allocates_gc_memory()`, with the compiler ensuring you don't hold any references into the heap across that call.
- ridiculous_fish 6y ago
  Great answer, thank you! Both gc-arena and josephine appear to take the "unidirectional" approach, where there is no recursive re-entrance into the GC heap. For example gc-arena will not collect while the heap is being mutated, which is Rust-friendly but also impractical. GC'd languages typically require reentrancy into managed code (managed -> native -> managed), and this has historically been the source of type confusion and other security vulnerabilities.

saagarjha 6y ago

I’m not sure I follow. Are you suggesting the addition of multiple mutable ownership of values to Rust, managed by a garbage collector?

ridiculous_fish 6y ago
No, I am talking about writing Rust code that refers to objects on a GC-managed heap. For example, assume v8-ish semantics: let mut cell = allocate(0.0); let counter : &mut f64 = cell.as_mut_ref(); *counter += 1; stuff(); *counter -= 1; Here `stuff()` may trigger further allocations which result in moving `cell`, leaving `counter` dangling.
- saagarjha 6y ago
  Ah. I am not a Rust expert but I think the language might actually support this sort of construct (though it might be inefficient to implement), as IIRC if you want something to stay at a fixed place in memory you need to “pin” it there.
- pirocks 6y ago
  Surely they way most gcs achieve this is by asking you to tell the gc when you aquire a reference to an object, and tell it again when you no longer need it. You could do that with a custom implementation of drop in rust.

Falell 6y ago

This isn't really directly related to your question, but I recall hearing that in Servo and Firefox, the usage of Rust is limited as it gets close to the DOM specifically because of interactions with the JS engine and its separate garbage collector, which Rust does not understand. Without any more specific knowledge, I bet the way a generational garbage collector moves data around really messes with Rust's view of the world...

monadic2 6y ago

If by GC you’re referring to its reference counting, either by Rc or Arc, there is no GC reachability beyond the reference counting. The responsibility for counting the contained object and dropping (cleanup before dealloc) is up to the type, either Rc or Arc (a stands for atomic, not automatic, as both are “automatic” in the sense that you never need to manually increment or decrement a reference). the owned, mutable object would contain the type information necessary to generate the right Rc calls ay the right time, but a distinct type is necessary to encapsulate the behavior. There are also escape hatches, between unsafe leaking and the RefCell type, to provide “interior mutability”, i.e. mutable aliasing via an without the memory safety issues which come with this. Note I have only had to use the unsafe bits when passing memory up to a c stack. I don’t believe there is a tracing GC implementation in the standard library, although I’ve heard plenty of discussion and you can find some simple implementations on crates.io. However, I would assume there would need to be some language changes to properly account for assumptions on how the Drop (free) functionality fires, not to mention significant backend work for tracing to work.

ridiculous_fish 6y ago
Let's put it this way: if you have a &mut to a heap allocated object (Box, whatever), you pretend it's unique, BUT its contents are also reachable by the global allocator, say, malloc. So it's not really a unique reference. If you allocate something new, Rust pretends it is independent, assuming that malloc won't muck with the other objects it knows about. What if we relax that assumption? Allocations may perturb other allocations - that's how moving GC heaps work! Can that be modeled usefully in Rust?
- pitaj 6y ago
  I think Rust's model with smart pointers and deref could work really well with a colored pointer, short-pause GC like ZGC. Rust has the capability to do things like execute load barriers on access, so it could still work when objects have been moved around.
- amaranth 6y ago
  The allocator API hands out `*mut u8` so... not really. If you changed the allocator API and everything that uses it and makes assumptions about how it works then sure, you could make it hand out a pointer to a pointer so you could come in later and update the inner pointer after you've done a GC pass. You couldn't do something like handing out a normal `Box` and keeping track of where it lives so you can patch it later though. Rust doesn't have move or copy constructors so as it gets passed around it'll just be `memcpy`'d and you'll lose track of it.

Rusky 6y ago

That's an interesting question, and there has been some work in that area. Getting shared mutability as a user of GC is basically the same as getting shared mutability in any other scenario in Rust. You use `UnsafeCell<T>` or a safe wrapper around it, like `Mutex` or `Cell`. You can get a feel for this even in idiomatic Rust using `Rc` instead of a tracing GC. When you start looking at other methods of GC things get trickier. Even with `UnsafeCell<T>` the GC can't, in general, know whether something is borrowed (mutably or immutably) by the mutator, so the problem to be solved is finding ways to enforce that there are no references into the heap at all, when collection needs to happen. But when you think about it, this is actually not so different from the usual problem of GC safepoints. The problem is the same- enforce that there are no un-rooted pointers into the heap, when collection needs to happen. And it turns out there are some tricks you can do with lifetimes to get borrowck to enforce safepoints for you, and it could even be made pretty ergonomic in the future. Some early discussion of the problem space: * http://blog.pnkfx.org/blog/categories/gc/ http://blog.pnkfx.org/blog/categories/gc/ * https://manishearth.github.io/blog/2015/09/01/designing-a-gc-in-rust/ https://manishearth.github.io/blog/2015/09/01/designing-a-gc... * https://manishearth.github.io/blog/2016/08/18/gc-support-in-rust-api-design/ https://manishearth.github.io/blog/2016/08/18/gc-support-in-... A design from Servo, and a paper to go with it: https://github.com/asajeffrey/josephine https://github.com/asajeffrey/josephine A series of blogposts describing a more recent attempt: https://boats.gitlab.io/blog/post/shifgrethor-i/ https://boats.gitlab.io/blog/post/shifgrethor-i/ The most recent attempt I know of: https://github.com/kyren/gc-arena/ https://github.com/kyren/gc-arena/ I think gc-arena is fairly similar to josephine- both treat the GC heap itself as a container-like object, requiring `&` or `&mut` access to dereference a GC pointer. Gc-arena also suggests that we could use generator yield points as GC safepoints- they have exactly the required lifetime properties. So you might (to borrow Python syntax) `yield from fn_that_allocates_gc_memory()`, with the compiler ensuring you don't hold any references into the heap across that call.

ridiculous_fish 6y ago
Great answer, thank you! Both gc-arena and josephine appear to take the "unidirectional" approach, where there is no recursive re-entrance into the GC heap. For example gc-arena will not collect while the heap is being mutated, which is Rust-friendly but also impractical. GC'd languages typically require reentrancy into managed code (managed -> native -> managed), and this has historically been the source of type confusion and other security vulnerabilities.