`Rc` is `!Send` but not thread-dependant?

language design Unsafe Code Guidelines
1

Consider this case:

use std::cell::RefCell;
use std::rc::{Rc, Weak};

pub struct Tree<T> {
    root: Option<Rc<Node<T>>>,
}

struct Node<T> {
    parent: Weak<Node<T>>,
    children: RefCell<Vec<Rc<Node<T>>>>,
}

Here Tree<T> can be Send if:

  • T is Send,
  • There's no public safe APIs that can get an Rc<Node<T>> or a Weak<Node<T>> from a Tree<T>.

In general, Rc is !Send because it shares the reference counters among threads. That's different from those real thread-dependant things like LocalKey.

I wonder if there could be a (safe) way to opt in the Tree<T> to be Send as if the Rc<T>s inside are not actually shared among threads. Like, to introduce a marker attribute #[thread_independant] and then track the methods of Tree<T> that cannot expose the Rc<T> inside? (Is that possible with the strict provenance enabled?)

BTW, this comes from a real case of UI tree rendering. As parsing a XML DOM tree and initializing a custom UI tree (where Rc and Weak are heavily used) is time-consuming, I switched that initialization procedure to new thread to avoid blocking the UI thread, and then sent the whole initializated tree back to the UI thread. I have avoided using thread-dependant things like thread_locals, but I hope if there are something that can enforce the safety precondition I've relied on.

2

Theoretically it's possible, but I doubt that it can be done easily in practice. Remember that Rc is not a special type and users can implement their own Rc-like types. The whole Send/Sync system is essentially a rudimentary user-defined proof system for data race safety built on top of the trait system. If not for the auto-derive, the traits (and the thread stuff) could've been theoretically defined in a third-party library.

The proof which you want requires a much more powerful proof system than we have, so we work around it by using unsafe-based "axioms". In other words, it's perfectly fine to use unsafe impl for such cases.

1 Like
3

So I think that the fundamental problem with making code like this safe is that the reason it's safe is that the entire Tree is owned by its root – the safety argument is "if you send the root to a different thread, the entire tree moves along with it and contains the only copies of the Rcs". In order to enforce that, you need to prove not only that the Rcs can't become exposed while in the Tree, but also that they can't have aliases outside the Tree by other means (e.g. because the tree was originally constructed by cloning an Rc it had obtained from elsewhere).

The most plausible approach I can think of is to use something like static-rc (which I haven't used myself and is still experimental, but which seems to have the right functionality) – the basic idea is that your code is only safely sendable because all the copies of the Rc are within the same tree, which also implies that they have exactly 1 weak and 1 strong reference, so a proof that this was safe would also prove that the reference count would be statically known at every point in the program. But if you statically know the reference count, there's no pont in actually storing the reference count in memory – you might as well just check it at compile time. That would also get you the Send behaviour you need because if the reference count isn't being update at runtime, there's no need to update it non-atomically. (EDIT: This doesn't work in your case because the parents have variable numbers of children, and each child is referencing its parent as a whole rather than an element of the children array – it would work for binary trees, though.)

As a side note, I'm curious as to whether Arc would optimize well on this sort of code (as the compiler would have enough information to be able to optimize some of the atomicness out, potentially producing the same code as with Rc). My guess is "maybe for allocation, but no for deallocation" because the deallocation code wouldn't be able to assume the reference count an thus would have to do a (slow) atomic-RMW to decrease it.

4

Yes, it is. But I think of the pointer's provenance. Each strict provenance API seems able to track which pointer comes from which allocated object. So I think it may be possible to collect the points-to informations via a static analysis (but may be imprecise). However, the pointer's provenances are not so strong as the lifetime notations that carry the coming-from information in the function's signatures.

What if we add a provenance generic parameter to Tree?

pub struct Tree<T, const PROV: Provenance> {
    root: Option<Rc<Node<T, PROV>>>,
}

struct Node<T, const PROV: Provenance> {
    parent: Weak<Node<T, PROV>>,
    children: RefCell<Vec<Rc<Node<T, PROV>>>>,
}

where the Provenance is a semilattice indicating which tree it belongs to (quite similar to a covariant lifetime parameter but doesn't talk about its lifetime). Then, as long as there are no pub safe APIs of Tree<T, PROV> that returns any type that exposes the PROV out, the Tree<T, PROV> is safe to be Send (of course with T: Send).

5

Oh, I just realized that the reference counting is not necessary in this case at all!

Since the Tree<T, PROV> owns all tree nodes, and it is the only way to get the Rc<Node<T, PROV>> from the Tree<T, PROV>, then all the parent: Weak<Node<T, PROV>> inside the tree are alive if Tree<T, PROV> is alive.

1 Like
6

It would be safe to move all Rcs together to another thread (if T: Send), but currently Rust can't guarantee that there won't be any Rc left behind.

Tracking whether all Rcs are together would be possible if Rust supported self-referential lifetimes. You would need Rc<'tree, T> with the lifetime pointing back to the Tree root. Currently such construct is not possible in the borrow checker (when you have such lifetime, the borrowed-from object can't be moved).

3 Likes
7

Users can't implement custom Rc-like types in Rust? Provenance is not relevant here. It applies to raw pointers and Rc is built on top of them, so provenance is automatically "built-in".

You want some kind of escape analysis with an ability to specify complex constraints on the type system level. As I wrote, we need a significantly more powerful type system for this.

I don't think it's sufficient. Consider scoped threads, you would be able to spawn threads which work with Rcs inside the type in parallel, thus potentially breaking Rc.

3 Likes
8

So the discussion is mostly about how it would seem to be difficult to make a safe way to opt in to this, it would require a proof of the same. But just to make sure you are just doing something like:

unsafe impl<T> Send for Tree<T> where T: Send {}

You could play some tricks and just make it temporarily Send to contain the unsafe a little bit, if you would like to hand out some of those Rcs. There do seem to be libraries for this and I wonder if it's a worthwhile addition to std.

9

Yes, and that's what I did in the real case:

/// Data that are not tied to a specific thread, and the ownership
/// of which can be transfered among threads safely.
pub unsafe trait ThreadIndependant {}

unsafe impl<T: Send> ThreadIndependant for T {}
unsafe impl<T: ThreadIndependant> ThreadIndepant for Rc<T> {}
unsafe impl<T: ThreadIndependant> ThreadIndependant for Weak<T> {}

// Here `Send` bound could not be added because many of them can contain `Rc`.
pub trait TreeElement: ThreadIndependant { /* ... */ }

pub struct Tree {
    root: Rc<dyn TreeElment>,
}

impl Tree {
    /// # Safety
    /// No `Rc` nor `Weak` exists to share anything inside the `Tree`.
    pub unsafe send(self) -> TreeSendWrapper {
        TreeSendWrapper { tree: self }
    }
}

pub struct TreeSendWrapper {
    tree: Tree,
}

// SAFETY: rely on the safety contract of `Tree::send`
unsafe impl Send for TreeSendWrapper {}

The problem is: it is hard to enforce that any Rc cannot exposed out of the Tree, and there would be tens of unsafe impl ThreadIndependant for Node1, unsafe impl ThreadIndependant for Node2, etc., which, IMO, is quite tedious, and the users tend to ignore these "noises" to them.

That's why I'm going to find some stronger proofs by the compiler other than the unsafe trait ThreadIndependant.

10

Yes, users can, as Rc isn't a lang item.

I mention provenance just because Rc is built on top of raw pointers an may make use of their provenance (I hope so).

That's true, just very similar to what lifetime does to track the output parameter comes from which input parameter. Like fn foo<'a, 'b>(a: &'a i32, b: &'b i32) -> &'a i32 means that the returned reference borrows from the input reference a, could there be similar things like fn bar<'a, 'b>(a: 'a Rc<i32>, b: 'b Rc<i32>) -> 'a Rc<i32> indicating the returned Rc<i32> is cloned from the input parameter a?

EDIT: for unsafe fn baz(a: *const i32, b: *const i32) -> *const i32, the provenance of the output pointer must be either of:

  1. the provenance of a;
  2. the provenance of b;
  3. a new allocated object;
  4. from a static object;
  5. from an exposed provenance;
  6. invalid provenance.

Similarly, for fn bar(a: Rc<i32>, b: Rc<i32>) -> Rc<i32>, the returned Rc<i32> can be either of the above case 1-4 (5 and 6 are unsafe so it is not considered here).

If my understaning is right, For unsafe fn baz we can already analysis which provenance the returned raw pointer belongs to (maybe ambiguous) with the strict provenance API enabled? That's why I guess the provenance can be leveraged for that kind of analysis of fn bar the Rc's case.

11

Perhaps the example is not complete or I'm not understanding this, but I don't think TreeElement can be ThreadIndependent/Send/SendLite? I believe the entire Tree can be Send, but if individual nodes are Send then couldn't there be a case where a node is sent to thread 2 but operations continue on the tree in thread 1? And if that node can't be sent without the whole tree, it probably doesn't need to be Send.

If you're worried about the unsafe genie escaping the bottle I think limiting unsafe impl Send to a function local wrapper type for the purposes of initialization works well enough.

12

I agree with this approach. To elaborate, it would be a struct like

// Function local if send/receive logic isolated to a function. Otherwise, module-local to avoid escaping this logic.
struct SendTree(Tree);

unsafe impl Send for SendTree {}

// Optional
impl SendTree {
  fn new(tree: Tree) -> SendTree {
    // Validate `Tree` to ensure that all contained `Rc`s have a single strong count.
    // This could be debug-only or test-only.
  }
}

Then, you'd wrap the Tree in SendTree to send it across a channel and on the receiving end, you'd unwrap it. If you can't isolate this logic within a single function, you could create a tiny module to isolate the logic to limit the blast radius of code you have to look at to reason about unsafe-safety.

13

I was about to suggest UniqueRc but of course there also must not be any Weak pointers either.

That suggest a differently weak version of ownership where it blocks the only de-allocation or de-initialization (i.e. manipulates weak and strong count) but does not claim ownership of the pointed-to-place itself. So no manipulation of the contents—counts and value—by any means through that value itself. It can only be upgraded to an actual Weak or Rc by presenting it with a Weak to the same allocation, proving the current thread owns that node. Of course it would be quite troublesome to use since it necessarily leaks on a normal Drop. Might only work ergonomically with truly linear types (a tree built with it would recursively reap its all children on Drop, which you'd want anyways to avoid stack overflow, where it could present the owning root to upgrade the pointers).

14

You would also need to check weak count. A escaped weak pointer could be used to resurrect an Rc from the original thread. Since presumably the reason for Rc here is weak parent pointers inside the tree you would also need to calculate the expected number of weak pointers.

2 Likes
15

A more "rusty" design would make this less painful: use a vector or arena of nodes and store the indices of child / parent nodes. It would likely also be faster due to better cache usage, especially if you can arrange so that nodes that are accessed after each other are close in the vector.

Such a vector of nodes would be trivial to transfer to another thread. As a bonus you could also store the child indices inline up to a certain max number, which can be a worthwhile optimisation in some cases. Profiling would be needed.

If you build the tree once and don't modify it this would be ideal, if you need to modify it to add/remove nodes you might want to have a list of free nodes that can be reused.

There are many valid points in the design space of data oriented graph/tree representations in Rust. Consider looking at the petgraph crate for inspiration.

1 Like