I came across an interesting question on Stack Overflow recently, and I found the process through which I developed my answer to be interesting on its own, so I’m going to document it here.
If you are unfamiliar with Rust’s Send trait, I would suggest reading Send and Sync in the Rustonomicon. The bird’s-eye view is that values implementing Send are safe to send to other threads. If you attempt to transfer a value to another thread and it does not implement the Send trait, you will receive a compile-time error.
The question was asking how to efficiently clone and send a data structure to another thread. The structure was recursive and used Rc for the recursive values. Here’s an example of the kind of structure being discussed:
#[derive(Clone)]
struct Node {
children: Vec<Rc<Node>>,
data: HugeAmountOfData,
}
// This type is a placeholder for a very large structure that we want to avoid
// copying as much as possible.
#[derive(Clone)]
struct HugeAmountOfData {}
The Rc<T> type is a reference-counted smart pointer that implements shared ownership of a T. The reference count is maintained non-atomically, so Rc<T> never implements Send, even if T does; sending an Rc<T> to another thread could cause corruption of the reference count, resulting in the best case scenario of a memory leak, and the worst case of a use-after-free and/or double-free. (The related type Arc<T> manages its reference count atomically, so it implements Send if T also does. The question specifically mentioned wanting to avoid Arc for performance reasons.)
Going back to the question, the problem to be solved was how to clone the entire structure and send it to another thread. The workaround posed in the question was to create a second set of types where Rc was replaced with Box and doing the clone in two steps: copy the data from the Rc structure to the Box structure, send the Box structure to the destination thread (Box<T> is Send when T also is), then move the data from the Box structure back into the Rc structure. The motivation behind the question was to avoid having to move the data a second time. The ideal solution would be to clone it once and then send it, which doesn’t work because Rc is never Send.
But what if we know that the Rc value is currently not shared? In that case, we should be able to send the Rc to another thread. In the terms of the Rc type, we should be able to safely send an Rc<T> to another thread if all of the following are true:
TisSend.- The strong reference count is 1.
- The weak reference count is 0.
The last two conditions together come up frequently here, so let’s create a new term for an Rc that satisfies them: an Rc is independent when its strong count is 1 and its weak count is 0.
We can implement sending independent Rcs to other threads with a wrapper that explicitly implements Send. The code is incredibly simple and easy to understand:
pub struct SendableRc<T>(Rc<T>);
impl<T: Clone> SendableRc<T> {
pub fn new(mut value: Rc<T>) -> Self {
Rc::make_mut(&mut value);
Self(value)
}
}
impl<T> SendableRc<T> {
pub fn into_inner(self) -> Rc<T> {
self.0
}
}
unsafe impl<T: Send> Send for SendableRc<T> {}
The linchpin of this code is the Rc::make_mut() call, after which value is guaranteed to be independent. If value has a strong count greater than 1, the inner T is cloned (which is why the T: Clone bound is required) and value is replaced with a new Rc containing the clone. Otherwise, if it has a weak count greater than 0, then all weak references are cleared and point nowhere. If the strong count is already 1 and the weak count already 0, nothing is done.
The into_inner() method is provided to extract the Rc, which discards the wrapper. And, finally, we explicitly implement Send as long as T: Send.
Let’s try it out!
fn main() {
let x = Rc::new(Node {
children: vec![],
data: HugeAmountOfData {},
});
let sendable = SendableRc::new(x);
std::thread::spawn(move || {
let x = sendable.into_inner();
}).join().unwrap();
}
Oh no, that didn’t work!
error[E0277]: `Rc<Node>` cannot be sent between threads safely
--> src/main.rs:37:24
|
37 | std::thread::spawn(move || {
| _____------------------_^
| | |
| | required by a bound introduced by this call
38 | | let x = sendable.into_inner();
39 | | }).join().unwrap();
| |_____^ `Rc<Node>` cannot be sent between threads safely
Wait, but we’re not sending an Rc, we’re sending a SendableRc! Why doesn’t this work? Reading more of the compiler output, we get to this:
note: required because it appears within the type `Node`
--> src/main.rs:24:8
|
24 | struct Node {
| ^^^^
note: required for `SendableRc<Node>` to implement `Send`
--> src/main.rs:5:22
|
5 | unsafe impl<T: Send> Send for SendableRc<T> {}
| ---- ^^^^ ^^^^^^^^^^^^^
| |
| unsatisfied trait bound introduced here
Ah, beans! I forgot that Node contains its own Rc, so SendableRc<Node> isn’t Send because Node isn’t.
In other words, SendableRc is a sound wrapper, but it doesn’t help us here because it’s only Send when T also is, and it’s not in this case — Node isn’t Send since it contains an Rc.
Rust saved us from doing something horribly unsound; we can’t just shallow-clone the top-level Node, we need to deep-clone the whole tree! But… once we do that, how do we communicate to the compiler that this is safe?
We have a scenario where our type is not guaranteed to be Send in all cases, but it can be Send sometimes. Helping the compiler understand this involves two pieces:
- A trait that communicates that a value is
Sendsometimes, and provides a way to make the current valueSend. - A wrapper that can wrap values implementing this new trait, implementing
Sendfor them.
For example, in the Node case, “make the current value Send” means “recursively make all Rc‘s independent.”
Here’s what that trait could look like:
pub unsafe trait SendIfUnshared {
fn unshare(&mut self);
}
Pretty straightforward… but what’s that unsafe keyword doing there?
An unsafe trait is one that can cause soundness issues if incorrectly implemented. It requires usage of the unsafe keyword in the corresponding impl block to remind the author (and readers) that there is a specific contract that must be upheld to avoid unsound code. We can already see this in the SendableRc implementation above — we use unsafe when implementing Send because it’s an unsafe trait; we uphold the contract of Send by requiring T: Send as well as making the contained Rc independent, and disallowing access to the Rc without discarding the wrapper (otherwise the Rc could be cloned, giving us a shared, sendable Rc, which would be unsound).
The contract of our new SendIfUnshared trait is:
After calling SendIfUnshared::unshare() on a value, that value must be safe to send to other threads until it is read from or written to again.
We have to disallow reads because Rcs can be cloned by a shared reference. Moving the value is the only operation that preserves its Send-ness according to this contract.
Given this trait, we can now implement it on Rc<T>:
// SAFETY: We require T:SendIfUnshared, we ensure the Rc isn't shared with
// anything else by calling Rc::make_mut(), and we forward the unshare() call to
// the inner T.
unsafe impl<T> SendIfUnshared for Rc<T>
where T: SendIfUnshared + Clone
{
fn unshare(&mut self) {
Rc::make_mut(self).unshare();
}
}
The safety comment documents why this is safe. We can now implement this trait for Node, after which Rc<Node> will also implement SendIfUnshared.
// SAFETY: We forward the unshare() call to the contained Rc's, and all other
// owned values are Send.
unsafe impl SendIfUnshared for Node {
fn unshare(&mut self) {
for i in &mut self.children {
i.unshare();
}
}
}
Not too bad! Now, we have enough to implement our Send wrapper.
pub struct SendableSendIfUnshared<T>(T);
// SAFETY: We require T:SendIfUnshared to construct values, we invoke unshare()
// on it, and we do not allow access to the inner T except by destroying the
// wrapper.
unsafe impl<T: SendIfUnshared> Send for SendableSendIfUnshared<T> {}
impl<T> SendableSendIfUnshared<T> {
pub fn into_inner(self) -> T {
self.0
}
}
impl<T: SendIfUnshared> SendableSendIfUnshared<T> {
pub fn new(mut inner: T) -> Self {
inner.unshare();
Self(inner)
}
}
It’s worth noting that I don’t derive any traits on the wrapper. Why? Recall the contract of SendIfUnshared — the value only remains effectively-Send if it’s not written to or read from. If we added #[derive(Debug)] then this constraint would be violated, because T‘s implementation of Debug could (and probably would) read from it! If the Debug implementation for Node decided to clone one of the Rcs and store it somewhere else, sending the Node to another thread via the wrapper would be unsound. Simply deriving Debug would open a soundness hole that could be created by completely safe code, and therefore we cannot derive it! The same goes for pretty much any other widely-useful trait. Therefore, to be safe we choose to derive nothing.
Simply put, in order to do anything with the inner T, the Sendable wrapper must be discarded. This operation is implemented by the into_inner() method, which consumes the wrapper to produce the contained value. Sending the value to another thread after this would require creating another wrapper, which will invoke unshare() on it, making it safe to send once again.
Let’s see if this new implementation works.
fn main() {
let x = Node {
children: vec![],
data: HugeAmountOfData {},
};
let x = SendableSendIfUnshared::new(x);
std::thread::spawn(move || {
let x = x.into_inner();
dbg!(x);
}).join().unwrap();
}
This compiles and runs, yielding this output:
[src\main.rs:79] x = Node {
children: [],
data: HugeAmountOfData,
}
Perfect! This does exactly what we needed: it eliminates the need for a second Box-based structure to make the data Send, which in turn eliminates the need to convert all of the Boxes into Rcs in the thread receiving the value. The values are copied only once!
One final addition helps make this wrapper more ergonomic:
pub trait SendIfUnsharedExt: SendIfUnshared + Sized {
fn into_sendable(self) -> SendableSendIfUnshared<Self> {
SendableSendIfUnshared::new(self)
}
}
impl<T: SendIfUnshared> SendIfUnsharedExt for T {}
This gives us an into_sendable() method on all values implementing SendIfUnshared so that we can write x.into_sendable() in place of the more verbose SendableSendIfUnshared::new(x).
In the future, when Rust implements trait specialization, we could have a blanket implementation of SendIfUnshared for all values that already implement Send — the unshare() method wouldn’t have to do anything.
If you’ve made it this far, you probably spotted one potential pitfall: future changes to the Node type might introduce a non-Send member, which would make Node‘s implementation of SendIfUnshared unsound. Thankfully, there’s a simple way we can help protect against this.
The first piece is a simple no-op function that asserts that its argument implements Send. We can use this to cause compile-time errors when values aren’t Send.
#[inline]
fn assert_send(_: &impl Send) {}
The second piece is to destructure self in implementations of SendIfUnshared. If any of the destructured variables are unused, an assert_send() call should be added for them. Here’s what that would look like for Node:
// SAFETY: We forward the unshare() call to the contained Rc's, and all other
// owned values are Send.
unsafe impl SendIfUnshared for Node {
fn unshare(&mut self) {
let Node { children, data } = self;
for i in children {
i.unshare();
}
assert_send(data);
}
}
This change should not impact code generation at all, since assert_send() doesn’t do anything at runtime. It will allow us to catch problems at compile-time:
- If a new field is added to
Node, the destructuring assignment (let Node { ... } = self;) will fail to compile because it does not include all fields. This will force the developer to look at this trait implementation. Realizing what it does, they will hopefully add anassert_send()call for the new field, which will fail to compile if the type of that field doesn’t implementSend. - If the type of a field is changed, the existing
assert_send()calls will ensure that the new type is alsoSend.
And there we have it — a safe mechanism for representing sometimes-sendable values in Rust!
You can play around with this code on the Rust Playground.