4 ms·

The existence of the StackRoot type is definitely a missing piece of the puzzle, thank you. So we have Object and StackRoot. But then what is a "root object?"

The existence of the StackRoot type is definitely a missing piece of the puzzle, thank you. So we have Object and StackRoot. But then what is a "root object?" let rooted: Vec<Object<'root>> = ...; // we have a vec of root objects I would expect this vector to just contain Objects? I think conceptually you have two different Object types: a "dangling" Object that is subject to collection, and a "rooted" Object which is referenced by a root stored in the RootSet. Part of my confusion is that there's no vocabulary to distinguish these. In this code: root!(value, gc) Visually it appears to "do something" to value but in fact there's two different variables, with two different types, both named 'value'. It would be clearer at least to me to reify that by giving them different types instead of calling both Object. In a moving GC this distinction becomes unavoidable: dangling objects are raw pointers, while rooted objects refer to the root location itself and require double indirection to access. Anyways it's just a suggestion, take it or leave it. It's very cool how Rust's lifetimes let you enforce that no collections happen while an Object dangles. One last thought: because you're already on the hook for passing in the GC when dereferencing an Object, you could exploit this by making Object references just a 32 bit offset, relative to the GC's heap. This would let you save some memory.

celeritascelery 4y ago
I had hard time trying to explain the concept without getting deep in the implementation. You have given me some ideas of how I can explain things clearer. Mentioning StackRoot seems like a critical part. > So we have Object and StackRoot. But then what is a "root object?" If you think of Object's as pointer to heap data, then "root object" is just a pointer to heap data where that data also has a entry in the root set pointing to it (the data is rooted). You are right that the object does not change types, only rebinds the lifetime. Initially I actually had them as two separate types; `RootObject` and `Object`. But this ended up making things harder because now I had to create two version of many functions, one for "dangling objects" and another for "rooted objects". And I was converting between the two types all the time. Or I could use generic code, but generic programming is more painful then concrete functions. I ended up unifying them since they had nearly identical properties, and they are only distinguished by lifetimes (bound to the GC or to a StackRoot). But better and more consistent nomenclature would make things more understandable. > In a moving GC this distinction becomes unavoidable: dangling objects are raw pointers, while rooted objects refer to the root location itself and require double indirection to access. Is that always true? My understanding is that generally moving GC's will put a forwarding pointer at the old address and update all references during collection. I want to make this GC moving at some point and didn't think the rooting system would be a limitation. > because you're already on the hook for passing in the GC when dereferencing an Object, you could exploit this by making Object references just a 32 bit offset You don't need a reference to the GC to dereference an object. An object is always safe to deference. But you do need to pass the GC to get a field of something in the GC heap (i.e. something that the object is pointing to, like a vector or a Cons cell). This is because GC heap allocated types use interior mutability and something could change under your nose and take an object that was previously reachable from a root and make it no longer reachable (Similar to my Preventing Escapes section). Therefore we require that taking the field of GC heap allocated type takes a reference to GC, and therefore makes it "dangling" by default. This was an advantage of the 2-type rooting systems I mentioned earlier. If we had a "dangling object" type we didn't need to take reference to the GC to access a field because we know that it's lifetime was borrowed from the GC already (i.e. It was already dangling). But I had not thought about using a 32-bit handle. I will look into that once I actually start using the Allocator API.
- ridiculous_fish 4y ago
  Thanks for the reply, what you wrote makes sense to me. I want to expand on the copying GC ideas: > I want to make this GC moving at some point and didn't think the rooting system would be a limitation. Currently the rune RootSet is "a list of pointers to be treated as roots" and so long as the pointer is in the list, the GC will not collect it, and you are free to pass around copies of that pointer. But if the heap object were to be moved, the GC could only update the pointers in the RootSet, not those on the native C (err, Rust) stack. So you would get dangling pointers, which is bad. One solution for this is double indirection: 1. StackRoot changes from "a pointer which should be rooted" to "a location in memory containing a pointer which should be rooted, and this location is known and updated by the GC." 2. You stop passing around copies of pointers, you pass around pointers to a StackRoot which itself contains a pointer. We do this because the GC may change the pointer stored in a StackRoot at any collection point. Hence double indirection: we have a pointer to a location which is known by the GC, which in turn contains a pointer to our data. This approach is mind-bending and took me a while to grok.
  - celeritascelery 4y ago
    ahh! That makes sense now. You are right, that would have to change to enable a copying collector.

celeritascelery 4y ago

I had hard time trying to explain the concept without getting deep in the implementation. You have given me some ideas of how I can explain things clearer. Mentioning StackRoot seems like a critical part. > So we have Object and StackRoot. But then what is a "root object?" If you think of Object's as pointer to heap data, then "root object" is just a pointer to heap data where that data also has a entry in the root set pointing to it (the data is rooted). You are right that the object does not change types, only rebinds the lifetime. Initially I actually had them as two separate types; `RootObject` and `Object`. But this ended up making things harder because now I had to create two version of many functions, one for "dangling objects" and another for "rooted objects". And I was converting between the two types all the time. Or I could use generic code, but generic programming is more painful then concrete functions. I ended up unifying them since they had nearly identical properties, and they are only distinguished by lifetimes (bound to the GC or to a StackRoot). But better and more consistent nomenclature would make things more understandable. > In a moving GC this distinction becomes unavoidable: dangling objects are raw pointers, while rooted objects refer to the root location itself and require double indirection to access. Is that always true? My understanding is that generally moving GC's will put a forwarding pointer at the old address and update all references during collection. I want to make this GC moving at some point and didn't think the rooting system would be a limitation. > because you're already on the hook for passing in the GC when dereferencing an Object, you could exploit this by making Object references just a 32 bit offset You don't need a reference to the GC to dereference an object. An object is always safe to deference. But you do need to pass the GC to get a field of something in the GC heap (i.e. something that the object is pointing to, like a vector or a Cons cell). This is because GC heap allocated types use interior mutability and something could change under your nose and take an object that was previously reachable from a root and make it no longer reachable (Similar to my Preventing Escapes section). Therefore we require that taking the field of GC heap allocated type takes a reference to GC, and therefore makes it "dangling" by default. This was an advantage of the 2-type rooting systems I mentioned earlier. If we had a "dangling object" type we didn't need to take reference to the GC to access a field because we know that it's lifetime was borrowed from the GC already (i.e. It was already dangling). But I had not thought about using a 32-bit handle. I will look into that once I actually start using the Allocator API.

ridiculous_fish 4y ago
Thanks for the reply, what you wrote makes sense to me. I want to expand on the copying GC ideas: > I want to make this GC moving at some point and didn't think the rooting system would be a limitation. Currently the rune RootSet is "a list of pointers to be treated as roots" and so long as the pointer is in the list, the GC will not collect it, and you are free to pass around copies of that pointer. But if the heap object were to be moved, the GC could only update the pointers in the RootSet, not those on the native C (err, Rust) stack. So you would get dangling pointers, which is bad. One solution for this is double indirection: 1. StackRoot changes from "a pointer which should be rooted" to "a location in memory containing a pointer which should be rooted, and this location is known and updated by the GC." 2. You stop passing around copies of pointers, you pass around pointers to a StackRoot which itself contains a pointer. We do this because the GC may change the pointer stored in a StackRoot at any collection point. Hence double indirection: we have a pointer to a location which is known by the GC, which in turn contains a pointer to our data. This approach is mind-bending and took me a while to grok.
- celeritascelery 4y ago
  ahh! That makes sense now. You are right, that would have to change to enable a copying collector.