Stacked Borrows incompatible with Garbage Collectors?

There has been a lot of experiments with garbage collection in rust.

I was recently doing some experiments with a trace collector, but am always running into issues with Stacked Borrows in Miri. It seems to me that stacked borrows are fundamentally incompatible with GC. A GC is dereferencing pointers all over the heap where it does not have an item on the borrow stack. As well as mutating mark bits everywhere.

Are stacked borrows incompatible with garbage collection in Rust? Or maybe there is an escape hatch around stacked borrows that allows both systems to coexist? Or maybe I am just approaching this fundamentally wrong and there is a way to make it work.

I am concerned that if stacked borrows ever become part of the rust spec it will rule out entire area's of computing (like gc) that are valid today.

For example in the code below, I take some pointers to stack locations then try and access them but hit borrow stack errors in Miri.

1 Like

I wonder why it doesn't have an item on the borrow stack though. If you're dereferencing those pointer it should mean you got them from somewhere, and at that point they should have been valid.

In general, the original raw pointer you got from the malloc call (or Box::into_raw) is always at the bottom of the borrow stack, and can therefore not be invalidated by anything else, including mutable references. Copies and casts of the original pointer also have the same tag, so they also cannot be invalidated.

You should make sure to never keep around a raw pointer you got by converting into and back from a mutable reference.

3 Likes

I added a playground sample. You can run it with Miri.

You should make sure to never keep around a raw pointer you got by converting into and back from a mutable reference.

ahh, that makes sense.

Is there a way to remove the stack-borrow type information from a pointer created from a reference?

No, you can't circumvent the rules and create a new "root" raw pointer. The rules are actual rules.

No, you can't circumvent the rules and create a new "root" raw pointer.

Looks like there is a sound way to convert them based on how Box::into_raw does it (go from "managed" pointers to "root" pointers). But it definitely seems like sticking with root pointers is best way to avoid violating stack borrow rules.

Well, more generally, you can treat any raw pointer as a root pointer as long as you never touch the things that you got that raw pointer from. Things below your "root pointer" in the stack will not invalidate it unless you touch them. Therefore it does not matter what into_raw does as long as you only access the box via that raw pointer and things derived from it.

Similarly if you make a mutable reference to a stack variable, turn that into a raw pointer, then never touch the stack variable again through anything but that raw pointer, then it also behaves as a root pointer.

1 Like

Wow, that was really helpful explanation. It completely explains the error I was seeing in the playground. Thank you.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.